On the worst-case error of least squares algorithms for L_2-approximation with high probability
share
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 ≲ √(1/k_n∑_j≥ k_n a_j^2) with k_n n/ln(n), where e_n are the sampling numbers and a_k are the approximation numbers. In particular, if (a_k)∈ℓ_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.
READ FULL TEXT