A basic problem in spectral clustering is the following. If a solution obtained from the spectral relaxation is close to an integral solution, is it possible to find this integral solution even though they might be in completely different basis? In this paper, we propose a new spectral clustering algorithm. It can recover a @math -partition such that the subspace corresponding to the span of its indicator vectors is @math close to the original subspace in spectral norm with @math being the minimum possible ( @math always). Moreover our algorithm does not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a @math -partition closer than @math . We present two applications for our algorithm. First one finds a disjoint union of bounded degree expanders which approximate a given graph in spectral norm. The second one is for approximating the sparsest @math -partition in a graph where each cluster have expansion at most @math provided @math where @math is the @math eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required @math .
Perhaps the simplest case of is when there is a gap between the @math smallest eigenvalue of Laplacian matrix, @math , and @math of the form ( k+1 1 . ) One might think of this as a stability criteria: It implies that all @math -partitions with maximum expansion @math are @math -close to each other. To put it in another way, approximating the optimum @math -partition is at least as easy as finding a @math -partition with minimum possible expansion among all its clusters. For the case of @math , it is trivial to show that thresholding the second smallest eigenvector of Laplacian yields @math -close partition to the optimal one. On the other hand, when @math , the best prior result is due to @cite_6 , which can find a @math -partition that is @math -close to the optimal one. In other words, when @math , there is no algorithm known to find a non-trivial approximation of the optimum @math -partition.
@cite_6
2950342785
We describe a new approximation algorithm for Max Cut. Our algorithm runs in @math time, where @math is the number of vertices, and achieves an approximation ratio of @math . In instances in which an optimal solution cuts a @math fraction of edges, our algorithm finds a solution that cuts a @math fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a @math fraction of edges, our spectral partitioning algorithm finds a set @math of vertices and a bipartition @math of @math such that at least a @math fraction of the edges incident on @math have one endpoint in @math and one endpoint in @math . (This can be seen as an analogue of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, var...