On the worst-case error of least squares algorithms for L₂-approximation with high probability

DOI10.1016/J.JCO.2020.101484arXiv2003.11947MaRDI QIDQ6337461FDOQ6337461

Publication date: 24 March 2020

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_{jgeq k_n} a_j^2} qquad ext{ 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}) i n e l l_{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

.

Mathematics Subject Classification ID

Numerical analysis (65-XX) Computer science (68-XX)

This page was built for publication: On the worst-case error of least squares algorithms for $L_2$-approximation with high probability

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