Phase transitions for greedy sparse approximation algorithms
From MaRDI portal
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.
The authors deal with three illustrative greedy algorithms -- compressed sensing machine pursuits (CoSeMP), subspace pursuits (SP), and iterative hard thresholdings (IHT) -- that have similar uniform guarantees of successful recovery of sparse signals when the measurement matrix \(A\) satisfies the ubiquitous restricted isometry property (RIP). These three algorithms are related. The authors develop several techniques. They derive an important theorem that can be used for CoSeMP, SP, and IHT algorithms. The phase-transition framework translates the generic RIP-based conditions of Theorem 3.
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
Cites work
- Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property
- Compressed sensing
- Compressed sensing: how sharp is the restricted isometry property?
- Compressive sampling
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Decoding by Linear Programming
- Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
- Finding the stationary states of Markov chains by iterative methods
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Improved bounds on restricted isometry constants for Gaussian matrices
- Instance optimal decoding by thresholding in compressed sensing
- Introductory lectures on convex optimization. A basic course.
- Iterative hard thresholding for compressed sensing
- On sparse reconstruction from Fourier and Gaussian measurements
- On support sizes of restricted isometry constants
- Phase transitions for greedy sparse approximation algorithms
- Probing the Pareto frontier for basis pursuit solutions
- Sparse Approximate Solutions to Linear Systems
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
- Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
- Subspace Pursuit for Compressive Sensing Signal Reconstruction
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
Cited in
(19)- Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction
- On the number of iterations for convergence of CoSaMP and subspace pursuit algorithms
- Greedy-like algorithms for the cosparse analysis model
- Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
- The gap between the null space property and the restricted isometry property
- Compressive Sensing
- Relationship between the optimal solutions of least squares regularized with \(\ell_{0}\)-norm and constrained by \(k\)-sparsity
- Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants
- Performance comparisons of greedy algorithms in compressed sensing.
- Phase transitions in semidefinite relaxations
- CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
- The restricted isometry property for random block diagonal matrices
- Quasi-linear compressed sensing
- Phase transitions for greedy sparse approximation algorithms
- 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
- Iterative hard thresholding for compressed sensing
- Hard thresholding pursuit algorithms: number of iterations
- GPU accelerated greedy algorithms for compressed sensing
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)
