Orthogonal matching pursuit under the restricted isometry property

DOI10.1007/S00365-016-9338-2MaRDI QIDQ515909zbMATH OpenOpenAlexFDO

Authors Albert Cohen, Wolfgang Dahmen, Ronald 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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1215245 (Why is no real title available?)
• A mathematical introduction to compressive sensing
• Compressed sensing and best \(k\)-term approximation
• Exact Recovery of Sparse Signals Using Orthogonal Matching Pursuit: How Many Iterations Do We Need?
• Greed is Good: Algorithmic Results for Sparse Approximation
• Greedy approximation
• Greedy approximation
• Instance-optimality in probability with an \(\ell _1\)-minimization decoder
• On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
• Sparse Approximation and Recovery by Greedy Algorithms
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Sparse approximation and recovery by greedy algorithms in Banach spaces
• Stability and robustness of weak orthogonal matching pursuits
• Stable signal recovery from incomplete and inaccurate measurements

Cited in

(27)

• Error estimates for orthogonal matching pursuit and random dictionaries
• Stability and robustness of weak orthogonal matching pursuits
• 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
• Analysis of orthogonal multi-matching pursuit under restricted isometry property
• Robustness of orthogonal matching pursuit under restricted isometry property
• Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares
• Generalized Orthogonal Matching Pursuit
• Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
• Conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery
• Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries
• Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method
• When does OMP achieve exact recovery with continuous 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
• On a simple derivation of the complementary matching pursuit
• Orthogonal Matching Pursuit: A Brownian Motion Analysis
• Efficiency of orthogonal super greedy algorithm under the restricted isometry property
• Fast overcomplete dictionary construction with probabilistic guarantees
• The recovery guarantee for orthogonal matching pursuit method to reconstruct sparse polynomials
• 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
• The performance of orthogonal multi-matching pursuit under the restricted isometry property
• Flavors of compressive sensing
• A sharp RIP condition for orthogonal matching pursuit
• 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)