Orthogonal matching pursuit under the restricted isometry property

DOI10.1007/S00365-016-9338-2zbMATH Open1379.94014arXiv1506.04779OpenAlexW2218353147MaRDI QIDQ515909FDOQ515909

Authors: Albert Cohen, Wolfgang Dahmen, Ronald DeVore 

Publication date: 17 March 2017

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

Abstract: This paper is concerned with the performance of Orthogonal Matching Pursuit (OMP) algorithms applied to a dictionary $mathcalD$ in a Hilbert space $mathcalH$. Given an element $finmathcalH$, OMP generates a sequence of approximations $f_n$, $n=1,2,dots$, each of which is a linear combination of $n$ dictionary elements chosen by a greedy criterion. It is studied whether the approximations $f_n$ are in some sense comparable to {em best $n$ term approximation} from the dictionary. One important result related to this question is a theorem of Zhang cite{TZ} in the context of sparse recovery of finite dimensional signals. This theorem shows that OMP exactly recovers $n$-sparse signal, whenever the dictionary $mathcalD$ satisfies a Restricted Isometry Property (RIP) of order $An$ for some constant $A$, and that the procedure is also stable in $el{l}^2$ under measurement noise. The main contribution of the present paper is to give a structurally simpler proof of Zhang's theorem, formulated in the general context of $n$ term approximation from a dictionary in arbitrary Hilbert spaces $mathcalH$. Namely, it is shown that OMP generates near best $n$ term approximations under a similar RIP condition.

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

Recommendations

• Robustness of orthogonal matching pursuit under restricted isometry property
• Improved bounds on restricted isometry constant for orthogonal multi matching pursuit
• A sharp RIP condition for orthogonal matching pursuit
• Error estimates for orthogonal matching pursuit and random dictionaries
• The performance of orthogonal multi-matching pursuit under the restricted isometry property

zbMATH Keywords

best \(n\)-term approximationinstance optimalityorthogonal matching pursuit (OMP)restricted isometry property (RIP)

Mathematics Subject Classification ID

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

Cites Work

• Stable signal recovery from incomplete and inaccurate measurements
• Title not available (Why is that?)
• Compressed sensing and best \(k\)-term approximation
• A mathematical introduction to compressive sensing
• Greed is Good: Algorithmic Results for Sparse Approximation
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Greedy approximation
• Greedy approximation
• Sparse approximation and recovery by greedy algorithms in Banach spaces
• 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
• Exact Recovery of Sparse Signals Using Orthogonal Matching Pursuit: How Many Iterations Do We Need?

Cited In (22)

• Error estimates for orthogonal matching pursuit and random dictionaries
• Greedy solution of ill-posed problems: error bounds and exact inversion
• Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit
• Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares
• The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials
• Analysis of orthogonal multi-matching pursuit under restricted isometry property
• Generalized Orthogonal Matching Pursuit
• Flavors of Compressive Sensing
• Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
• Conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery
• Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method
• Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries
• Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension
• A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Orthogonal Matching Pursuit: A Brownian Motion Analysis
• On a simple derivation of the complementary matching pursuit
• Efficiency of orthogonal super greedy algorithm under the restricted isometry property
• Fast overcomplete dictionary construction with probabilistic guarantees
• Sparsity and incoherence in orthogonal matching pursuit
• Analysis of target data-dependent greedy kernel algorithms: convergence rates for \(f\)-, \(f \cdot P\)- and \(f/P\)-greedy
• On the exponential convergence of matching pursuits in quasi-incoherent dictionaries

This page was built for publication: Orthogonal matching pursuit under the restricted isometry property

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