Information-based nonlinear approximation: an average case setting

From MaRDI portal





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.











This page was built for publication: Information-based nonlinear approximation: an average case setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1772685)