# Noisy ℓ0-Sparse Subspace Clustering on Dimensionality Reduced Data

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 62 references that are in the map.
- First posted on arXiv 22 Jun 2022.

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

- [Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit](https://mlsanity.com/paper/1507.01238/) (2015)
- [Experiments with Random Projection](https://mlsanity.com/paper/1301.3849/) (2013)
- [Noisy Sparse Subspace Clustering](https://mlsanity.com/paper/1309.1233/) (2013)
- [On Geometric Analysis of Affine Sparse Subspace Clustering](https://mlsanity.com/paper/1808.05965/) (2018)
- [Greedy Feature Selection for Subspace Clustering](https://mlsanity.com/paper/1303.4778/) (2013)
- [Greedy Subspace Clustering](https://mlsanity.com/paper/1410.8864/) (2014)
- [Is an Affine Constraint Needed for Affine Subspace Clustering?](https://mlsanity.com/paper/2005.03888/) (2020)
- [Sign-Full Random Projections](https://mlsanity.com/paper/1805.00533/) (2018)
- [GCWSNet: Generalized Consistent Weighted Sampling for Scalable and Accurate Training of Neural Networks](https://mlsanity.com/paper/2201.02283/) (2022)
- [Recovery of Coherent Data via Low-Rank Dictionary Pursuit](https://mlsanity.com/paper/1404.4032/) (2014)
- [Binary and Multi-Bit Coding for Stable Random Projections](https://mlsanity.com/paper/1503.06876/) (2015)
- [On the Suboptimality of Proximal Gradient Descent for ℓ0 Sparse Approximation](https://mlsanity.com/paper/1709.01230/) (2017)

## Abstract (arXiv)

Sparse subspace clustering methods with sparsity induced by ℓ0-norm, such as ℓ0-Sparse Subspace Clustering (ℓ0-SSC)~citepYangFJYH16-L0SSC-ijcv, are demonstrated to be more effective than its ℓ1 counterpart such as Sparse Subspace Clustering (SSC)~citepElhamifarV13. However, the theoretical analysis of ℓ0-SSC is restricted to clean data that lie exactly in subspaces. Real data often suffer from noise and they may lie close to subspaces. In this paper, we show that an optimal solution to the optimization problem of noisy ℓ0-SSC achieves subspace detection property (SDP), a key element with which data from different subspaces are separated, under deterministic and semi-random model. Our results provide theoretical guarantee on the correctness of noisy ℓ0-SSC in terms of SDP on noisy data for the first time, which reveals the advantage of noisy ℓ0-SSC in terms of much less restrictive condition on subspace affinity. In order to improve the efficiency of noisy ℓ0-SSC, we propose Noisy-DR-ℓ0-SSC which provably recovers the subspaces on dimensionality reduced data. Noisy-DR-ℓ0-SSC first projects the data onto a lower dimensional space by random projection, then performs noisy ℓ0-SSC on the projected data for improved efficiency. Experimental results demonstrate the effectiveness of Noisy-DR-ℓ0-SSC.