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

DOI10.1016/j.jat.2012.01.007zbMath1248.41048arXiv1003.5349OpenAlexW2030298412MaRDI 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 projectionorthogonal matching pursuitLebesgue-type inequalitiesbest \(m\)-term approximationorthogonal greedy algorithms

Mathematics Subject Classification ID

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

Related Items (7)

Sparse approximation is provably hard under coherent dictionaries ⋮ Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries ⋮ Explicit constructions of RIP matrices and related problems ⋮ Orthogonal matching pursuit under the restricted isometry property ⋮ On Optimal Estimate of the Block Orthogonal Greedy Algorithm for g-Frames ⋮ Unnamed Item ⋮ SPARSE APPROXIMATION AND RECOVERY BY GREEDY ALGORITHMS IN BANACH SPACES

Cites Work

• 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
• Unnamed Item
• Unnamed Item

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