Information-based nonlinear approximation: an average case setting (Q1772685)

Given an element \(f\) of a Banach space \(X\) and a subset \(D\), called a dictionary, the authors study the so-called \(k\)-term approximations to \(f\), that is, approximations of the form \[ \sum_{j=1}^k a_jf_j \quad a_i \in {\mathbb R}, \quad f_j \in D. \] It is assumed that \(f\) is an element of a subset \(F \subset X\), equiped with a probability measure \(\mu\). The information about \(f\) is given by the values \(L_1f, \ldots , L_n f\) of some \(n\) linear functionals, and the error of approximation is estimated in the average (as opposed to the worst) case. It is shown that the problem can be essentially decomposed in two partial problems that can be solved independently. As an application, the authors consider piecewise polynomial approximation in \(C[0,1]\) on the class \(F_r\) of functions \(f \in C^r\) with \(\| f^{(r)}\| \leq 1\), with respect to the \(r\)-fold Wiener measure. In this case, to approximate \(f\) with error \(\varepsilon\) it is necessary and sufficient to know its values at \(O\left ( [\varepsilon^{-1}\ln^{1/2}(1/\varepsilon)]^{1/(r+1/2)} \right )\) equidistant points and use \(O\left (\varepsilon^{-1/(r+1/2)} \right )\) adaptively chosen breakpoints.