# Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering

arXiv: https://arxiv.org/abs/2204.02572 · HTML: https://mlsanity.com/paper/2204.02572/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 48 references that are in the map.
- First posted on arXiv 6 Apr 2022.

## Builds on (most cited first, 12 of 12)

- [Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit](https://mlsanity.com/paper/1507.01238/) (2015)
- [Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering](https://mlsanity.com/paper/1605.02633/) (2016)
- [Subspace Clustering by Block Diagonal Representation](https://mlsanity.com/paper/1805.09243/) (2018)
- [Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework](https://mlsanity.com/paper/1610.05211/) (2016)
- [Robust subspace clustering](https://mlsanity.com/paper/1301.2603/) (2013)
- [Noisy Sparse Subspace Clustering](https://mlsanity.com/paper/1309.1233/) (2013)
- [Robust Subspace Clustering via Thresholding](https://mlsanity.com/paper/1307.4891/) (2013)
- [Greedy Feature Selection for Subspace Clustering](https://mlsanity.com/paper/1303.4778/) (2013)
- [Noisy subspace clustering via matching pursuits](https://mlsanity.com/paper/1612.03450/) (2016)
- [A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data](https://mlsanity.com/paper/1610.07650/) (2016)
- [Active Orthogonal Matching Pursuit for Sparse Subspace Clustering](https://mlsanity.com/paper/1708.04764/) (2017)
- [Restricted Connection Orthogonal Matching Pursuit For Sparse Subspace Clustering](https://mlsanity.com/paper/1905.00420/) (2019)

## Built on by (most cited first, 1 of 1)

- [A Geometric View of SRC: Learning Representations for Stable Residual Inference](https://mlsanity.com/paper/2605.29673/) (2026)

## Abstract (arXiv)

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 popular L1-minimization based methods. This paper proposes a new SSC scheme using generalized OMP (GOMP), a soup-up of OMP whereby multiple neighbors are identified per iteration, along with a new stopping rule requiring nothing more than a knowledge of the ambient signal dimension. Compared to conventional OMP, which identifies one neighbor per iteration, the proposed GOMP method involves fewer iterations, thereby enjoying lower algorithmic complexity; advantageously, the proposed stopping rule is free from off-line estimation of subspace dimension and noise power. Under the semi-random model, analytic performance guarantees, in terms of neighbor recovery rates, are established to justify the advantage of the proposed GOMP. The results show that, with a high probability, GOMP (i) is halted by the proposed stopping rule, and (ii) can retrieve more true neighbors than OMP, consequently yielding higher final data clustering accuracy. Computer simulations using both synthetic data and real human face data are provided to validate our analytic study and evidence the effectiveness of the proposed approach.