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 re
- PDF / 346,262 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 211 Views
Abstract 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. Keywords Sparse · Constructive · Greedy · Lebesgue inequality
1 Introduction The paper is a survey on recent breakthrough results in constructive sparse approximation. In all cases discussed here the new technique is based on greedy approximation. The main motivation for the study of sparse approximation is that many real-world signals can be well approximated by sparse ones. Sparse approximation automatically implies a need for nonlinear approximation, in particular, for greedy approximation. We give a brief description of a sparse approximation problem and present a discussion of the obtained results and their relation to previous work. In Sect. 2 we concentrate on breakthrough results from [18] and [41]. In these papers we extended a fundamental result of Zhang [48] on the Lebesgue-type inequality for the RIP dictionaries in a Hilbert space (see Theorem 2.2 below) in several directions. We found new more general than the RIP conditions on a dictionary, which still V. Temlyakov (B) University of South Carolina, Columbia, USA e-mail: [email protected] V. Temlyakov Steklov Institute of Mathematics, Moscow, Russia © Springer International Publishing Switzerland 2016 T. Qian and L.G. Rodino (eds.), Mathematical Analysis, Probability and Applications – Plenary Lectures, Springer Proceedings in Mathematics & Statistics 177, DOI 10.1007/978-3-319-41945-9_7
183
184
V. Temlyakov
guarantee the Lebesgue-type inequalities in a Hilbert space setting. We generalized these conditions to a Banach space setting and proved the Lebesgue-type inequalities for dictionaries satisfying those conditions. To illustrate the power of new conditions we applied this new technique to bases instead of redundant dictionaries. In particular, this technique gave very strong results for the trigonometric system. In a general setting, we are working in a Banach space X with a redundant system of elements D (dictionary D). There is a solid justification of importance of a Banach space setting in numerical analysis in general and in sparse approximation in particular (see, for instance, [40], Preface, and [29]). An element (function, signal) mf ∈ X is said to be m-sparse with respect to D if it has a representation xi gi , gi ∈ D, i = 1, . . . , m. The set of all m-sparse elements is denoted by f = i=1 m (D). For a given element f 0 we
Data Loading...
