On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries

DOI10.1016/j.jat.2012.01.007zbMath1248.41048arXiv1003.5349MaRDI QIDQ420768

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 projection; orthogonal matching pursuit; Lebesgue-type inequalities; best \(m\)-term approximation; orthogonal greedy algorithms

Mathematics Subject Classification ID

46C05: Hilbert and pre-Hilbert spaces: geometry and topology (including spaces with semidefinite inner product)

41A65: Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)

41A17: Inequalities in approximation (Bernstein, Jackson, Nikol'ski?-type inequalities)

41A25: Rate of convergence, degree of approximation

65D15: Algorithms for approximation of functions

Related Items

Unnamed Item, Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries, Sparse approximation is provably hard under coherent dictionaries, Orthogonal matching pursuit under the restricted isometry property, Explicit constructions of RIP matrices and related problems, SPARSE APPROXIMATION AND RECOVERY BY GREEDY ALGORITHMS IN BANACH SPACES

Cites Work

• Unnamed Item
• Unnamed Item
• On greedy algorithms for dictionaries with bounded cumulative coherence
• On performance of greedy algorithms
• On the size of incoherent systems
• Deterministic constructions of compressed sensing matrices
• On Lebesgue-type inequalities for greedy approximation
• 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