# Finding a sparse vector in a subspace: Linear sparsity using alternating directions

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2014.

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

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifold](https://mlsanity.com/paper/2209.09211/) (2022)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation](https://mlsanity.com/paper/2110.00053/) (2021)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Unique sparse decomposition of low rank matrices](https://mlsanity.com/paper/2106.07736/) (2021)
- [Lifelong Matrix Completion with Sparsity-Number](https://mlsanity.com/paper/2203.07637/) (2022)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [A Riemannian ADMM](https://mlsanity.com/paper/2211.02163/) (2022)
- [SQ Lower Bounds for Random Sparse Planted Vector Problem](https://mlsanity.com/paper/2301.11124/) (2023)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [Linearly Separable Features in Shallow Nonlinear Networks: Width Scales Polynomially with Intrinsic Data Dimension](https://mlsanity.com/paper/2501.02364/) (2025)
- [A Riemannian smoothing steepest descent method for non-Lipschitz optimization on submanifolds](https://mlsanity.com/paper/2104.04199/) (2021)
- [Unsupervised Congestion Status Identification Using LMP Data](https://mlsanity.com/paper/2411.10058/) (2024)
- [A Quantum Tensor Network-Based Viewpoint for Modeling and Analysis of Time Series Data](https://mlsanity.com/paper/2511.13514/) (2025)
- [Boosting RANSAC via Dual Principal Component Pursuit](https://mlsanity.com/paper/2110.02918/) (2021)
- [Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit](https://mlsanity.com/paper/2502.02668/) (2025)

## Abstract (arXiv)

Is it possible to find the sparsest vector (direction) in a generic subspace S subseteq ℝp with dim(S)= n < p? This problem can be considered a homogeneous variant of the sparse recovery problem, and finds connections to sparse dictionary learning, sparse PCA, and many other problems in signal processing and machine learning. In this paper, we focus on a **planted sparse model** for the subspace: the target sparse vector is embedded in an otherwise random subspace. Simple convex heuristics for this planted recovery problem provably break down when the fraction of nonzero entries in the target sparse vector substantially exceeds O(1/√n). In contrast, we exhibit a relatively simple nonconvex approach based on alternating directions, which provably succeeds even when the fraction of nonzero entries is Omega(1). To the best of our knowledge, this is the first practical algorithm to achieve linear scaling under the planted sparse model. Empirically, our proposed algorithm also succeeds in more challenging data models, e.g., sparse dictionary learning.