Lecture 5, slide 15

Now associate u_i Î Rⁿ (||u_i||2 = 1) to the node i. The idea is that if u_i u_j = 1 (vector inner product) then i and belong to the same set, whereas if u_i u_j = -1 they belong to different subsets.
If the product is in between a random technique will decide, i.e. a random vector r Î Rⁿ will be generated and S := {i : ru_i > 0}. As before x_ij:= u_i u_j, and we solve as follows.
Given a solution X the vectors u_i can be computed via a Cholesky decomposition.