Sparse approximation by greedy algorithms
This is an incremental survey that synthesizes existing research in sparse approximation for the mathematical and computational communities.
The paper surveys recent results in constructive sparse approximation, focusing on Lebesgue-type inequalities for greedy algorithms, approximation with trigonometric systems, and dictionaries with tensor product structures, providing constructive methods based on greedy approximation theory and compressed sensing techniques.
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.