On the stability and accuracy of least squares approximations
This work addresses the fundamental problem of stable and accurate function approximation from random samples, providing theoretical guarantees for practitioners.
The paper provides a criterion on the dimension m of approximation spaces to ensure that least squares approximations from random samples are stable and achieve accuracy comparable to the best approximation error in L^2 norm. The criterion is illustrated for trigonometric and algebraic polynomials with uniform and Chebyshev measures.
We consider the problem of reconstructing an unknown function $f$ on a domain $X$ from samples of $f$ at $n$ randomly chosen points with respect to a given measure $ρ_X$. Given a sequence of linear spaces $(V_m)_{m>0}$ with ${\rm dim}(V_m)=m\leq n$, we study the least squares approximations from the spaces $V_m$. It is well known that such approximations can be inaccurate when $m$ is too close to $n$, even when the samples are noiseless. Our main result provides a criterion on $m$ that describes the needed amount of regularization to ensure that the least squares method is stable and that its accuracy, measured in $L^2(X,ρ_X)$, is comparable to the best approximation error of $f$ by elements from $V_m$. We illustrate this criterion for various approximation schemes, such as trigonometric polynomials, with $ρ_X$ being the uniform measure, and algebraic polynomials, with $ρ_X$ being either the uniform or Chebyshev measure. For such examples we also prove similar stability results using deterministic samples that are equispaced with respect to these measures.