##
**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.

Reviewer: Yuly Makovoz (Lowell)

### MSC:

41A46 | Approximation by arbitrary nonlinear expressions; widths and entropy |

41A15 | Spline approximation |

PDF
BibTeX
XML
Cite

\textit{M. Kon} and \textit{L. Plaskota}, J. Complexity 21, No. 2, 211--229 (2005; Zbl 1069.41019)

### References:

[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.