Super greedy type algorithms

DOI10.1007/S10444-011-9220-5zbMATH Open1258.41013arXiv1010.5423OpenAlexW2159665097MaRDI QIDQ1928073FDOQ1928073

Authors: Entao Liu, V. N. Temlyakov 

Publication date: 2 January 2013

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

Abstract: We study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy-type algorithms. We call such greedy algorithms {it super greedy algorithms}. The idea of picking several elements at a greedy step of the algorithm is not new. Recently, we observed the following new phenomenon. For incoherent dictionaries these new type of algorithms (super greedy algorithms) provide the same (in the sense of order) upper bound for the error as their analogues from the standard greedy algorithms. The super greedy algorithms are computationally simpler than their analogues from the standard greedy algorithms. We continue to study this phenomenon.

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

Recommendations

• Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries
• Vector greedy algorithms
• Weak greedy algorithms
• Projection greedy algorithm
• On performance of greedy algorithms

zbMATH Keywords

thresholdingconvergence rateincoherent dictionarysuper greedy algorithms

Mathematics Subject Classification ID

Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Geometry and structure of normed linear spaces (46B20) Rate of convergence, degree of approximation (41A25) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Cites Work

• Nonlinear methods of approximation
• Some remarks on greedy algorithms
• Weak greedy algorithms
• Greedy approximation
• Greedy algorithms and \(M\)-term approximation with regard to redundant dictionaries
• Atomic decomposition by basis pursuit
• On Lebesgue-type inequalities for greedy approximation

Cited In (2)

• Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries
• Efficiency of orthogonal super greedy algorithm under the restricted isometry property

Uses Software

• PDCO

This page was built for publication: Super greedy type algorithms

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