Finding a Sparse Vector in a Subspace: Linear Sparsity Using Alternating Directions

Qing Qu, Ju Sun, John Wright

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Is it possible to find the sparsest vector (direction) in a generic subspace S ⊆ Rp with dim =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 ω (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.

Original languageEnglish (US)
Article number7547961
Pages (from-to)5855-5880
Number of pages26
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Oct 2016
Externally publishedYes


  • Alternating direction method
  • Sparse vector
  • dictionary learning
  • homogeneous recovery
  • nonconvex optimization
  • sparse recovery
  • subspace modeling


Dive into the research topics of 'Finding a Sparse Vector in a Subspace: Linear Sparsity Using Alternating Directions'. Together they form a unique fingerprint.

Cite this