PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Qing Qu, Ju Sun, John Wright

arXiv:1412.4659v3cs.ITcs.CVcs.LGmath.ITmath.OCstat.ML

TL;DR

Can a sparse vector be efficiently recovered from a subspace beyond the sparsity range where convex relaxations for the planted model break down? The paper uses alternating directions followed by linear-programming rounding. It reports a linear-sparsity guarantee and empirical success on synthetic and complete dictionary-learning models.

  • Problem

    Whether sparse vectors can be efficiently recovered from a planted subspace beyond the O(1/√n) convex-relaxation threshold remains an open question.

    Source: B. Prior Arts · p. 3

  • Method

    An alternating-directions method moves toward a sparse optimum, followed by linear-programming rounding to recover the exact sparse vector.

    Source: §I · p. 1, §III · p. 6

  • Results

    The algorithm guarantees recovery for θ = Ω(1), empirically succeeds for p ≥ Ω(n polylog(n)), and also performs well on complete dictionary learning.

    Source: C. Contributions and Recent Developments · p. 3

  • Takeaways & Limitations

    The authors report that the algorithm is practical for large datasets and extracted meaningful features from face images.

    Source: §VI · p. 13

    The paper reports a substantial gap between its optimality theorem, empirical simulations, and guarantees obtained by its efficient algorithm.

    Source: §VI · p. 12

Abstract

from arXiv · show

Is it possible to find the sparsest vector (direction) in a generic subspace $\mathcal{S} \subseteq \mathbb{R}^p$ with $\mathrm{dim}(\mathcal{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/\sqrt{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.

I. INTRODUCTION

The paper asks whether a sparse vector can be efficiently recovered from a subspace, focusing on a planted model where the target is embedded in an otherwise random subspace. It connects this problem to dictionary learning and sparse PCA, reviews limits of convex methods, and presents an alternating-directions approach with linear-sparsity guarantees and empirical results.

I. INTRODUCTION

  • The problem is to efficiently recover a nonzero sparse vector from a subspace, equivalently to find a nonzero sparse x satisfying Ax = 0.The paper studies this problem under a planted model in which the target sparse vector is embedded in an otherwise random subspace.Source: §I · p. 1

A. Motivation

  • Complete dictionary learning reduces to finding sparse directions in a known data row space, while sparse PCA seeks a sparse basis for a subspace in the data-poor regime.The paper also lists applications of related problem variants in control, structure from motion, spectral estimation, and other areas.Source: A. Motivation · p. 2

B. Prior Arts

  • Convex relaxations for the planted model provably break down when the target’s nonzero fraction substantially exceeds O(1/√n), motivating the search for efficient methods beyond that threshold.The paper frames whether this threshold is the best achievable by efficient guaranteed algorithms as an open question.Source: B. Prior Arts · pp. 2–3

C. Contributions and Recent Developments

  • The proposed alternating-directions algorithm uses data-driven initialization and LP rounding, with simple iterations of linear complexity in the data size.The paper allows the planted vector to have a constant fraction of nonzeros and reports empirical success at p ≥ Ω(n polylog(n)), including complete dictionary learning.Source: C. Contributions and Recent Developments · p. 3

D. Paper Organization, Notations and Reproducible Research

The paper formulates sparse-vector recovery in a subspace as an ℓ1 objective over unit-norm basis coefficients, then develops an alternating-direction method with data-driven initialization and LP rounding. Under the planted sparse model, the approach is designed to recover vectors with linear sparsity; the paper also outlines its organization and notation.

D. Paper Organization, Notations and Reproducible Research

  • The paper presents its formulation, algorithm, theoretical results, and experiments across Sections II–V, with full proofs deferred to the appendices.Its notation defines local constants and uses “with high probability” for failure probability dominated by p^-κ; reproduction codes are available online.Source: D. Paper Organization, Notations and… · pp. 3–4

II. PROBLEM FORMULATION AND GLOBAL OPTIMALITY

  • Theorem II.1 gives exact recovery under the planted sparse model when 1/√n < θ < θ0 and p ≥ Cn, with probability at least 1 − cp^-2.The unique optimizer of the ℓ1 objective over unit-norm coefficients recovers x0 up to scale.Source: §II · p. 4

III. ALGORITHM BASED ON ALTERNATING DIRECTION METHOD (ADM)

  • The proposed algorithm uses normalized rows of Y as initializations, alternates updates of x and q, and applies LP rounding to recover the exact optimizer.The alternating updates are enabled by a relaxation with auxiliary x ≈ Yq; the paper notes that arbitrary or random initialization may fail in the linear-sparsity regime.Source: §III · pp. 5–6

IV. MAIN RESULTS AND SKETCH OF ANALYSIS

The paper analyzes an alternating-direction algorithm with row-based initializations and LP rounding for the planted sparse model. It reports high-probability recovery and frames the method as a practical, efficient guarantee at linear sparsity, while noting a sample-complexity gap against other results.

A. Main Results

  • The theorem’s sample complexity is described as suboptimal relative to the global-optimality result and Barak et al.’s result.Source: A. Main Results · p. 6
  • The authors characterize the method as the first practical, efficient approach guaranteed to achieve θ ∼ Ω(1), while LP rounding alone succeeds w.h.p. for θ ∈ O(1/√n).Source: A. Main Results · p. 6

B. A Sketch of Analysis

The proof sketch establishes that a data-driven initializer can guide ADM toward the planted solution, after which LP rounding recovers it exactly. The argument bounds the iterations needed to reach a rounding-safe region, but the authors note that their theory does not prove the convergence observed in practice.

B. A Sketch of Analysis

  • For p ≥ Cn^4 log n, ADM reaches the safe region within O(n^4 log n) iterations with probability at least 1 − cp^-2, provided θ ∈ (1/√n, θ0), where θ0 ∈ (0, 1) and C, c are positive constants.Source: B. A Sketch of Analysis · p. 8
  • When the ADM output has a sufficiently large first coordinate, LP rounding returns the target solution exactly with high probability.The sufficient condition is |q1| > 2θ, for θ ∈ (1/√n, θ0), under the stated sample-size condition.Source: B. A Sketch of Analysis · p. 8
  • At least one normalized row of the basis provides a suitable initialization with high probability.The proof then tracks progress from this initializer toward the target direction.Source: B. A Sketch of Analysis · p. 9
  • ADM makes uniform progress toward the target and, once inside a spherical cap, its iterates remain near the optimum.The proof sketch attributes these stages to uniform progress away from the equator and no jumps away from the caps.Source: B. A Sketch of Analysis · p. 9
  • Combining initialization, ADM, and rounding recovers x0 up to scale, and the minimum-ℓ1 selector identifies it among the row initializers.The proof uses the uniqueness of ±x0 as minimum-ℓ1 unit vectors in the subspace.Source: B. A Sketch of Analysis · p. 9
  • The theory does not prove the practical convergence observed for ADM, so LP rounding is included to complete the guarantee.The authors describe rounding as seemingly unnecessary in practice and as an artifact of the current analysis.Source: B. A Sketch of Analysis · p. 10

V. EXPERIMENTAL RESULTS

The experiments assess ADM on synthetic planted-sparse and dictionary-learning models, and on real face images. They examine recovery transitions in simulation and whether sparse-vector search reveals patterns in face data.

V. EXPERIMENTAL RESULTS

  • The experiments evaluate ADM on synthetic data and real datasets.The synthetic evaluations cover planted-sparse and dictionary-learning models; the real-data demonstration uses face images.Source: §V · p. 10
  • Synthetic experiments map phase transitions for both the planted-sparse and dictionary-learning models.The section describes these as evaluations of the algorithm's performance.Source: §V · p. 10
  • The real-data experiment demonstrates how sparse-vector search can help discover patterns in face images.Source: §V · p. 10

A. Phase Transition on Synthetic Data

Synthetic experiments test ADM on planted-sparse and complete dictionary-learning models using phase-transition plots. The reported results show empirical operation in the linear-sparsity regime, while the planted-model theoretical sample requirement remains substantially higher than the empirical one.

A. Phase Transition on Synthetic Data

  • The planted-sparse simulations use a k-sparse target with random support and unit nonzero entries, combined with an iid Gaussian subspace.The experiments initialize ADM with all normalized basis rows and repeat each parameter pair ten times.Source: A. Phase Transition on Synthetic Data · p. 10
  • Complete dictionary-learning simulations generate sparse coefficient rows with Gaussian nonzero entries and count recovery when any row is recovered.The experiments repeat the planted-model procedure, with this changed success criterion.Source: A. Phase Transition on Synthetic Data · p. 10
  • Both models empirically reach linear sparsity when p is on the order of n log n.The phase-transition plots indicate that the log n factor appears necessary in the tested settings; O(n log n) is described as near optimal for both models.Source: A. Phase Transition on Synthetic Data · p. 10, Figure 2 · p. 11, Figure 3 · p. 11
  • The planted-model empirical sample requirement is much lower than the theorem's p ≥ Ω(n^4 log n) requirement.The authors state that the empirical requirement is far below their theoretical bound.Source: A. Phase Transition on Synthetic Data · pp. 10–11

B. Exploratory Experiments on Faces

The face experiments apply ADM to illumination and multi-person face subspaces, while the discussion notes a gap between the planted-model theory, empirical behavior, and algorithmic guarantees. The authors frame sparse-vector search as practical on realistic data and identify a broader, still underexplored application space.

B. Exploratory Experiments on Faces

  • The spectral method with LP post-processing produced vectors with higher sparsity by the stated ℓ1/ℓ2 and ℓ4/ℓ2 criteria, but its resulting images were harder to interpret physically.For the one-person, varying-illumination experiment, ADM vectors corresponded well to different extreme illumination conditions.Source: B. Exploratory Experiments on Faces · pp. 11–12
  • For ten people under normal lighting, ADM vectors roughly captured differences concentrated around facial parts, while spectral-method vectors were denser and less physically structured.The compared patterns included differences around eyebrows, forehead hair, and noses.Source: B. Exploratory Experiments on Faces · p. 12, Figure 5 · p. 13
  • The face experiments suggest potential uses in peculiarity discovery and locating differences, and demonstrate practical operation on realistic-sized data beyond the analyzed planted model.The authors characterize these uses as potential and say the vectors seem useful.Source: B. Exploratory Experiments on Faces · p. 12

VI. CONNECTIONS AND DISCUSSION

  • For the planted sparse model, the p-n performance gap between the optimality theorem, empirical simulations, and efficient-algorithm guarantees remains substantial.The authors suggest tighter analysis may narrow the theory–empirical gap, while matching the theoretical limit may require new algorithmic ideas.Source: §VI · p. 12
  • The discussion proposes combining problem-specific initialization with geometric analysis as a potentially powerful framework for the planted sparse-vector problem.With initialization biased toward either pole, the described asymptotic Huber-loss landscape has nonzero gradients pointing toward favorable directions.Source: §VI · p. 13
  • The authors present their algorithm as efficient, strongly guaranteed, and practical for large datasets, while describing sparse or structured subspace elements as an underexplored area.They hope the work will inspire additional application ideas.Source: §VI · p. 13

APPENDIX A TECHNICAL TOOLS AND PRELIMINARIES

The appendices collect technical lemmas and use Gaussian-matrix and concentration results in analyses of the planted basis and its orthonormalized version. The supplied proof fragments state conditioning and probability bounds under specified parameter conditions.

APPENDIX A TECHNICAL TOOLS AND PRELIMINARIES

  • Appendix A records technical tools used in the analysis, including concentration, covering-number, Gaussian-matrix spectrum, and moment inequalities.The listed tools include Gaussian concentration and moment-control Bernstein inequalities.Source: Appendix A · pp. 14–16

APPENDIX B THE RANDOM BASIS VS. ITS ORTHONORMALIZED VERSION

  • Appendix B studies the planted random basis and its orthonormalized version, with the stated aim of making their large-p similarity rigorous.The text says the results support the proof of Theorem II.1 and translation of results between the two bases.Source: Appendix B · p. 17, §0 · p. 17

0 G is well-conditioned (proved in Lemma B.2). We write

  • The well-conditioning analysis gives simultaneous bounds with probability at least 1 − cp^-2 under conditions including p ≥ Cn and θ > 1/√n.The supplied lemma fragment states the result for constants C and c greater than zero.Source: §0 · pp. 19–20

APPENDIX C PROOF OF ℓ1/ℓ2 GLOBAL OPTIMALITY

The proof analyzes a canonical ℓ1 minimization over the unit sphere and establishes the planted directions as its unique global minimizers under stated conditions. It then extends the result to arbitrary orthonormal input bases by a change of variables.

APPENDIX C PROOF OF ℓ1/ℓ2 GLOBAL OPTIMALITY

  • The canonical program minimizes ∥Yq∥1 subject to ∥q∥2 = 1, and the proof analyzes this formulation first.The appendix identifies Y as the canonical orthonormal basis used in the analysis.Source: Appendix C · p. 21
  • For 1/√n ≤ θ ≤ θ0 with θ0 sufficiently small, ±e1 are the only global minimizers under the spherical constraint for input basis Y.The proof states that the corresponding minimizers of the canonical objective are unique.Source: Appendix C · p. 22
  • An arbitrary orthonormal basis bY = YU yields an equivalent program after the change of variable q := Uq.The proof uses this equivalence to extend the canonical-basis result.Source: Appendix C · p. 22

APPENDIX D GOOD INITIALIZATION

The appendices support the algorithm’s initialization analysis and finite-sample gap argument. They state that the initialization is biased toward the target and that the gap is positive over a large portion of the sphere under the relevant technical conditions.

APPENDIX D GOOD INITIALIZATION

  • The initialization analysis states that the procedure described in Section III produces initializations biased toward the optimal solution.The proof fragment also states a high-probability existence result for a row-based initialization under conditions including p ≥ Cn and θ > 1/√n.Source: Appendix D · pp. 22–23

APPENDIX E LOWER BOUNDING FINITE SAMPLE GAP G(q)

  • The finite-sample analysis aims to lower-bound G(q) and states that this gap is strictly positive over a large portion of the sphere.The appendix concludes that its proposition applies under the same technical conditions stated there.Source: Appendix E · pp. 23, 25
  • The gap analysis identifies bounding |Q1(q)| below and ∥Q2(q)∥2 above as its main challenge, and notes that the unnormalized basis Y is easier to analyze.The stated challenge concerns terms that depend on the orthonormal basis.Source: Appendix E · p. 24

A. Lower Bounding the Expected Gap G(q)

The appendix derives a lower bound on the expected gap G(q) using expectation estimates and auxiliary inequalities, then outlines finite-sample concentration and uniformization.

A. Lower Bounding the Expected Gap G(q)

1) Sketch of the Proof:

2) Auxiliary Results Used in the Proof: √

B. Finite Sample Concentration

1) Concentration for Q1(q):

The appendix turns pointwise concentration bounds into uniform guarantees and shows that Q(q) approximates its population counterpart under specified scaling conditions.

1) Concentration for Q1(q):

2) Concentration for Q2(q):

C. Union Bound

  • For θ > 1/√n and p ≥ C(ξ)n^4 log n, the bounds hold uniformly with probability at least 1 − c(ξ)p^-2.Source: C. Union Bound · pp. 30–31

D. Q(q) approximates Q(q)

  • For θ > 1/√n and p ≥ C(ξ)n^4 log n, the stated bounds hold with probability at least 1 − c(ξ)p^-2, for a positive constant c(ξ).Source: D. Q(q) approximates Q(q) · p. 32

APPENDIX F LARGE |q1| ITERATES STAYING IN SAFE REGION FOR ROUNDING

The appendix analyzes the safe region for rounding, bounds iteration complexity, and proves that the rounding procedure recovers the desired solution under stated conditions.

APPENDIX F LARGE |q1| ITERATES STAYING IN SAFE REGION FOR ROUNDING

  • When θ is sufficiently small, the safe-region argument shows with high probability that sufficiently close iterates satisfy the condition needed for rounding.Source: Appendix F · pp. 33–34

APPENDIX G BOUNDING ITERATION COMPLEXITY

  • The iteration argument gives a bound of C5 n^4 log n steps under its stated small-θ assumptions.Source: Appendix G · p. 35

APPENDIX H ROUNDING TO THE DESIRED SOLUTION

  • For θ ≤ θ0 and p ≥ C3(θ0)n, the rounding returns e1/q1; the analysis also states recovery holds regardless of the orthonormal basis.Source: Appendix H · pp. 35–36

Related papers

Loading 1412.4659v3…