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

In this work, we present local convergence analysis and a recovery guarantee for KSS, assuming In the UoS model, the goal of SC is to recover the data are generated by the semi-random underlying subspaces and cluster the unlabeled data union of subspaces model, where N points are points into the corresponding subspaces. To achieve randomly sampled from K 2 overlapping this goal, many algorithms have been proposed in subspaces. We show that if the initial assignment the past two decades, such as sparse subspace clustering of the KSS method lies within a neighborhood methods (Elhamifar & Vidal, 2013; Wang & Xu, of a true clustering, it converges at a 2013), low-rank representation-based methods (Liu et al., superlinear rate and finds the correct clustering 2012), thresholding-based methods (Heckel & Bölcskei, within Θ(loglogN) iterations with high probability.