Exponential tractability of L₂-approximation with function values

DOI10.1007/S10444-023-10021-7arXiv2205.04141MaRDI QIDQ6398596FDOQ6398596

Paweł Siedlecki, Mario Ullrich, H. Woźniakowski, David Krieg

Publication date: 9 May 2022

Abstract: We study the complexity of high-dimensional approximation in the

L_{2}

-norm when different classes of information are available; we compare the power of function evaluations with the power of arbitrary continuous linear measurements. Here, we discuss the situation when the number of linear measurements required to achieve an error

v a r e p s i l o n i n (0, 1)

in dimension

d i n m a t h b b N

depends only poly-logarithmically on

v a r e p s i l o n^{- 1}

. This corresponds to an exponential order of convergence of the approximation error, which often happens in applications. However, it does not mean that the high-dimensional approximation problem is easy, the main difficulty usually lies within the dependence on the dimension

d

. We determine to which extent the required amount of information changes, if we allow only function evaluation instead of arbitrary linear information. It turns out that in this case we only lose very little, and we can even restrict to linear algorithms. In particular, several notions of tractability hold simultaneously for both types of available information.

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Multidimensional problems (41A63) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Rate of convergence, degree of approximation (41A25)

This page was built for publication: Exponential tractability of $L_2$-approximation with function values

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