Sparse approximation by greedy algorithms
It is a survey on recent results in constructive sparse approximation. Three directions are discussed here: (1) Lebesgue-type inequalities for greedy algorithms with respect to a special class of dictionaries, (2) constructive sparse approximation with respect to the trigonometric system, (3) sparse approximation with respect to dictionaries with tensor product structure. In all three cases constructive ways are provided for sparse approximation. The technique used is based on fundamental results from the theory of greedy approximation. In particular, results in the direction (1) are based on deep methods developed recently in compressed sensing. We present some of these results with detailed proofs.
Code (0)
등록된 구현이 없습니다.
Tasks
compressed sensingSimilar Papers 제목 키워드 기반
Sparse approximation and recovery by greedy algorithms in Banach spaces
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…
Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms
We consider the problem of sparse atomic optimization, where the notion of "sparsity" is generalized to meaning some linear combination of few atoms. The definition of atomic set is very broad; popular examples include t…
Step-Size Decay and Structural Stagnation in Greedy Sparse Learning
Greedy algorithms are central to sparse approximation and stage-wise learning methods such as matching pursuit and boosting. It is known that the Power-Relaxed Greedy Algorithm with step sizes $m^{-α}$ may fail to conver…
Sparse LearningSLS (Single $\ell_1$ Selection): a new greedy algorithm with an $\ell_1$-norm selection rule
In this paper, we propose a new greedy algorithm for sparse approximation, called SLS for Single L_1 Selection. SLS essentially consists of a greedy forward strategy, where the selection rule of a new component at each i…
DenoisingBiomechanical surrogate modelling using stabilized vectorial greedy kernel methods
Greedy kernel approximation algorithms are successful techniques for sparse and accurate data-based modelling and function approximation. Based on a recent idea of stabilization of such algorithms in the scalar output ca…