On the worst-case error of least squares algorithms for $L_2$-approximation with high probability

Abstract

It was recently shown in [4] that, for $L_2$-approximation of functions from a Hilbert space, function values are almost as powerful as arbitrary linear information, if the approximation numbers are square-summable. That is, we showed that \[ e_n \,\lesssim\, \sqrt{\frac{1}{k_n} \sum_{j\geq k_n} a_j^2} \qquad \text{ with }\quad k_n \asymp \frac{n}{\ln(n)}, \] where $e_n$ are the sampling numbers and $a_k$ are the approximation numbers. In particular, if $(a_k)\in {\ell }_2$, then $e_n$ and $a_n$ are of the same polynomial order. For this, we presented an explicit (weighted least squares) algorithm based on i.i.d. random points and proved that this works with positive probability. This implies the existence of a good deterministic sampling algorithm. Here, we present a modification of the proof in [4] that shows that the same algorithm works with probability at least $1-n^{-c}$ for all $c>0$.

7 pages. arXiv admin note: substantial text overlap with arXiv:1905.02516

Cited by in corpus (9)

• A sharp upper bound for sampling numbers in $L_2$
• A note on sampling recovery of multivariate functions in the uniform norm
• Exponential tractability of $L_2$-approximation with function values
• New lower bounds for the integration of periodic functions
• On the power of iid information for linear approximation
• Function values are enough for $L_2$-approximation: Part II
• Sampling recovery in $L_2$ and other norms
• On the power of adaption and randomization
• Approximation of Functions: Optimal Sampling and Complexity