Optimal weighted least-squares methods

Cohen, Albert¹ ; Migliorati, Giovanni¹

¹ Sorbonne Universités, UPMC Univ Paris 06, CNRS, UMR 7598, Laboratoire Jacques-Louis Lions, 4, place Jussieu 75005, Paris, France.

The SMAI Journal of computational mathematics, Tome 3 (2017), pp. 181-203

Résumé

We consider the problem of reconstructing an unknown bounded function $u$ defined on a domain $X\subset {ℝ}^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 $\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={ℝ}^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.

Détail

Publié le : 2017-10-02
DOI : 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.