Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering

arXiv2206.05553MaRDI QIDQ6401776

Author name not available (Why is that?)

Publication date: 11 June 2022

Abstract: The K-subspaces (KSS) method is a generalization of the K-means method for subspace clustering. In this work, we present local convergence analysis and a recovery guarantee for KSS, assuming data are generated by the semi-random union of subspaces model, where $N$ points are randomly sampled from $Kge2$ overlapping subspaces. We show that if the initial assignment of the KSS method lies within a neighborhood of a true clustering, it converges at a superlinear rate and finds the correct clustering within $Theta(loglogN)$ iterations with high probability. Moreover, we propose a thresholding inner-product based spectral method for initialization and prove that it produces a point in this neighborhood. We also present numerical results of the studied method to support our theoretical developments.

Has companion code repository: https://github.com/peng8wang/icml2022-k-subspaces

This page was built for publication: Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering

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