Sparse approximation with bases. Based on advanced courses given at the Centre de Recerca Matemàtica, Barcelona, Spain, November 2011. Edited by Sergey Tikhonov (Q2339770): Difference between revisions

This book mainly deals with a kind of interesting and current nonlinear approximation called \textit{\(m\)-term approximation}, or \textit{sparse approximation}, with bases. The idea, utilized in the so-called \textit{threshholding greedy algorithm} (TGA shortly), is that the elements of the basis used in approximation depend on the function being approximated. The fundamental question, answered in this book, is which bases are suitable for the use of TGA. Also, an introduction to the case when the basis is replaced by a more general system which is not necessarily minimal (e.g., redundant system, dictionary) is made. In Chapter 1, the existence and uniqueness of a best approximant in linear setting and classical results on Schauder and unconditional bases are presented. Further, some existence results of the best \(m\)-term approximation (\(m\)-fixed) are given for the cases when we approximate functions \(f\) in \(L_{p}\) spaces, by elements in the nonlinear subspace of all complex trigonometric polynomials which have at most \(m\) nonzero coefficients and by elements in the nonlinear subspace of all piecewise constant functions with at most \(m-1\) breakpoints. Chapter 2 contains the first results on greedy-type bases, in particular for the trigonometric system and for the Haar basis. The general setting can be described as follows. Let \(X\) be a Banach space with a basis \(\Psi=\{\psi_{k}\}_{k\in \mathbb{N}}\) satisfying \(\|\psi_{k}\|\geq C>0\), \(k\in \mathbb{N}\). For \(f\in X\), consider the expansion \(f=\sum_{k=1}^{\infty}c_{k}(f, \Psi)\cdot \psi_{k}\). For an element \(f\) we say that a permutation of natural numbers, \(\rho=(\rho(j))\), \(\rho(j)=k_{j}\), belongs to \(D(f)\), if \(|c_{k_{1}}(f, \Psi)|\geq |c_{k_{2}}(f, \Psi)|\geq \dots\) The \(m\)th greedy approximant of \(f\) with respect to the basis \(\Psi\) and a permutation \(\rho\in D(f)\) is defined by \(G_{m}(f, \Psi, \rho):=G_{m}(f, \Psi):=\sum_{j=1}^{m}c_{k_{j}}(f, \Psi)\psi_{k_{j}}\) and this algorithm \(G_{m}\) is called threshholding greedy algorithm (TGA), or simply greedy algorithm (GA). The best \(m\)-term approximation with respect to \(\Psi\) is defined by \[ \sigma_{m}(f, \Psi)_{X}=\inf_{c_{k}, \Lambda} \|f - \sum_{k\in \Lambda}c_{k} \psi_{k}\|_{X}, \] where the infimum is taken over the coefficients \(c_{k}\) and all the sets of indices \(\Lambda\) with cardinality \(|\Lambda|=m\). A basis \(\Psi\) will be called a greedy basis, if for every \(f\in X\), there exists a permutation \(\rho\in D(f)\), such that \(\|f-G_{m}(f, \Psi, \rho)\|_{X}\leq C \sigma_{m}(f, \Psi)_{X}\), where \(C>0\) is independent of \(f\) and \(m\). This inequality can be called Lebesgue-type inequality and its name was suggested by the classical upper estimate proved by Lebesgue in the approximation by the partial sum of the Fourier series \(S_{n}(f)\), \(\|f-S_{n}(f)\|_{\infty}\leq (4+ (4 ln(n))/\pi^{2})E_{n}(f)_{\infty}\), with \(E_{n}(f)_{\infty}\) denoting the best approximation by trigonometric polynomials of degree \(\leq n\) in the uniform norm. It is worth noting the advantage of the \(n\)-term nonlinear approximation over the linear approximation, by comparing in the case of \(f(x)=|\sin(x)|\), the best linear approximation with trigonometric polynomials of degree \(\leq n\), \(E_{n}(f)_{\infty}\sim \frac{1}{n}\) (obtained by Ch. de la Vallée Poussin and S. N. Bernstein) and the \(n\)-term best approximation obtained by Maiorov, \(\sigma(|\sin|, {\mathcal{T}})_{\infty}\sim \frac{1}{n^{3/2}}\), where \({\mathcal{T}}\) denotes the trigonometric system. One of the main results in this chapter is the following Lebesgue-type inequality. Theorem. For each \(f\in L_{p}([0, 2\pi]^{d})\), \(1\leq p\leq \infty\), we have \[ \|f-G_{m}(f, {\mathcal{T}}^{d})\|_{p}\leq (1+3m^{h(p)})\sigma_{m}(f, {\mathcal{T}}^{d})_{p}, \] where \(h(p)=|1/2 - 1/p|\) and \({\mathcal{T}}^{d}\) denotes the system of all trigonometric polynomials of \(d\) variables. In addition, it is proved here that the Haar basis is a greedy basis for the \(L_{p}\) spaces with \(1<p<\infty\) and that in general, a basis is greedy if and only if it is unconditional and democratic. Some further properties of greedy-type bases also are discussed. Chapter 3 discusses Lebesgue-type inequalities for a wider class of bases, called quasi-greedy bases. Chapter 4 treats some greedy-type bases from the duality point of view. For example, it it proved that under some conditions, the basic sequence, dual (biorthogonal) to an almost-greedy (or greedy) basis, is also almost-greedy (greedy). Chapter 5 is a strong development of the results in Chapter 2, for the case of trigonometric approximation. It turns out that the trigonometric system is a very good testing field for different greedy-type algorithms. However, these results show that TGA is not a good algorithm for the trigonometric system. It turns out that greedy algorithms designed for general dictionaries work well for a trigonometric system. An introduction to the theory of of these algorithms with respect to more general systems is made in Chapter 6. Chapter 7 called \textit{Appendix} contains well-known results in analysis used in the previous chapters. The book is based on numerous research papers of the author and is recommended to researchers working in approximation theory, numerical analysis, harmonic analysis and functional analysis. Also, it could be used for various graduate courses in the above mentioned topics.