Provable Subspace Clustering: When LRR Meets SSC

• Published in: IEEE transactions on information theory 2019-09, Vol.65 (9), p.5406-5432
• Main Authors: Wang, Yu-Xiang, Xu, Huan, Leng, Chenlei
• Format: Article
• Language: English
• Subjects: Algorithms; Clustering; Clustering algorithms; Computational geometry; Computer vision; Convexity; graph connectivity; Matching pursuit algorithms; Mathematical analysis; Matrix methods; Motion segmentation; Noise measurement; Optimization; Representations; Sparse matrices; Subspace clustering; Subspaces; Task analysis
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2019.2915593

An important problem in analyzing big data is subspace clustering , i.e., to represent a collection of points in a high-dimensional space via the union of low-dimensional subspaces. Sparse subspace clustering (SSC) and Low-rank representation (LRR) are the state-of-the-art methods for this task. These two methods are fundamentally similar in that both are based on convex optimization exploiting the intuition of "Self-Expressiveness". The main difference is that the SSC minimizes the vector \ell _{1} norm of the representation matrix to induce sparsity while LRR minimizes the nuclear norm (aka trace norm) to promote a low-rank structure. Because the representation matrix is often simultaneously sparse and low-rank, we propose a new algorithm, termed Low-rank sparse subspace clustering (LRSSC), by the combining SSC and LRR, and develop theoretical guarantees of the success of the algorithm. The results reveal interesting insights into the strengths and the weaknesses of SSC and LRR, and demonstrate how the LRSSC can take advantage of both methods in preserving the "Self-Expressiveness Property" and "Graph Connectivity" at the same time. A byproduct of our analysis is that it also expands the theoretical guarantee of SSC to handle cases when the subspaces have arbitrarily small canonical angles but are "nearly independent".