Timezone: »

Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering
Peng Wang · Huikang Liu · Anthony Man-Cho So · Laura Balzano

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #611
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 $K \ge 2$ 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(\log\log N)$ 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.

Author Information

Peng Wang (University of Michigan)
Huikang Liu (Imperial College London)
Anthony Man-Cho So (The Chinese University of Hong Kong)
Laura Balzano (University of Michigan)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors