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

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
Set OpenAlex properties.
 
(2 intermediate revisions by 2 users not shown)
Property / author
 
Property / author: Vladimir N. Temlyakov / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Sorin Gheorghe Gal / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/978-3-0348-0890-3 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1185548173 / rank
 
Normal rank

Latest revision as of 14:39, 19 March 2024

scientific article
Language Label Description Also known as
English
Sparse approximation with bases. Based on advanced courses given at the Centre de Recerca Matemàtica, Barcelona, Spain, November 2011. Edited by Sergey Tikhonov
scientific article

    Statements

    Sparse approximation with bases. Based on advanced courses given at the Centre de Recerca Matemàtica, Barcelona, Spain, November 2011. Edited by Sergey Tikhonov (English)
    0 references
    7 April 2015
    0 references
    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.
    0 references
    Schauder basis
    0 references
    Haar basis
    0 references
    trigonometric system
    0 references
    unconditional bases
    0 references
    general dictionaries
    0 references
    greedy bases
    0 references
    quasi-greedy bases
    0 references
    almost-greedy bases
    0 references
    best approximation
    0 references
    greedy algorithm
    0 references
    \(m\)-term approximation
    0 references
    sparse approximation with bases
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references