Optimal pointwise sampling for L^2 approximation
share
Given a function u∈ L^2=L^2(D,μ), where D⊂ℝ^d and μ is a measure on D, and a linear subspace V_n⊂ L^2 of dimension n, we show that near-best approximation of u in V_n can be computed from a near-optimal budget of Cn pointwise evaluations of u, with C>1 a universal constant. The sampling points are drawn according to some random distribution, the approximation is computed by a weighted least-squares method, and the error is assessed in expected L^2 norm. This result improves on the results in [6,8] which require a sampling budget that is sub-optimal by a logarithmic factor, thanks to a sparsification strategy introduced in [17,18]. As a consequence, we obtain for any compact class 𝒦⊂ L^2 that the sampling number ρ_Cn^ rand(𝒦)_L^2 in the randomized setting is dominated by the Kolmogorov n-width d_n(𝒦)_L^2. While our result shows the existence of a randomized sampling with such near-optimal properties, we discuss remaining issues concerning its generation by a computationally efficient algorithm.
READ FULL TEXT