Optimal weighted least-squares methods
The SMAI journal of computational mathematics, Volume 3 (2017) , pp. 181-203.

We consider the problem of reconstructing an unknown bounded function u defined on a domain X d from noiseless or noisy samples of u at n points (x i ) i=1,,n . We measure the reconstruction error in a norm L 2 (X,dρ) for some given probability measure dρ. Given a linear space V m with dim (V m )=mn, we study in general terms the weighted least-squares approximations from the spaces V m based on independent random samples. It is well known that least-squares approximations can be inaccurate and unstable when m is too close to n, even in the noiseless case. Recent results from [6, 7] have shown the interest of using weighted least squares for reducing the number n of samples that is needed to achieve an accuracy comparable to that of best approximation in V m , compared to standard least squares as studied in [4]. The contribution of the present paper is twofold. From the theoretical perspective, we establish results in expectation and in probability for weighted least squares in general approximation spaces V m . These results show that for an optimal choice of sampling measure dμ and weight w, which depends on the space V m and on the measure dρ, stability and optimal accuracy are achieved under the mild condition that n scales linearly with m up to an additional logarithmic factor. In contrast to [4], the present analysis covers cases where the function u and its approximants from V m are unbounded, which might occur for instance in the relevant case where X= d and dρ is the Gaussian measure. From the numerical perspective, we propose a sampling method which allows one to generate independent and identically distributed samples from the optimal measure dμ. This method becomes of interest in the multivariate setting where dμ is generally not of tensor product type. We illustrate this for particular examples of approximation spaces V m of polynomial type, where the domain X is allowed to be unbounded and high or even infinite dimensional, motivated by certain applications to parametric and stochastic PDEs.

Published online:
DOI: https://doi.org/10.5802/smai-jcm.24
Classification: 41A10,  41A25,  41A65,  62E17,  93E24
Keywords: multivariate approximation, weighted least squares, error analysis, convergence rates, random matrices, conditional sampling, polynomial approximation.
     author = {Albert Cohen and Giovanni Migliorati},
     title = {Optimal weighted least-squares methods},
     journal = {The SMAI journal of computational mathematics},
     pages = {181--203},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {3},
     year = {2017},
     doi = {10.5802/smai-jcm.24},
     mrnumber = {3716755},
     zbl = {1416.62177},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.24/}
Albert Cohen; Giovanni Migliorati. Optimal weighted least-squares methods. The SMAI journal of computational mathematics, Volume 3 (2017) , pp. 181-203. doi : 10.5802/smai-jcm.24. https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.24/

[1] B. Adcock; A. C. Hansen A generalized sampling theorem for stable reconstructions in arbitrary bases, J. Fourier Anal. Appl., Volume 18 (2012), pp. 685-716 | Article | MR 2984365 | Zbl 1259.94035

[2] G. Chardon; A. Cohen; L. Daudet Sampling and reconstruction of solutions to the Helmholtz equation, Sampl. Theory Signal Image Process., Volume 13 (2014), pp. 67-89 | MR 3315354 | Zbl 1346.94073

[3] A. Chkifa; A. Cohen; G. Migliorati; F. Nobile; R. Tempone Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic PDEs, M2AN, Volume 49 (2015), pp. 815-837 | Article | MR 3342229 | Zbl 1318.41004

[4] A. Cohen; M. A. Davenport; D. Leviatan On the stability and accuracy of least squares approximations, Found. Comput. Math., Volume 13 (2013), pp. 819-834 | Article | MR 3105946 | Zbl 1276.93086

[5] L. Devroye Non-Uniform Random Variate Generation, Springer, 1985

[6] A. Doostan; J. Hampton Coherence motivated sampling and convergence analysis of least squares polynomial Chaos regression, Comput. Methods Appl. Mech. Engrg., Volume 290 (2015), pp. 73-97 | Article | MR 3340149 | Zbl 1426.62174

[7] J. D. Jakeman; A. Narayan; T. Zhou A Christoffel function weighted least squares algorithm for collocation approximations, Math. Comp., Volume 86 (2017), pp. 1913-1947 | MR 3626543 | Zbl 1361.65009

[8] A. Máté; P. Nevai; V. Totik Szegö’s extremum problem on the unit circle, Annals of Mathematics,, Volume 134 (1991), pp. 433-453 | Article | Zbl 0752.42015

[9] G. Migliorati Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets, J. Approx. Theory, Volume 189 (2015), pp. 137-159 | Article | MR 3280676 | Zbl 1309.41002

[10] G. Migliorati; F. Nobile; R. Tempone Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points, J. Multivar. Analysis, Volume 142 (2015), pp. 167-182 | Article | MR 3412746 | Zbl 1327.41004

[11] G. Migliorati; F. Nobile; E. von Schwerin; R. Tempone Analysis of discrete L 2 projection on polynomial spaces with random evaluations, Found. Comput. Math., Volume 14 (2014), pp. 419-456 | MR 3201952 | Zbl 1301.41005

[12] P. Nevai Géza Freud, orthogonal polynomials and Christoffel Functions. A case study, J. Approx. theory, Volume 48 (1986), pp. 3-167 | Article | Zbl 0606.42020

[13] E. B. Saff; V. Totik Logarithmic Potentials with External Fields, Springer, 1997 | Zbl 0881.31001

[14] J. Tropp User friendly tail bounds for sums of random matrices, Found. Comput. Math., Volume 12 (2012), pp. 389-434 | Article | MR 2946459 | Zbl 1259.60008