On the optimality of the orthogonal greedy algorithm for -coherent dictionaries

DOI10.1016/J.JAT.2012.01.007MaRDI QIDQ420768zbMATH OpenOpenAlexFDO

Authors E. D. Livshitz

Publication date 23 May 2012

Published in Journal of Approximation Theory (Search for Journal in Brave)

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

zbMATH Keywords

orthogonal matching pursuitorthogonal projectionLebesgue-type inequalitiesbest \(m\)-term approximationorthogonal greedy algorithms

Mathematics Subject Classification ID

Inequalities in approximation (Bernstein, Jackson, Nikol'ski?-type inequalities) (41A17) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Algorithms for approximation of functions (65D15) Rate of convergence, degree of approximation (41A25) Hilbert and pre-Hilbert spaces: geometry and topology (including spaces with semidefinite inner product) (46C05)

Abstract: We show that Orthogonal Greedy Algorithms (Orthogonal Matching Pursuit) provides almost optimal approximation on the first [1/(20M)] steps for M-coherent dictionaries

Recommendations

• On performance of greedy algorithms
• Realizability of greedy algorithms
• Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries
• On Lebesgue-type inequalities for greedy approximation
• On greedy algorithms for dictionaries with bounded cumulative coherence

Cites work

• scientific article; zbMATH DE number 3486464 (Why is no real title available?)
• scientific article; zbMATH DE number 2079345 (Why is no real title available?)
• Deterministic constructions of compressed sensing matrices
• Greed is Good: Algorithmic Results for Sparse Approximation
• On Lebesgue-type inequalities for greedy approximation
• On greedy algorithms for dictionaries with bounded cumulative coherence
• On performance of greedy algorithms
• On the size of incoherent systems
• Simple Constructions of Almost k-wise Independent Random Variables
• Stable recovery of sparse overcomplete representations in the presence of noise

Cited in

(8)

• Explicit constructions of RIP matrices and related problems
• On optimal estimate of the block orthogonal greedy algorithm for g-frames
• Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries
• Orthogonal matching pursuit under the restricted isometry property
• Sparse approximation is provably hard under coherent dictionaries
• Realizability of greedy algorithms
• Greedy algorithms and approximation properties for frames in Hilbert spaces
• Sparse approximation and recovery by greedy algorithms in Banach spaces

This page was built for publication: On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries

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