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

DOI10.1109/TIT.2016.2601599MaRDI QIDQ2976591zbMATH OpenOpenAlexFDO

Authors

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.4659

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Is it possible to find the sparsest vector (direction) in a generic subspace $mathcalSsubseteqmathbb{R}^p$ with $mathrmdim(mathcalS)=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/sqrtn)$. 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.

Cited in

(16)

• A geometric analysis of phase retrieval
• Line search algorithms for locally Lipschitz functions on Riemannian manifolds
• Robust data-driven discovery of governing physical laws with error bars
• Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods
• Stochastic proximal gradient method FOR _1 regularized optimization over a sphere
• Finding a low-rank basis in a matrix subspace
• An active-set proximal quasi-Newton algorithm for ℓ₁-regularized minimization over a sphere constraint
• Completely positive factorization by a Riemannian smoothing method
• Seq-SVF: an unsupervised data-driven method for automatically identifying hidden governing equations
• On sparse approximations of solutions to linear systems with orthogonal matrices
• Performance bounds of the intensity-based estimators for noisy phase retrieval
• The Capra-subdifferential of the ℓ ₀ pseudonorm
• Recovering imbalanced clusters via gradient-based projection pursuit
• Optimal spectral recovery of a planted vector in a subspace
• A restricted memory quasi-Newton bundle method for nonsmooth optimization on Riemannian manifolds
• Finding nonoverlapping substructures of a sparse matrix

This page was built for publication: Finding a Sparse Vector in a Subspace: Linear Sparsity Using Alternating Directions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976591)