In this paper, we analyze a method known as polynomial frame approximation for approximating smooth, multivariate functions defined on irregular domains in @math dimensions, where @math can be arbitrary. This method is simple, and relies only on orthogonal polynomials on a bounding tensor-product domain. In particular, the domain of the function need not be known in advance. When restricted to a subdomain, an orthonormal basis is no longer a basis, but a frame. Numerical computations with frames present potential difficulties, due to the near-linear dependence of the finite approximation system. Nevertheless, well-conditioned approximations can be obtained via regularization; for instance, truncated singular value decompositions. We comprehensively analyze such approximations in this paper, providing error estimates for functions with both classical and mixed Sobolev regularity, with the latter being particularly suitable for higher-dimensional problems. We also analyze the sample complexity of the approximation for sample points chosen randomly according to a probability measure, providing estimates in terms of the Nikolskii-type inequality for the domain. For a large class of nontrivial domains, we show that the sample complexity for points drawn from the uniform measure is quadratic in the dimension of the polynomial space, independently of @math .
Our work also extends recent research on computing polynomial approximations of functions defined on high-dimensional tensor-product domains. This approach has received substantial interest recently, due to its applications in, notably, UQ. See @cite_45 @cite_17 @cite_42 @cite_13 @cite_34 @cite_18 @cite_1 @cite_15 and references therein. One particular consequence of our work is to show that an irregular domain (either known or unknown) is no barrier to polynomial approximation of high-dimensional functions. Note that polynomial approximations are frequently used in practical UQ studies even when the domain is non-tensorial (see @cite_4 @cite_25 and references therein). Our work therefore provides a theoretical basis for these approaches.
@cite_18 @cite_4 @cite_42 @cite_1 @cite_45 @cite_15 @cite_34 @cite_13 @cite_25 @cite_17
2056558085 2041509689 2963843310 2615290254 2026679679 2963798430 2256307465 2086684904
We propose a method for the approximation of solutions of PDEs with stochastic coefficients based on the direct, i.e., non-adapted, sampling of solutions. This sampling can be done by using any legacy code for the deterministic problem as a black box. The method converges in probability (with probabilistic error bounds) as a consequence of sparsity and a concentration of measure phenomenon on the empirical correlation between samples. We show that the method is well suited for truly high-dimensional problems. The numerical approximation of parametric partial differential equations D(u,y)=0 is a computational challenge when the dimension d of the parameter vector y is large, due to the so-called curse of dimensionality. It was recently shown in [1,2] that, for a certain class of elliptic PDEs with diffusion coefficients depending on the parameters in an affine manner, there exist polynomial approximations to the solution map y↦u(y) with an algebraic convergence rate that is independent of the parametric dimension d. The analysis in [1,2] used, however, the affine parameter dependence of the operator. The present paper proposes a strategy for establishing similar results for classes of parametric PDEs that do not necessarily fall in this category. Our approach is based on building an analytic extension z↦u(z) of the solution map on certain tensor product of ellipses in the complex domain, and using this extension to estimate the Legendre coefficients of u. The varying semi-axes lengths of the ellipses in each coordinate zj reflect the anisotropy of the solution map with respect to the corresponding parametric variables yj. This allows us to derive algebraic convergence rates for tensorized Legendre expansions in the case d=∞. We also show that such rates are preserved when using certain interpolation procedures, which is an instance of a non-intrusive method. As examples of parametric PDEs that are covered by this approach, we consider (i) elliptic diffusion equations with coefficients that depend on the parameter vector y in a not necessarily affine manner, (ii) parabolic diffusion equations with similar dependence of the coefficient on y, (iii) nonlinear, monotone parametric elliptic PDEs, and (iv) elliptic equations set on a domain that is parametrized by the vector y. We give general strategies that allow us to derive the analytic extension in a unified abstract way for all these examples, in particular based on the holomorphic version of the implicit function theorem in Banach spaces. We expect that this approach can be applied to a large variety of parametric PDEs, showing that the curse of dimensionality can be overcome under mild assumptions. Collocation has become a standard tool for approximation of parameter- ized systems in the uncertainty quantification (UQ) community. Techniques for least- squares regularization, compressive sampling recovery, and interpolatory reconstruc- tion are becoming standard tools used in a variety of applications. Selection of a col- location mesh is frequently a challenge, but methods that construct geometrically un- structured collocation meshes have shown great potential due to attractive theoretical properties and direct, simple generation and implementation. We investigate prop- erties of these meshes, presenting stability and accuracy results that can be used as guides for generating stochastic collocation grids in multiple dimensions. We consider the problem of reconstructing an unknown function f on a domain X from samples of f at n randomly chosen points with respect to a given measure źX. Given a sequence of linear spaces (Vm)m>0 with dim(Vm)=m≤n, we study the least squares approximations from the spaces Vm. It is well known that such approximations can be inaccurate when m is too close to n, even when the samples are noiseless. Our main result provides a criterion on m that describes the needed amount of regularization to ensure that the least squares method is stable and that its accuracy, measured in L2(X,źX), is comparable to the best approximation error of f by elements from Vm. We illustrate this criterion for various approximation schemes, such as trigonometric polynomials, with źX being the uniform measure, and algebraic polynomials, with źX being either the uniform or Chebyshev measure. For such examples we also prove similar stability results using deterministic samples that are equispaced with respect to these measures. Parametrized families of PDEs arise in various contexts such as inverse problems, control and optimization, risk assessment, and uncertainty quantification. In most of these applications, the number of parameters is large or perhaps even infinite. Thus, the development of numerical methods for these parametric problems is faced with the possible curse of dimensionality. This article is directed at (i) identifying and understanding which properties of parametric equations allow one to avoid this curse and (ii) developing and analyzing effective numerical methodd which fully exploit these properties and, in turn, are immune to the growth in dimensionality. The first part of this article studies the smoothness and approximability of the solution map, that is, the map @math where @math is the parameter value and @math is the corresponding solution to the PDE. It is shown that for many relevant parametric PDEs, the parametric smoothness of this map is typically holomorphic and also highly anisotropic in that the relevant parameters are of widely varying importance in describing the solution. These two properties are then exploited to establish convergence rates of @math -term approximations to the solution map for which each term is separable in the parametric and physical variables. These results reveal that, at least on a theoretical level, the solution map can be well approximated by discretizations of moderate complexity, thereby showing how the curse of dimensionality is broken. This theoretical analysis is carried out through concepts of approximation theory such as best @math -term approximation, sparsity, and @math -widths. These notions determine a priori the best possible performance of numerical methods and thus serve as a benchmark for concrete algorithms. The second part of this article turns to the development of numerical algorithms based on the theoretically established sparse separable approximations. The numerical methods studied fall into two general categories. The first uses polynomial expansions in terms of the parameters to approximate the solution map. The second one searches for suitable low dimensional spaces for simultaneously approximating all members of the parametric family. The numerical implementation of these approaches is carried out through adaptive and greedy algorithms. An a priori analysis of the performance of these algorithms establishes how well they meet the theoretical benchmarks. Uncertainty quantification in complex physical models is often challenged by the computational expense of these models. One often needs to operate under the assumption of sparsely available model simulations. This issue is even more critical when models include a large number of input parameters. This “curse of dimensionality,” in particular, leads to a prohibitively large number of basis terms in spectral methods for uncertainty quantification, such as polynomial chaos (PC) methods. In this work, we implement a PC-based surrogate model construction that “learns” and retains only the most relevant basis terms of the PC expansion, using sparse Bayesian learning. This dramatically reduces the dimensionality of the problem, making it more amenable to further analysis such as sensitivity or calibration studies. The model of interest is the community land model with about 80 input parameters, which also exhibits nonsmooth input-output behavior. We enhanced the methodology by a clustering and classifying procedure that leads to a piecewisePC surrogate thereby dealing with nonlinearity. We then obtain global sensitivity information for five outputs with respect to all input parameters using less than 10,000 model simulations—a very small number for an 80-dimensional input parameter space. Motivated by the numerical treatment of parametric and stochastic PDEs, we analyze the least-squares method for polynomial approximation of multivariate functions based on random sampling according to a given probability measure. Recent work has shown that in the univariate case, the least-squares method is quasi-optimal in expectation in [A. Cohen, M A. Davenport and D. Leviatan. Found. Comput. Math. 13 (2013) 819–834] and in probability in [G. Migliorati, F. Nobile, E. von Schwerin, R. Tempone, Found. Comput. Math. 14 (2014) 419–456], under suitable conditions that relate the number of samples with respect to the dimension of the polynomial space. Here “quasi-optimal” means that the accuracy of the least-squares approximation is comparable with that of the best approximation in the given polynomial space. In this paper, we discuss the quasi-optimality of the polynomial least-squares method in arbitrary dimension. Our analysis applies to any arbitrary multivariate polynomial space (including tensor product, total degree or hyperbolic crosses), under the minimal requirement that its associated index set is downward closed. The optimality criterion only involves the relation between the number of samples and the dimension of the polynomial space, independently of the anisotropic shape and of the number of variables. We extend our results to the approximation of Hilbert space-valued functions in order to apply them to the approximation of parametric and stochastic elliptic PDEs. As a particular case, we discuss “inclusion type” elliptic PDE models, and derive an exponential convergence estimate for the least-squares method. Numerical results confirm our estimate, yet pointing out a gap between the condition necessary to achieve optimality in the theory, and the condition that in practice yields the optimal convergence rate.