Phase transitions for greedy sparse approximation algorithms
From MaRDI portal
Publication:629259
DOI10.1016/J.ACHA.2010.07.001zbMATH Open1229.94003arXiv1004.1821OpenAlexW2150386037MaRDI QIDQ629259FDOQ629259
Authors: Jeffrey D. Blanchard, Coralia Cartis, Jared Tanner, Andrew Thompson 
Publication date: 9 March 2011
Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)
Abstract: A major enterprise in compressed sensing and sparse approximation is the design and analysis of computationally tractable algorithms for recovering sparse, exact or approximate, solutions of underdetermined linear systems of equations. Many such algorithms have now been proven to have optimal-order uniform recovery guarantees using the ubiquitous Restricted Isometry Property (RIP). However, it is unclear when the RIP-based sufficient conditions on the algorithm are satisfied. We present a framework in which this task can be achieved; translating these conditions for Gaussian measurement matrices into requirements on the signal's sparsity level, length, and number of measurements. We illustrate this approach on three of the state-of-the-art greedy algorithms: CoSaMP, Subspace Pursuit (SP), and Iterative Hard Thresholding (IHT). Designed to allow a direct comparison of existing theory, our framework implies that, according to the best known bounds, IHT requires the fewest number of compressed sensing measurements and has the lowest per iteration computational cost of the three algorithms compared here.
Full work available at URL: https://arxiv.org/abs/1004.1821
Recommendations
- Sparse approximation by greedy algorithms
- Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction
- Sparse Approximation and Recovery by Greedy Algorithms
- Greed is Good: Algorithmic Results for Sparse Approximation
- Approximation Bounds for Sparse Programs
- Algorithms for simultaneous sparse approximation. I: Greedy pursuit
- Phase transitions in semidefinite relaxations
- Optimization on sparse random hypergraphs and spin glasses
- Phase transitions in parameter rich optimization problems
- Large deviations of the greedy independent set algorithm on sparse random graphs
compressed sensingphase transitionsgreedy algorithmsrestricted isometry propertyGaussian matricessparse solutions to underdetermined systems
Cites Work
- Probing the Pareto frontier for basis pursuit solutions
- Title not available (Why is that?)
- Introductory lectures on convex optimization. A basic course.
- Compressive sampling
- Decoding by Linear Programming
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Compressed sensing
- Iterative hard thresholding for compressed sensing
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
- Title not available (Why is that?)
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
- Sparse Approximate Solutions to Linear Systems
- High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
- On sparse reconstruction from Fourier and Gaussian measurements
- Phase transitions for greedy sparse approximation algorithms
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Finding the stationary states of Markov chains by iterative methods
- Subspace Pursuit for Compressive Sensing Signal Reconstruction
- Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
- Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property
- Compressed sensing: how sharp is the restricted isometry property?
- Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
- Improved bounds on restricted isometry constants for Gaussian matrices
- Instance optimal decoding by thresholding in compressed sensing
- On support sizes of restricted isometry constants
Cited In (19)
- Compressive Sensing
- Iterative hard thresholding for compressed sensing
- On the number of iterations for convergence of CoSaMP and subspace pursuit algorithms
- The gap between the null space property and the restricted isometry property
- Phase transitions in semidefinite relaxations
- Relationship between the optimal solutions of least squares regularized with \(\ell_{0}\)-norm and constrained by \(k\)-sparsity
- Phase transitions for greedy sparse approximation algorithms
- Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
- Greedy-like algorithms for the cosparse analysis model
- Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants
- Hard thresholding pursuit algorithms: number of iterations
- GPU accelerated greedy algorithms for compressed sensing
- The restricted isometry property for random block diagonal matrices
- Performance comparisons of greedy algorithms in compressed sensing.
- From theoretical guarantee to practical performance: selectable and optimal step-lengths for IHT and HTP algorithms in compressed sensing
- On support sizes of restricted isometry constants
- Quasi-linear compressed sensing
- CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
- Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction
Uses Software
This page was built for publication: Phase transitions for greedy sparse approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q629259)
