On the power of standard information for tractability for $L_2$-approximation in the randomized setting

Abstract

We study approximation of multivariate functions from a separable Hilbert space in the randomized setting with the error measured in the weighted $L_2$ norm. We consider algorithms that use standard information ${\Lambda }^{\mathrm{std}}$ consisting of function values or general linear information ${\Lambda }^{\mathrm{all}}$ consisting of arbitrary linear functionals. We use the weighted least squares regression algorithm to obtain the upper estimates of the minimal randomized error using ${\Lambda }^{\mathrm{std}}$. We investigate the equivalences of various notions of algebraic and exponential tractability for ${\Lambda }^{\mathrm{std}}$ and ${\Lambda }^{\mathrm{all}}$ for the normalized or absolute error criterion. We show that in the randomized setting for the normalized or absolute error criterion, the power of ${\Lambda }^{\mathrm{std}}$ is the same as that of ${\Lambda }^{\mathrm{all}}$ for all notions of exponential and algebraic tractability without any condition. Specifically, we solve four Open Problems 98, 100-102 as posed by E.Novak and H.Woźniakowski in the book: Tractability of Multivariate Problems, Volume III: Standard Information for Operators, EMS Tracts in Mathematics, Zürich, 2012.

25 pages

Cited by in corpus (1)

• A sharp upper bound for sampling numbers in $L_2$