Sparse approximation and recovery by greedy algorithms in Banach spaces

DOI10.1017/FMS.2014.7zbMATH Open1296.41030arXiv1303.6811OpenAlexW2963734283MaRDI QIDQ2879425FDOQ2879425

Authors: V. N. Temlyakov 

Publication date: 1 September 2014

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

Abstract: We study sparse approximation by greedy algorithms. We prove the Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm (WCGA), a generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. The results are proved for redundant dictionaries satisfying certain conditions. Then we apply these general results to the case of bases. In particular, we prove that the WCGA provides almost optimal sparse approximation for the trigonometric system in $L_p$, $2lep<infty$.

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

Recommendations

• Sparse approximation by greedy algorithms
• Convergence of some greedy algorithms in Banach spaces
• Greedy approximation in Banach spaces
• Greedy algorithms in Banach spaces

zbMATH Keywords

sparse approximationgreedy algorithmsorthogonal matching pursuitLebesgue-type inequalitiesbest \(m\)-term approximation

Mathematics Subject Classification ID

General theory of numerical analysis in abstract spaces (65J05) Spline approximation (41A15) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Geometry and structure of normed linear spaces (46B20) Algorithms for approximation of functions (65D15) Rate of convergence, degree of approximation (41A25)

Cites Work

• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Greed is Good: Algorithmic Results for Sparse Approximation
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Nonlinear methods of approximation
• The thresholding greedy algorithm, greedy bases, and duality
• A remark on greedy approximation in Banach spaces.
• Greedy algorithm for general biorthogonal systems
• Quasi-greedy bases and Lebesgue-type inequalities
• On the existence of almost greedy bases in Banach spaces
• Greedy algorithm and \(m\)-term trigonometric approximation
• Greedy approximation with regard to non-greedy bases
• An example of an almost greedy uniformly bounded orthonormal basis for \(L_p(0,1)\)
• Greedy algorithms in Banach spaces
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• On Lebesgue-type inequalities for greedy approximation
• On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
• Title not available (Why is that?)
• On performance of greedy algorithms
• Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants
• Sparse Approximation and Recovery by Greedy Algorithms
• Lebesgue-Type Inequalities for Greedy Approximation in Banach Spaces

Cited In (13)

• Greedy approximation in convex optimization
• Constructive sparse trigonometric approximation for functions with small mixed smoothness
• Efficiency of weak greedy algorithms for \(m\)-term approximations
• Greedy algorithms in Banach spaces
• Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries
• Unified error estimate for weak biorthogonal greedy algorithms
• Greedy-type approximation in Banach spaces and applications
• Nonlinear trigonometric approximations of multivariate function classes
• Orthogonal matching pursuit under the restricted isometry property
• Sparse approximation using new greedy-like bases in superreflexive spaces
• Sparse approximation with bases. Based on advanced courses given at the Centre de Recerca Matemàtica, Barcelona, Spain, November 2011. Edited by Sergey Tikhonov
• Sparse approximation by greedy algorithms
• Dictionary descent in optimization

This page was built for publication: Sparse approximation and recovery by greedy algorithms in Banach spaces

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