2015/03/03 by Ali Kemal Sinop, Sinop, Ali Kemal
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Graph theory and applications #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1503.00827
openalex publication_date 2015/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 k-partition such that the subspace corresponding to the span of its indicator vectors is O(√(opt)) close to the original subspace in spectral norm with opt being the minimum possible (opt ≤ 1 always). Moreover our algorithm does not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a k-partition closer than o(k ⋅ opt). 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 k-partition in a graph where each cluster have expansion at most ϕk provided ϕk ≤ O(λk+1) where λk+1 is the (k+1)st eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required ϕk ≤ O(λk+1/k).