How to Round Subspaces: A New Spectral Clustering Algorithm

DOI10.1137/1.9781611974331.CH128zbMATH Open1412.62086arXiv1503.00827OpenAlexW1842953391MaRDI QIDQ4575712FDOQ4575712

Authors: Ali Kemal Sinop 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: 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(sqrtopt)$ close to the original subspace in spectral norm with $opt$ being the minimum possible ($optle1$ 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(kcdotopt)$. 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 $ph{i}_k$ provided $ph{i}_{k}leO(lambd{a}_{k+1})$ where $lambd{a}_{k+1}$ is the $(k+1{)}^{st}$ eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required $ph{i}_{k}leO(lambd{a}_{k+1}/k)$.

Full work available at URL: https://arxiv.org/abs/1503.00827

Recommendations

• A robust subspace clustering algorithm
• Subspace clustering through sub-clusters
• Robust subspace clustering
• A subspace clustering algorithm based on simultaneously sparse and low-rank representation
• A survey on enhanced subspace clustering
• Clustering affine subspaces: hardness and algorithms

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Cited In (3)

• Spectral concentration and greedy \(k\)-clustering
• Convex programming based spectral clustering
• Spectral embedding of \(k\)-cliques, graph partitioning and \(k\)-means

This page was built for publication: How to Round Subspaces: A New Spectral Clustering Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575712)