Orthogonal matching pursuit under the restricted isometry property

DOI10.1007/s00365-016-9338-2zbMath1379.94014arXiv1506.04779OpenAlexW2218353147MaRDI QIDQ515909

Wolfgang Dahmen, Albert Cohen, Ronald A. DeVore

Publication date: 17 March 2017

Published in: Constructive Approximation (Search for Journal in Brave)

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

zbMATH Keywords

instance optimalitybest \(n\)-term approximationorthogonal matching pursuit (OMP)restricted isometry property (RIP)

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Random matrices (algebraic aspects) (15B52) Information theory (general) (94A15) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Related Items

Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares, Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method, Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension, Conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery, The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials, Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries, Fast overcomplete dictionary construction with probabilistic guarantees, Flavors of Compressive Sensing, Analysis of target data-dependent greedy kernel algorithms: convergence rates for \(f\)-, \(f \cdot P\)- and \(f/P\)-greedy, Sparsity and incoherence in orthogonal matching pursuit, Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs, Efficiency of orthogonal super greedy algorithm under the restricted isometry property, Preserving injectivity under subgaussian mappings and its application to compressed sensing, Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit

Cites Work

• Unnamed Item
• A mathematical introduction to compressive sensing
• On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
• Instance-optimality in probability with an \(\ell _1\)-minimization decoder
• Stability and Robustness of Weak Orthogonal Matching Pursuits
• SPARSE APPROXIMATION AND RECOVERY BY GREEDY ALGORITHMS IN BANACH SPACES
• Sparse Approximation and Recovery by Greedy Algorithms
• Compressed sensing and best 𝑘-term approximation
• Greedy Approximation
• Greed is Good: Algorithmic Results for Sparse Approximation
• Greedy approximation
• Exact Recovery of Sparse Signals Using Orthogonal Matching Pursuit: How Many Iterations Do We Need?
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Stable signal recovery from incomplete and inaccurate measurements