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

DOI10.1016/J.JAT.2012.01.007zbMATH Open1248.41048arXiv1003.5349OpenAlexW2030298412MaRDI QIDQ420768FDOQ420768

Authors: E. D. Livshitz 

Publication date: 23 May 2012

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

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

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

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

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)

Cites Work

• Stable recovery of sparse overcomplete representations in the presence of noise
• Greed is Good: Algorithmic Results for Sparse Approximation
• Simple Constructions of Almost k-wise Independent Random Variables
• Deterministic constructions of compressed sensing matrices
• On Lebesgue-type inequalities for greedy approximation
• Title not available (Why is that?)
• On performance of greedy algorithms
• On greedy algorithms for dictionaries with bounded cumulative coherence
• On the size of incoherent systems
• Title not available (Why is that?)

Cited In (8)

• On optimal estimate of the block orthogonal greedy algorithm for g-frames
• Explicit constructions of RIP matrices and related problems
• 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)