On the Stability and Accuracy of Least Squares Approximations

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 dim(V _m )=m≤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 ²(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.