Quoc T. Le Gia

Josef Dick, Frances Y. Kuo, Quoc T. Le Gia et al.

We construct quasi-Monte Carlo methods to approximate the expected values of linear functionals of Galerkin discretizations of parametric operator equations which depend on a possibly infinite sequence of parameters. Such problems arise in the numerical solution of differential and integral equations with random field inputs. We analyze the regularity of the solutions with respect to the parameters in terms of the rate of decay of the fluctuations of the input field. If $p\in (0,1]$ denotes the "summability exponent" corresponding to the fluctuations in affine-parametric families of operators, then we prove that deterministic "interlaced polynomial lattice rules" of order $α= \lfloor 1/p \rfloor+1$ in $s$ dimensions with $N$ points can be constructed using a fast component-by-component algorithm, in $\mathcal{O}(α\,s\, N\log N + α^2\,s^2 N)$ operations, to achieve a convergence rate of $\mathcal{O}(N^{-1/p})$, with the implied constant independent of $s$. This dimension-independent convergence rate is superior to the rate $\mathcal{O}(N^{-1/p+1/2})$, for $2/3\leq p\leq 1$ recently established for randomly shifted lattice rules under comparable assumptions. In our analysis we use a non-standard Banach space setting and introduce "smoothness-driven product and order dependent (SPOD)" weights for which we show fast CBC construction.

Josef Dick, Robert N. Gantner, Quoc T. Le Gia et al.

We propose and analyze deterministic multilevel approximations for Bayesian inversion of operator equations with uncertain distributed parameters, subject to additive Gaussian measurement data. The algorithms use a multilevel (ML) approach based on deterministic, higher order quasi-Monte Carlo (HoQMC) quadrature for approximating the high-dimensional expectations, which arise in the Bayesian estimators, and a Petrov-Galerkin (PG) method for approximating the solution to the underlying partial differential equation (PDE). This extends the previous single-level approach from [J. Dick, R. N. Gantner, Q. T. Le Gia and Ch. Schwab, Higher order Quasi-Monte Carlo integration for Bayesian Estimation. Report 2016-13, Seminar for Applied Mathematics, ETH Zürich (in review)]. We obtain sufficient conditions which allow us to achieve arbitrarily high, algebraic convergence rates in terms of work, which are independent of the dimension of the parameter space. The convergence rates are limited only by the spatial regularity of the forward problem,the discretization order achieved by the Petrov Galerkin discretization, and by the sparsity of the uncertainty parametrization. We provide detailed numerical experiments for linear elliptic problems in two space dimensions, with $s=1024$ parameters characterizing the uncertain input, confirming the theory and showing that the ML HoQMC algorithms outperform, in terms of error vs.~computational work, both multilevel Monte Carlo (MLMC) methods and single-level (SL) HoQMC methods.

Josef Dick, Robert N. Gantner, Quoc T. Le Gia et al.

We analyze combined Quasi-Monte Carlo quadrature and Finite Element approximations in Bayesian estimation of solutions to countably-parametric operator equations with holomorphic dependence on the parameters as considered in [Cl.~Schillings and Ch.~Schwab: Sparsity in Bayesian Inversion of Parametric Operator Equations. Inverse Problems, {\bf 30}, (2014)]. Such problems arise in numerical uncertainty quantification and in Bayesian inversion of operator equations with distributed uncertain inputs, such as uncertain coefficients, uncertain domains or uncertain source terms and boundary data. We show that the parametric Bayesian posterior densities belong to a class of weighted Bochner spaces of functions of countably many variables, with a particular structure of the QMC quadrature weights: up to a (problem-dependent, and possibly large) finite dimension $S$ product weights can be used, and beyond this dimension, weighted spaces with so-called SPOD weights are used to describe the solution regularity. We establish error bounds for higher order Quasi-Monte Carlo quadrature for the Bayesian estimation based on [J.~Dick, Q.T.~LeGia and Ch.~Schwab, Higher order Quasi-Monte Carlo integration for holomorphic, parametric operator equations, Report 2014-23, SAM, ETH Zürich]. It implies, in particular, regularity of the parametric solution and of the countably-parametric Bayesian posterior density in SPOD weighted spaces. This, in turn, implies that the Quasi-Monte Carlo quadrature methods in [J. Dick, F.Y.~Kuo, Q.T.~Le Gia, D.~Nuyens, Ch.~Schwab, Higher order QMC Galerkin discretization for parametric operator equations, SINUM (2014)] are applicable to these problem classes, with dimension-independent convergence rates $\calO(N^{-1/p})$ of $N$-point HoQMC approximated Bayesian estimates, where $0<p<1$ depends only on the sparsity class of the uncertain input in the Bayesian estimation.

Yu Guang Wang, Quoc T. Le Gia, Ian H. Sloan et al.

Spherical needlets are highly localized radial polynomials on the sphere $\mathbb{S}^{d}\subset \mathbb{R}^{d+1}$, $d\ge 2$, with centers at the nodes of a suitable cubature rule. The original semidiscrete spherical needlet approximation of Narcowich, Petrushev and Ward is not computable, in that the needlet coefficients depend on inner product integrals. In this work we approximate these integrals by a second quadrature rule with an appropriate degree of precision, to construct a fully discrete needlet approximation. We prove that the resulting approximation is equivalent to filtered hyperinterpolation, that is to a filtered Fourier-Laplace series partial sum with inner products replaced by appropriate cubature sums. It follows that the $\mathbb{L}_{p}$-error of discrete needlet approximation of order $J$ for $1 \le p \le \infty$ and $s > d/p$ has for a function $f$ in the Sobolev space $\mathbb{W}_{p}^{s}(\mathbb{S}^{d})$ the optimal rate of convergence in the sense of optimal recovery, namely $\mathcal{O}\bigl(2^{-J s}\bigr)$. Moreover, this is achieved with a filter function that is of smoothness class $C^{\lfloor \frac{d+3}{2}\rfloor}$, in contrast to the usually assumed $C^{\infty}$. A numerical experiment for a class of functions in known Sobolev smoothness classes gives $\mathbb{L}_2$ errors for the fully discrete needlet approximation that are almost identical to those for the original semidiscrete needlet approximation. Another experiment uses needlets over the whole sphere for the lower levels together with high-level needlets with centers restricted to a local region. The resulting errors are reduced in the local region away from the boundary, indicating that local refinement in special regions is a promising strategy.

Josef Dick, Frances Y. Kuo, Quoc T. Le Gia et al.

Quasi-Monte Carlo (QMC) rules $1/N \sum_{n=0}^{N-1} f(\boldsymbol{y}_n A)$ can be used to approximate integrals of the form $\int_{[0,1]^s} f(\boldsymbol{y} A) \,\mathrm{d} \boldsymbol{y}$, where $A$ is a matrix and $\boldsymbol{y}$ is row vector. This type of integral arises for example from the simulation of a normal distribution with a general covariance matrix, from the approximation of the expectation value of solutions of PDEs with random coefficients, or from applications from statistics. In this paper we design QMC quadrature points $\boldsymbol{y}_0, ..., \boldsymbol{y}_{N-1} \in [0,1]^s$ such that for the matrix $Y = (\boldsymbol{y}_{0}^\top, ..., \boldsymbol{y}_{N-1}^\top)^\top$ whose rows are the quadrature points, one can use the fast Fourier transform to compute the matrix-vector product $Y \boldsymbol{a}^\top$, $\boldsymbol{a} \in \mathbb{R}^s$, in $\mathcal{O}(N \log N)$ operations and at most $s-1$ extra additions. The proposed method can be applied to lattice rules, polynomial lattice rules and a certain type of Korobov $p$-set. The approach is illustrated computationally by three numerical experiments. The first test considers the generation of points with normal distribution and general covariance matrix, the second test applies QMC to high-dimensional, affine-parametric, elliptic partial differential equations with uniformly distributed random coefficients, and the third test addresses Finite-Element discretizations of elliptic partial differential equations with high-dimensional, log-normal random input data. All numerical tests show a significant speed-up of the computation times of the fast QMC matrix method compared to a conventional implementation as the dimension becomes large.

Quoc T. Le Gia, Ian H. Sloan, Yu Guang Wang et al.

In this paper we establish a multiscale approximation for random fields on the sphere using spherical needlets --- a class of spherical wavelets. We prove that the semidiscrete needlet decomposition converges in mean and pointwise senses for weakly isotropic random fields on $\mathbb{S}^{d}$, $d\ge2$. For numerical implementation, we construct a fully discrete needlet approximation of a smooth $2$-weakly isotropic random field on $\mathbb{S}^{d}$ and prove that the approximation error for fully discrete needlets has the same convergence order as that for semidiscrete needlets. Numerical examples are carried out for fully discrete needlet approximations of Gaussian random fields and compared to a discrete version of the truncated Fourier expansion.

Quoc T. Le Gia, Ian H. Sloan, Robert S. Womersley et al.

This paper discusses sparse isotropic regularization for a random field on the unit sphere $\mathbb{S}^2$ in $\mathbb{R}^{3}$, where the field is expanded in terms of a spherical harmonic basis. A key feature is that the norm used in the regularization term, a hybrid of the $\ell_{1}$ and $\ell_2$-norms, is chosen so that the regularization preserves isotropy, in the sense that if the observed random field is strongly isotropic then so too is the regularized field. The Pareto efficient frontier is used to display the trade-off between the sparsity-inducing norm and the data discrepancy term, in order to help in the choice of a suitable regularization parameter. A numerical example using Cosmic Microwave Background (CMB) data is considered in detail. In particular, the numerical results explore the trade-off between regularization and discrepancy, and show that substantial sparsity can be achieved along with small $L_{2}$ error.

Yoshihito Kazashi, Quoc T. Le Gia

We investigate a discretization of a class of stochastic heat equations on the unit sphere with multiplicative noises. A spectral method is used for the spatial discretization and the truncation of the Wiener process, while an implicit Euler scheme with non-uniform steps is used for the temporal discretization. Some numerical experiments inspired by Earth's surface temperature data analysis GISTEMP provided by NASA are given.

Josef Dick, Quoc T. Le Gia, Christoph Schwab

We analyze the convergence of higher order Quasi-Monte Carlo (QMC) quadratures of solution-functionals to countably-parametric, nonlinear operator equations with distributed uncertain parameters taking values in a separable Banach space $X$ admitting an unconditional Schauder basis. Such equations arise in numerical uncertainty quantification with random field inputs. Unconditional bases of $X$ render the random inputs and the solutions of the forward problem countably parametric, deterministic. We show that these parametric solutions belong to a class of weighted Bochner spaces of functions of countably many variables, with a particular structure of the QMC quadrature weights: up to a (problem-dependent, and possibly large) finite dimension, product weights can be used, and beyond this dimension, weighted spaces with so-called SPOD weights recently introduced in [F.Y.~Kuo, Ch.~Schwab, I.H.~Sloan, Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients. SIAM J. Numer. Anal., 50, 3351--3374, 2012.] can be used to describe the solution regularity. The regularity results in the present paper extend those in [J. Dick, F.Y.~Kuo, Q.T.~Le Gia, D.~Nuyens, Ch.~Schwab, Higher order QMC (Petrov-)Galerkin discretization for parametric operator equations. SIAM J. Numer. Anal., 52, 2676 -- 2702, 2014.] established for affine parametric, linear operator families; they imply, in particular, efficient constructions of (sequences of) QMC quadrature methods there, which are applicable to these problem classes. We present a hybridized version of the fast component-by-component (CBC for short) construction of a certain type of higher order digital net.