With cedram.org   version française
Search for an article
Table of contents for this volume | Previous article | Next article
Albert Cohen; Giovanni Migliorati
Optimal weighted least-squares methods
SMAI-Journal of computational mathematics, 3 (2017), p. 181-203, doi: 10.5802/smai-jcm.24
Article PDF
Class. Math.: 41A10, 41A25, 41A65, 62E17, 93E24
Keywords: multivariate approximation, weighted least squares, error analysis, convergence rates, random matrices, conditional sampling, polynomial approximation.


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 $(x^i)_{i=1,\dots ,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 ${\rm dim}(V_m)=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.


[1] B. Adcock & A. C. Hansen, “A generalized sampling theorem for stable reconstructions in arbitrary bases”, J. Fourier Anal. Appl. 18 (2012), p. 685-716 Article
[2] G. Chardon, A. Cohen & L. Daudet, “Sampling and reconstruction of solutions to the Helmholtz equation”, Sampl. Theory Signal Image Process. 13 (2014), p. 67-89
[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 49 (2015), p. 815-837 Article
[4] A. Cohen, M. A. Davenport & D. Leviatan, “On the stability and accuracy of least squares approximations”, Found. Comput. Math. 13 (2013), p. 819-834 Article
[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. 290 (2015), p. 73-97 Article
[7] J. D. Jakeman, A. Narayan & T. Zhou, “A Christoffel function weighted least squares algorithm for collocation approximations”, Math. Comp. 86 (2017), p. 1913-1947
[8] A. Máté, P. Nevai & V. Totik, “Szegö’s extremum problem on the unit circle”, Annals of Mathematics, 134 (1991), p. 433-453 Article
[9] G. Migliorati, “Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets”, J. Approx. Theory 189 (2015), p. 137-159 Article
[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 142 (2015), p. 167-182 Article
[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. 14 (2014), p. 419-456
[12] P. Nevai, “Géza Freud, orthogonal polynomials and Christoffel Functions. A case study”, J. Approx. theory 48 (1986), p. 3-167 Article
[13] E. B. Saff & V. Totik, Logarithmic Potentials with External Fields, Springer, 1997
[14] J. Tropp, “User friendly tail bounds for sums of random matrices”, Found. Comput. Math. 12 (2012), p. 389-434 Article