We consider the problem of reconstructing an unknown bounded function $u$ defined on a domain $X\subset {\mathbb{R}}^{d}$ from noiseless or noisy samples of $u$ at $n$ points ${\left({x}^{i}\right)}_{i=1,\cdots ,n}$. We measure the reconstruction error in a norm ${L}^{2}(X,d\rho )$ for some given probability measure $d\rho $. Given a linear space ${V}_{m}$ with $\mathrm{dim}\left({V}_{m}\right)=m\le n$, 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\mu $ and weight $w$, which depends on the space ${V}_{m}$ and on the measure $d\rho $, 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={\mathbb{R}}^{d}$ and $d\rho $ 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\mu $. This method becomes of interest in the multivariate setting where $d\mu $ 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.

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.

@article{SMAI-JCM_2017__3__181_0, 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] 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] 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] 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] 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] Non-Uniform Random Variate Generation, Springer, 1985

[6] 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] A Christoffel function weighted least squares algorithm for collocation approximations, Math. Comp., Volume 86 (2017), pp. 1913-1947 | MR 3626543 | Zbl 1361.65009

[8] Szegö’s extremum problem on the unit circle, Annals of Mathematics,, Volume 134 (1991), pp. 433-453 | Article | Zbl 0752.42015

[9] 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] 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] 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] 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] Logarithmic Potentials with External Fields, Springer, 1997 | Zbl 0881.31001

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