HW4 normalized cut grading comments

[Haijie Gu]

In the grading of homework 4 problem 2, most of you get comments like: return D^{-1/2} U which lacks enough explanation.

So here it is:

The normalized cut essentially solves the following generalized eigenvalue problem

(D-W)y = \lambda Dy

By taking the transform: z = D^{1/2}y, the above problem becomes:

D^{-1/2}(D-W)D^{-1/2} z = \lambda z

Once you got z back by doing SVD on D^{-1/2}(D-W)D^{-1/2}, you need to recover y by taking y = D^{-1/2}z.

Best,

-jay