Nonlinear methods of approximation (Q1396184): Difference between revisions

This extensive survey paper is, according to its author, complementary to the survey by \textit{R. A. DeVore} [Acta Numerica 7, 51--150 (1998; Zbl 0931.65007)]. The central concept is \(m\)-term approximation, that is, approximation of a given element \(f\) of a Banach space \(X\) by linear combinations of \(\leq m\) elements \(g_k\) taken from some fixed subset of \(X\) called dictionary and assumed to be dense in \(X\). Generally speaking, the \(g_k\) in the sum \(\sum_1^m c_k g_k\) approximating \(f\) depend on \(m\) and must be recalculated when \(m\) increases. Among the algorithms for finding good \(g_k\), of particular importance are the so-called greedy algorithms which add, when \(m\) advances to \(m+1\), only one new element. Various types of greedy algorithms are considered: pure, relaxed, weak, dual, thresholding, orthogonal, etc. as well as various dictionaries. The space \(X\) is either the Hilbert space or a general (usually uniformly smooth) Banach space. Convergence of algorithms is discussed and estimates for rates of convergence are found for various settings. For some concrete dictionaries one can claim more than what follows from the general theory. For example, two-sided estimates are given for approximation of functions \(f:[0,1]^2 \to {\mathbb R}\) by bilinear combinations of the form \(\sum_1^m c_k u_k(x_1)v_k(x_2)\). Other examples are: approximation of multivariate functions by linear combinations of ridge functions, that is, functions of the form \(g(x\cdot e)\), where \(x,e \in {\mathbb R}^d\), \(g:{\mathbb R}^1\to {\mathbb R}^1\); approximation by the trigonometric sums \(\sum_1^m c_ke^{i(x\cdot e_k)}\) and by elements of the Haar bases. Among other questions discussed in the paper are the connection between \(m\)-term approximation and \(\varepsilon\)-entropy and universality of dictionaries. As a source for comparizon and motivation, the author provides a detailed review of linear approximation methods. 34 open problems are stated. Bibliography contains 105 items.