Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

We analyze the accuracy of the discrete least-squares approximation of a function $u$ in multivariate polynomial spaces $P_\Lambda:=span\{y\mapsto y^\nu \,: \, \nu\in \Lambda\}$ with $\Lambda\subset N_0^d$ over the domain $\Gamma:=[-1,1]^d$ , based on the sampling of this function at points $y^1,\dots,y^m \in \Gamma$ . The samples are independently drawn according to a given probability density $\rho$ belonging to the class of multivariate beta densities, which includes the uniform density as a particular case. Motivated by recent results in high-dimensional parametric and stochastic PDEs, we restrict our attention to polynomial spaces associated with \emph{downward closed} sets $\Lambda$ of \emph{prescribed} cardinality $n$ and we optimize the choice of the space for the given sample. This implies in particular that the selected polynomial space depends on the sample. We are interested in comparing the error of this least-squares approximation measured in $L^2(\Gamma,\rho)$ with the best achievable polynomial approximation error when using downward closed sets of cardinality $n$ . We establish conditions between the dimension $n$ and the size $m$ of the sample, under which these two errors are proven to be comparable. We show that the dimension $d$ enters only moderately in the resulting trade-off between $m$ and $n$ , in terms of a logarithmic factor $\ln(d)$ , and is even absent when the optimization is restricted to a relevant subclass of downward closed sets. In principle, this allows one to use these methods in high dimension. Our analysis builds upon (Chkifa et al. in ESAIM Math Model Numer Anal 49(3):815–837, 2015), which considered fixed and non-optimized downward closed multi-index sets. Potential applications of the proposed results are found in the development and analysis of efficient numerical methods for computing the solution of high-dimensional parametric or stochastic PDEs, but is not limited to this area.

MATHICSE Technical Report : Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

Giovanni Migliorati, Fabio Nobile

We analyze the accuracy of the discrete least-squares approximation of a function u in multivariate polynomial spaces

P_\Lambda := span\{y \mapsto y^\nu | \nu \in \Lambda\}

with

\Lambda\subset N_0^d

over the domain

\Gamma := [-1,1]^d

, based on the sampling of this function at points

y^1,...,y^m \in \Gamma

. The samples are independently drawn according to a given probability density

\rho

belonging to the class of multivariate beta densities, which includes the uniform and Chebyshev densities as particular cases. Motivated by recent results on high-dimensional parametric and stochastic PDEs, we restrict our attention to polynomial spaces associated with downward closed sets

\Lambda

of prescribed cardinality n and we optimize the choice of the space for the given sample. This implies in particular that the selected polynomial space depends on the sample. We are interested in comparing the error of this least-squares approximation measured in

L^2(\Gamma,\rho)

with the best achievable polynomial approximation error when using downward closed sets of cardinality n. We establish conditions between the dimension n and the size m of the sample, under which these two errors are proven to be comparable. Our main finding is that the dimension d enters only moderately in the resulting trade-off between m and n, in terms of a logarithmic factor ln(d), and is even absent when the optimization is restricted to a relevant subclass of downward closed sets, named anchored sets. In principle, this allows one to use these methods in arbitrarily high or even infinite dimension. Our analysis builds upon [3] which considered fixed and non-optimized downward closed multi-index sets. Potential applications of the proposed results are found in the development and analysis of efficient numerical methods for computing the solution of high-dimensional parametric or stochastic PDEs, but is not limited to this area.

MATHICSE2015

Adaptive polynomial approximation by means of random discrete least squares

Giovanni Migliorati

We address adaptive multivariate polynomial approximation by means of the discrete least-squares method with random evaluations, to approximate in the L2 probability sense a smooth function depending on a random variable distributed according to a given probability density. The polynomial least-squares approximation is computed using random noiseless pointwise evaluations of the target function. Here noiseless means that the pointwise evaluation of the function is not polluted by the presence of noise. Recent works Migliorati et al. (Found Comput Math 14:419–456, 2014), Cohen et al. (Found Comput Math 13:819–834, 2013), and Chkifa et al. (Discrete least squares polynomial approximation with random evaluations – application to parametric and stochastic elliptic PDEs, EPFL MATHICSE report 35/2013, submitted) have analyzed the univariate and multivariate cases, providing error estimates for (a priori) given sequences of polynomial spaces. In the present work, we apply the results developed in the aforementioned analyses to devise adaptive least-squares polynomial approximations. We build a sequence of quasi-optimal best n-term sets to approximate multivariate functions that feature strong anisotropy in moderately high dimensions. The adaptive approximation relies on a greedy selection of basis functions, which preserves the downward closedness property of the polynomial approximation space. Numerical results show that the adaptive approximation is able to catch effectively the anisotropy in the function.

Springer2015

Approximation of Quantities of Interest in Stochastic PDEs by the Random Discrete $L^2$ Projection on Polynomial Spaces

Giovanni Migliorati, Fabio Nobile, Erik Gustaf Bogislaw Von Schwerin

In this work we consider the random discrete

L^2

projection on polynomial spaces (hereafter RDP) for the approximation of scalar quantities of interest (QOIs) related to the solution of a partial differential equation model with random input parameters. In the RDP technique the QOI is first computed for independent samples of the random input parameters, as in a standard Monte Carlo approach, and then the QOI is approximated by a multivariate polynomial function of the input parameters using a discrete least squares approach. We consider several examples including the Darcy equations with random permeability, the linear elasticity equations with random elastic coefficient, and the Navier--Stokes equations in random geometries and with random fluid viscosity. We show that the RDP technique is well suited to QOIs that depend smoothly on a moderate number of random parameters. Our numerical tests confirm the theoretical findings in [G. Migliorati, F. Nobile, E. von Schwerin, and R. Tempone, Analysis of the Discrete

L^2

Projection on Polynomial Spaces with Random Evaluations, MOX report 46-2011, Politecnico di Milano, Milano, Italy, submitted], which have shown that, in the case of a single uniformly distributed random parameter, the RDP technique is stable and optimally convergent if the number of sampling points is proportional to the square of the dimension of the polynomial space. Here optimality means that the weighted

L^2

norm of the RDP error is bounded from above by the best

L^\infty

error achievable in the given polynomial space, up to logarithmic factors. In the case of several random input parameters, the numerical evidence indicates that the condition on quadratic growth of the number of sampling points could be relaxed to a linear growth and still achieve stable and optimal convergence. This makes the RDP technique very promising for moderately high dimensional uncertainty quantification.

Siam Publications2013