# Greedy Feature Selection for Subspace Clustering

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2013.

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

- [Learning a Self-Expressive Network for Subspace Clustering](https://mlsanity.com/paper/2110.04318/) (2021)
- [Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering](https://mlsanity.com/paper/2206.05553/) (2022)
- [Avengers Ensemble! Improving Transferability of Authorship Obfuscation](https://mlsanity.com/paper/2109.07028/) (2021)
- [Detecting adversaries in Crowdsourcing](https://mlsanity.com/paper/2110.04117/) (2021)
- [PMSSC: Parallelizable multi-subset based self-expressive model for subspace clustering](https://mlsanity.com/paper/2111.12232/) (2021)
- [Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering](https://mlsanity.com/paper/2204.02572/) (2022)
- [Contrastive Learning Subspace for Text Clustering](https://mlsanity.com/paper/2408.14119/) (2024)
- [Neural Ordinary Differential Equation Model for Evolutionary Subspace Clustering and Its Applications](https://mlsanity.com/paper/2107.10484/) (2021)
- [Provable Clustering of a Union of Linear Manifolds Using Optimal Directions](https://mlsanity.com/paper/2201.02745/) (2022)
- [Noisy ℓ0-Sparse Subspace Clustering on Dimensionality Reduced Data](https://mlsanity.com/paper/2206.11079/) (2022)
- [Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees](https://mlsanity.com/paper/2311.01806/) (2023)

## Abstract (arXiv)

Unions of subspaces provide a powerful generalization to linear subspace models for collections of high-dimensional data. To learn a union of subspaces from a collection of data, sets of signals in the collection that belong to the same subspace must be identified in order to obtain accurate estimates of the subspace structures present in the data. Recently, sparse recovery methods have been shown to provide a provable and robust strategy for exact feature selection (EFS)--recovering subsets of points from the ensemble that live in the same subspace. In parallel with recent studies of EFS with L1-minimization, in this paper, we develop sufficient conditions for EFS with a greedy method for sparse signal recovery known as orthogonal matching pursuit (OMP). Following our analysis, we provide an empirical study of feature selection strategies for signals living on unions of subspaces and characterize the gap between sparse recovery methods and nearest neighbor (NN)-based approaches. In particular, we demonstrate that sparse recovery methods provide significant advantages over NN methods and the gap between the two approaches is particularly pronounced when the sampling of subspaces in the dataset is sparse. Our results suggest that OMP may be employed to reliably recover exact feature sets in a number of regimes where NN approaches fail to reveal the subspace membership of points in the ensemble.