Sparse Approximation and Recovery by Greedy Algorithms
From MaRDI portal
Abstract: We study sparse approximation by greedy algorithms. Our contribution is two-fold. First, we prove exact recovery with high probability of random -sparse signals within iterations of the Orthogonal Matching Pursuit (OMP). This result shows that in a probabilistic sense the OMP is almost optimal for exact recovery. Second, we prove the Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm, a generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. However, even in the case of a Hilbert space our results add some new elements to known results on the Lebesque-type inequalities for the RIP dictionaries. Our technique is a development of the recent technique created by Zhang.
Cited in
(24)- Sparse sampling recovery in integral norms on some function classes
- Computable Performance Bounds on Sparse Recovery
- Greedy approximation in convex optimization
- Sparse representations and approximation theory
- Efficient Least Residual Greedy Algorithms for Sparse Recovery
- Phase transitions for greedy sparse approximation algorithms
- Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit
- Approximate sparse recovery: optimizing time and measurements
- Sparse approximation based on a random overcomplete basis
- The WCGA in \(L^p(\log L)^{\alpha}\) spaces
- Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries
- Random points are good for universal discretization
- Orthogonal matching pursuit under the restricted isometry property
- A Greedy Algorithm for Sparse Precision Matrix Approximation
- Sparse Recovery With Graph Constraints
- Brief introduction in greedy approximation
- Sparse approximation using new greedy-like bases in superreflexive spaces
- A fast homotopy algorithm for gridless sparse recovery
- A new result on recovery sparse signals using orthogonal matching pursuit
- Covering point-sets with parallel hyperplanes and sparse signal recovery
- Sparse approximation by greedy algorithms
- Sparse approximation and recovery by greedy algorithms in Banach spaces
- Sampling recovery on function classes with a structural condition
- Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD
This page was built for publication: Sparse Approximation and Recovery by Greedy Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986270)
