Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering
Abstract: Sparse subspace clustering (SSC) using greedy-based neighbor selection, such as orthogonal matching pursuit (OMP), has been known as a popular computationally-efficient alternative to the standard $\ell_1$-minimization based methods. However, existing stopping rules of OMP to halt neighbor search needs additional offline work to estimate some ground truths, e.g., subspace dimension and/or noise strength. This paper proposes a new SSC scheme using generalized OMP (GOMP), a soup-up of OMP whereby multiple, say $p(\geq1)$, neighbors are identified per iteration to further speed up neighbor acquisition, along with a new stopping rule requiring nothing more than a knowledge of the ambient signal dimension and the number $p$ of identified neighbors in each iteration. Compared to conventional OMP (i.e., $p=1$), the proposed GOMP method involves fewer iterations, thereby enjoying lower algorithmic complexity. Under the semi-random model, analytic performance guarantees are provided. It is shown that, with a high probability, (i) GOMP can retrieve more true neighbors than OMP, consequently yielding higher data clustering accuracy, and (ii) the proposed stopping rule terminates neighbor search once the number of recovered neighbors is close to the subspace dimension. Issues about selecting $p$ for practical implementation are also discussed. Computer simulations using both synthetic and real data are provided to demonstrate the effectiveness of the proposed approach and validate our analytic study.
Submission Length: Long submission (more than 12 pages of main content)
Changes Since Last Submission: This is the final version.
Assigned Action Editor: ~Stephen_Becker1
License: Creative Commons Attribution 4.0 International (CC BY 4.0)
Submission Number: 989
Loading