Information-based nonlinear approximation: an average case setting. (English) Zbl 1069.41019

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.


41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
41A15 Spline approximation
Full Text: DOI Link


[1] DeVore, R.A., Nonlinear approximation, Acta numer., 8, 51-150, (1998) · Zbl 0931.65007
[2] Kon, M.A.; Plaskota, L., Information complexity of neural networks, Neural networks, 13, 365-376, (2000)
[3] Kon, M.A.; Plaskota, L., Complexity of neural network approximation with limited informationa worst case approach, J. complexity, 17, 345-365, (2000) · Zbl 0984.68127
[4] Maiorov, V.E.; Wasilkowski, G.W., Probabilistic and average linear widths in \(L_\infty\) norm with respect to r-fold Wiener measure, J. approx. theory, 84, 31-40, (1996) · Zbl 0835.41025
[5] Plaskota, L., Noisy information and computational complexity, (1996), Cambridge University Press Cambridge · Zbl 0925.68158
[6] Plaskota, L., Average case \(L_\infty\) approximation in the presence of Gaussian noise, J. approx. theory, 93, 501-515, (1998) · Zbl 0913.41019
[7] Traub, J.F.; Wasilkowski, G.W.; Wo┼║niakowski, H., Information-based complexity, (1988), Academic Press New York · Zbl 0674.68039
[8] Wasilkowski, G.W., Information of varying cardinality, J. complexity, 2, 204-228, (1986) · Zbl 0615.94004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.