On performance of greedy algorithms
type: Item
instance of: scholarly article
title: On performance of greedy algorithms
zbMATH Open document ID: 1230.41005
author: V. N. Temlyakov
author: Pavel Zheltov
published in: Journal of Approximation Theory
publication date: 2011-10-10T00:00:00Z
review text: Let \(H\) be a Hilbert space and \(\mathcal{D}:=\{\varphi_{i}:i\in\mathbb{N} \}\subset H\) be such that \(\overline{\text{span}\mathcal{D}}\mathcal{=}H.\) A dictionary \(\mathcal{D}\) is called \(M\)-coherent if its coherence, defined by \(\sup\{|<\varphi,\psi>| :\varphi,\psi\in\mathcal{D}, \varphi\neq\psi\}\) is exactly \(M.\) The authors consider the Orthogonal Greedy Algorithm (OGA) and Pure Greedy Algorithm (PGA) for \(M\)-coherent dictionaries and study the performance of such algorithms. They prove that the OGA for dictionaries with small coherence \(M\) performs almost as well as the best \(m\)-term approximation for signals with sparsity close to the theoretically possible threshold \(m=\frac{1}{2}(M^{-1}+1).\) This threshold is sharp. The above results are obtained by proving an additive-type Lebesgue inequality for OGA applied to every \(M\)-coherent dictionary \(\mathcal{D}\) and any signal \(f\in H\) (Th. 5). Also, an additive-type Lebesgue inequality for PGA (Th.8) is established. The PGA matches the rate of convergence of the best \(m\)-term approximation beyond the saturation limit of \(m^{-\frac{1}{2}}.\)
reviewed by: Costică Mustăţa
Mathematics Subject Classification ID: 41A65
Mathematics Subject Classification ID: 41A30
zbMATH DE Number: 5955949
zbMATH Keywords: additive-type Lebesgue inequality
zbMATH Keywords: greedy algorithm
zbMATH Keywords: orthogonal matching pursuit
zbMATH Keywords: \(m\)-term approximation
zbMATH Keywords: incoherent dictionary
zbMATH Keywords: coherence
zbMATH Keywords: orthogonal greedy algorithm
zbMATH Keywords: sparse representation
describes a project that uses: CoSaMP
MaRDI profile type: Publication
full work available at URL: j.jat.2011.03.009
OpenAlex ID: W2058891218
cites work: Adaptive greedy approximations
cites work: Some remarks on greedy algorithms
cites work: Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
cites work: Stable recovery of sparse overcomplete representations in the presence of noise
cites work: On Lebesgue-type inequalities for greedy approximation
cites work: Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
cites work: Q4471300
cites work: Sparse representations in unions of bases
cites work: Projection pursuit
cites work: On a conjecture of Huber concerning the convergence of projection pursuit regression
cites work: Two lower estimates in greedy approximation
cites work: CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
cites work: Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
cites work: Greedy approximation
cites work: Greed is Good: Algorithmic Results for Sparse Approximation
cites work: Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
DOI: 10.1016/J.JAT.2011.03.009
Recommended article: Q3737235
Recommended article: Some remarks on greedy algorithms
Recommended article: Greedy in Approximation Algorithms
Recommended article: Q4038320
Recommended article: A note on greedy algorithm
Recommended article: Optimality of the greedy algorithm for some function classes
Recommended article: The average performance of the greedy matching algorithm
Recommended article: Some results on greedy algorithm conjectures
Recommended article: The classification of greedy algorithms
description: scientific article; zbMATH DE number 5955949