to discard the discreteness condition and instead allow that fi takes arbitrary values in R.This leads to the relaxed optimization problem re f'Lf subject to ff=vn. (4) By the Rayleigh-Ritz theorem (e.g.,see Section 5.5.2.of Luitkepohl,1997)it can be seen immediately that the solution of this problem is given by the vector f which is the eigenvector corresponding to the second smallest eigenvalue of L(recall that the smallest eigenvalue of L is 0 with eigenvector 1). So we can approximate a minimizer of RatioCut by the second eigenvector of L.However,in order to obtain a partition of the graph we need to re-transform the real-valued solution vector f of the relaxed problem into a discrete indicator vector.The simplest way to do this is to use the sign of f as indicator function,that is to choose ∈Aiff≥0 Effi<0. However,in particular in the case of k>2 treated below,this heuristic is too simple.What most spectral clustering algorithms do instead is to consider the coordinates fi as points in R and cluster them into two groups C,C by the k-means clustering algorithm.Then we carry over the resulting clustering to the underlying data points,that is we choose ∈A if fi∈C ∈Aiff∈C. This is exactly the unnormalized spectral clustering algorithm for the case of k=2. 5.2 Approximating RatioCut for arbitrary k The relaxation of the RatioCut minimization problem in the case of a general value k follows a similar principle as the one above.Given a partition of V into k sets A1,...,Ak,we define k indicator vectors hi=(h1.j,...,hn.i)'by hi.j J1/4 if∈A (i=1,,n;j=1,.,) (5) 00 otherwise Then we set the matrix HE Rnxk as the matrix containing those k indicator vectors as columns. Observe that the columns in H are orthonormal to each other,that is H'H=I.Similar to the calculations in the last section we can see that hLh =cut(A.A) A Moreover,one can check that h;Lhi (H'LH)ii. Combining those facts we get RatioCut(A,,Ak)=∑Lh:=∑(H'LH)i=Tr(H'LH, 11to discard the discreteness condition and instead allow that fi takes arbitrary values in ❘. This leads to the relaxed optimization problem min f∈❘n f 0Lf subject to f ⊥ ✶, kfk = √ n. (4) By the Rayleigh-Ritz theorem (e.g., see Section 5.5.2. of L¨utkepohl, 1997) it can be seen immediately that the solution of this problem is given by the vector f which is the eigenvector corresponding to the second smallest eigenvalue of L (recall that the smallest eigenvalue of L is 0 with eigenvector ✶). So we can approximate a minimizer of RatioCut by the second eigenvector of L. However, in order to obtain a partition of the graph we need to re-transform the real-valued solution vector f of the relaxed problem into a discrete indicator vector. The simplest way to do this is to use the sign of f as indicator function, that is to choose ( vi ∈ A if fi ≥ 0 vi ∈ A if fi < 0. However, in particular in the case of k > 2 treated below, this heuristic is too simple. What most spectral clustering algorithms do instead is to consider the coordinates fi as points in ❘ and cluster them into two groups C, C by the k-means clustering algorithm. Then we carry over the resulting clustering to the underlying data points, that is we choose ( vi ∈ A if fi ∈ C vi ∈ A if fi ∈ C. This is exactly the unnormalized spectral clustering algorithm for the case of k = 2. 5.2 Approximating RatioCut for arbitrary k The relaxation of the RatioCut minimization problem in the case of a general value k follows a similar principle as the one above. Given a partition of V into k sets A1, . . . , Ak, we define k indicator vectors hj = (h1,j , . . . , hn,j ) 0 by hi,j = ( 1/ p |Aj | if vi ∈ Aj 0 otherwise (i = 1, . . . , n; j = 1, . . . , k). (5) Then we set the matrix H ∈ ❘ n×k as the matrix containing those k indicator vectors as columns. Observe that the columns in H are orthonormal to each other, that is H0H = I. Similar to the calculations in the last section we can see that h 0 iLhi = cut(Ai , Ai) |Ai | . Moreover, one can check that h 0 iLhi = (H0LH)ii. Combining those facts we get RatioCut(A1, . . . , Ak) = X k i=1 h 0 iLhi = X k i=1 (H0LH)ii = Tr(H0LH), 11