The Library
Provable subspace clustering : when LRR meets SSC
Tools
Wang, Yu-Xiang, Xu, Huan and Leng, Chenlei (2019) Provable subspace clustering : when LRR meets SSC. IEEE Transaction on Information Theory, 65 (9). pp. 5406-5432. doi:10.1109/TIT.2019.2915593 ISSN 0018-9448.
|
PDF
WRAP-provable-subspace-clustering-LRR-SSC-Leng-2019.pdf - Accepted Version - Requires a PDF viewer. Download (1444Kb) | Preview |
Official URL: https://doi.org/10.1109/TIT.2019.2915593
Abstract
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 SSC minimizes thevector`1norm 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 anew algorithm, termed Low-Rank Sparse Subspace Clustering (LRSSC), by combining SSC and LRR, and develop theoretical guarantees of the success of the algorithm. The results reveal interesting insights into the strengths and weaknesses of SSC and LRR, and demonstrate how 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”.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | ||||||||
Library of Congress Subject Headings (LCSH): | Big data, Graph connectivity | ||||||||
Journal or Publication Title: | IEEE Transaction on Information Theory | ||||||||
Publisher: | IEEE | ||||||||
ISSN: | 0018-9448 | ||||||||
Official Date: | September 2019 | ||||||||
Dates: |
|
||||||||
Volume: | 65 | ||||||||
Number: | 9 | ||||||||
Page Range: | pp. 5406-5432 | ||||||||
DOI: | 10.1109/TIT.2019.2915593 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 6 June 2019 | ||||||||
Date of first compliant Open Access: | 11 June 2019 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year