Source author record

Christoph Schwab

Christoph Schwab appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

19works
7topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2023arXiv

Monte Carlo convergence rates for $k$th moments in Banach spaces

We formulate standard and multilevel Monte Carlo methods for the $k$th moment $\mathbb{M}^k_\varepsilon[ξ]$ of a Banach space valued random variable $ξ\colonΩ\to E$, interpreted as an element of the $k$-fold injective tensor product space $\otimes^k_\varepsilon E$. For the standard Monte Carlo estimator of $\mathbb{M}^k_\varepsilon[ξ]$, we prove the $k$-independent convergence rate $1-\frac{1}{p}$ in the $L_q(Ω;\otimes^k_\varepsilon E)$-norm, provided that (i) $ξ\in L_{kq}(Ω;E)$ and (ii) $q\in[p,\infty)$, where $p\in[1,2]$ is the Rademacher type of $E$. By using the fact that Rademacher averages are dominated by Gaussian sums combined with a version of Slepian's inequality for Gaussian processes due to Fernique, we moreover derive corresponding results for multilevel Monte Carlo methods, including a rigorous error estimate in the $L_q(Ω;\otimes^k_\varepsilon E)$-norm and the optimization of the computational cost for a given accuracy. Whenever the type of the Banach space $E$ is $p=2$, our findings coincide with known results for Hilbert space valued random variables. We illustrate the abstract results by three model problems: second-order elliptic PDEs with random forcing or random coefficient, and stochastic evolution equations. In these cases, the solution processes naturally take values in non-Hilbertian Banach spaces. Further applications, where physical modeling constraints impose a setting in Banach spaces of type $p<2$, are indicated.

preprint2022arXiv

Deep ReLU neural networks overcome the curse of dimensionality for partial integrodifferential equations

Deep neural networks (DNNs) with ReLU activation function are proved to be able to express viscosity solutions of linear partial integrodifferental equations (PIDEs) on state spaces of possibly high dimension $d$. Admissible PIDEs comprise Kolmogorov equations for high-dimensional diffusion, advection, and for pure jump Lévy processes. We prove for such PIDEs arising from a class of jump-diffusions on $\mathbb{R}^d$ that for any suitable measure $μ^d$ on $\mathbb{R}^d$ there exist constants $C,{\mathfrak{p}},{\mathfrak{q}}>0$ such that for every $\varepsilon \in (0,1]$ and for every $d\in \mathbb{N}$ the DNN $L^2(μ^d)$-expression error of viscosity solutions of the PIDE is of size $\varepsilon$ with DNN size bounded by $Cd^{\mathfrak{p}}\varepsilon^{-\mathfrak{q}}$. In particular, the constant $C>0$ is independent of $d\in \mathbb{N}$ and of $\varepsilon \in (0,1]$ and depends only on the coefficients in the PIDE and the measure used to quantify the error. This establishes that ReLU DNNs can break the curse of dimensionality (CoD for short) for viscosity solutions of linear, possibly degenerate PIDEs corresponding to suitable Markovian jump-diffusion processes. As a consequence of the employed techniques we also obtain that expectations of a large class of path-dependent functionals of the underlying jump-diffusion processes can be expressed without the CoD.

preprint2021arXiv

Multilevel approximation of Gaussian random fields: Covariance compression, estimation and spatial prediction

Centered Gaussian random fields (GRFs) indexed by compacta such as smooth, bounded Euclidean domains or smooth, compact and orientable manifolds are determined by their covariance operators. We consider centered GRFs given as variational solutions to coloring operator equations driven by spatial white noise, with an elliptic self-adjoint pseudodifferential coloring operator from the Hörmander class. This includes the Matérn class of GRFs as a special case. Using biorthogonal multiresolution analyses on the manifold, we prove that the precision and covariance operators, respectively, may be identified with bi-infinite matrices and finite sections may be diagonally preconditioned rendering the condition number independent of the dimension $p$ of this section. We prove that a tapering strategy by thresholding applied on finite sections of the bi-infinite precision and covariance matrices results in optimally numerically sparse approximations. That is, asymptotically only linearly many nonzero matrix entries are sufficient to approximate the original section of the bi-infinite covariance or precision matrix using this tapering strategy to arbitrary precision. The locations of these nonzero matrix entries are known a priori. The tapered covariance or precision matrices may also be optimally diagonally preconditioned. Analysis of the relative size of the entries of the tapered covariance matrices motivates novel, multilevel Monte Carlo (MLMC) oracles for covariance estimation, in sample complexity that scales log-linearly with respect to the number $p$ of parameters. In addition, we propose and analyze a novel compressive algorithm for simulating and kriging of GRFs. The complexity (work and memory vs. accuracy) of these three algorithms scales near-optimally in terms of the number of parameters $p$ of the sample-wise approximation of the GRF in Sobolev scales.

preprint2020arXiv

Space-time discontinuous Galerkin approximation of acoustic waves with point singularities

We develop a convergence theory of space-time discretizations for the linear, 2nd-order wave equation in polygonal domains $Ω\subset\mathbb{R}^2$, possibly occupied by piecewise homogeneous media with different propagation speeds. Building on an unconditionally stable space-time DG formulation developed in [Moiola, Perugia 2018], we (a) prove optimal convergence rates for the space-time scheme with local isotropic corner mesh refinement on the spatial domain, and (b) demonstrate numerically optimal convergence rates of a suitable \emph{sparse} space-time version of the DG scheme. The latter scheme is based on the so-called \emph{combination formula}, in conjunction with a family of anisotropic space-time DG-discretizations. It results in optimal-order convergent schemes, also in domains with corners, with a number of degrees of freedom that scales essentially like the DG solution of one stationary elliptic problem in $Ω$ on the finest spatial grid. Numerical experiments for both smooth and singular solutions support convergence rate optimality on spatially refined meshes of the full and sparse space-time DG schemes.

preprint2016arXiv

Higher order Quasi-Monte Carlo integration for Bayesian Estimation

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.

preprint2016arXiv

Multilevel higher order Quasi-Monte Carlo Bayesian Estimation

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.

preprint2016arXiv

Multilevel Quasi-Monte Carlo Methods for Lognormal Diffusion Problems

In this paper we present a rigorous cost and error analysis of a multilevel estimator based on randomly shifted Quasi-Monte Carlo (QMC) lattice rules for lognormal diffusion problems. These problems are motivated by uncertainty quantification problems in subsurface flow. We extend the convergence analysis in [Graham et al., Numer. Math. 2014] to multilevel Quasi-Monte Carlo finite element discretizations and give a constructive proof of the dimension-independent convergence of the QMC rules. More precisely, we provide suitable parameters for the construction of such rules that yield the required variance reduction for the multilevel scheme to achieve an $\varepsilon$-error with a cost of $\mathcal{O}(\varepsilon^{-θ})$ with $θ< 2$, and in practice even $θ\approx 1$, for sufficiently fast decaying covariance kernels of the underlying Gaussian random field inputs. This confirms that the computational gains due to the application of multilevel sampling methods and the gains due to the application of QMC methods, both demonstrated in earlier works for the same model problem, are complementary. A series of numerical experiments confirms these gains. The results show that in practice the multilevel QMC method consistently outperforms both the multilevel MC method and the single-level variants even for non-smooth problems.

preprint2015arXiv

Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations

We analyze the convergence of compressive sensing based sampling techniques for the efficient evaluation of functionals of solutions for a class of high-dimensional, affine-parametric, linear operator equations which depend on possibly infinitely many parameters. The proposed algorithms are based on so-called "non-intrusive" sampling of the high-dimensional parameter space, reminiscent of Monte-Carlo sampling. In contrast to Monte-Carlo, however, a functional of the parametric solution is then computed via compressive sensing methods from samples of functionals of the solution. A key ingredient in our analysis of independent interest consists in a generalization of recent results on the approximate sparsity of generalized polynomial chaos representations (gpc) of the parametric solution families, in terms of the gpc series with respect to tensorized Chebyshev polynomials. In particular, we establish sufficient conditions on the parametric inputs to the parametric operator equation such that the Chebyshev coefficients of the gpc expansion are contained in certain weighted $\ell_p$-spaces for $0<p\leq 1$. Based on this we show that reconstructions of the parametric solutions computed from the sampled problems converge, with high probability, at the $L_2$, resp. $L_\infty$ convergence rates afforded by best $s$-term approximations of the parametric solution up to logarithmic factors.

preprint2015arXiv

Compressive Space-Time Galerkin Discretizations of Parabolic Partial Differential Equations

We study linear parabolic initial-value problems in a space-time variational formulation based on fractional calculus. This formulation uses "time derivatives of order one half" on the bi-infinite time axis. We show that for linear, parabolic initial-boundary value problems on $(0,\infty)$, the corresponding bilinear form admits an inf-sup condition with sparse tensor product trial and test function spaces. We deduce optimality of compressive, space-time Galerkin discretizations, where stability of Galerkin approximations is implied by the well-posedness of the parabolic operator equation. The variational setting adopted here admits more general Riesz bases than previous work; in particular, no stability in negative order Sobolev spaces on the spatial or temporal domains is required of the Riesz bases accommodated by the present formulation. The trial and test spaces are based on Sobolev spaces of equal order $1/2$ with respect to the temporal variable. Sparse tensor products of multi-level decompositions of the spatial and temporal spaces in Galerkin discretizations lead to large, non-symmetric linear systems of equations. We prove that their condition numbers are uniformly bounded with respect to the discretization level. In terms of the total number of degrees of freedom, the convergence orders equal, up to logarithmic terms, those of best $N$-term approximations of solutions of the corresponding elliptic problems.

preprint2015arXiv

Fast QMC matrix-vector multiplication

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.

preprint2015arXiv

Higher order QMC Galerkin discretization for parametric operator equations

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.

preprint2015arXiv

Higher order Quasi-Monte Carlo integration for holomorphic, parametric operator equations

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.

preprint2015arXiv

Isotropic Gaussian random fields on the sphere: Regularity, fast simulation and stochastic partial differential equations

Isotropic Gaussian random fields on the sphere are characterized by Karhunen-Loève expansions with respect to the spherical harmonic functions and the angular power spectrum. The smoothness of the covariance is connected to the decay of the angular power spectrum and the relation to sample Hölder continuity and sample differentiability of the random fields is discussed. Rates of convergence of their finitely truncated Karhunen-Loève expansions in terms of the covariance spectrum are established, and algorithmic aspects of fast sample generation via fast Fourier transforms on the sphere are indicated. The relevance of the results on sample regularity for isotropic Gaussian random fields and the corresponding lognormal random fields on the sphere for several models from environmental sciences is indicated. Finally, the stochastic heat equation on the sphere driven by additive, isotropic Wiener noise is considered, and strong convergence rates for spectral discretizations based on the spherical harmonic functions are proven.

preprint2015arXiv

Multi-level higher order QMC Galerkin discretization for affine parametric operator equations

We develop a convergence analysis of a multi-level algorithm combining higher order quasi-Monte Carlo (QMC) quadratures with general Petrov-Galerkin discretizations of countably affine parametric operator equations of elliptic and parabolic type, extending both the multi-level first order analysis in [\emph{F.Y.~Kuo, Ch.~Schwab, and I.H.~Sloan, Multi-level quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficient} (in review)] and the single level higher order analysis in [\emph{J.~Dick, F.Y.~Kuo, Q.T.~Le~Gia, D.~Nuyens, and Ch.~Schwab, Higher order QMC Galerkin discretization for parametric operator equations} (in review)]. We cover, in particular, both definite as well as indefinite, strongly elliptic systems of partial differential equations (PDEs) in non-smooth domains, and discuss in detail the impact of higher order derivatives of {\KL} eigenfunctions in the parametrization of random PDE inputs on the convergence results. Based on our \emph{a-priori} error bounds, concrete choices of algorithm parameters are proposed in order to achieve a prescribed accuracy under minimal computational work. Problem classes and sufficient conditions on data are identified where multi-level higher order QMC Petrov-Galerkin algorithms outperform the corresponding single level versions of these algorithms. Numerical experiments confirm the theoretical results.

preprint2014arXiv

Efficient Resolution of Anisotropic Structures

We highlight some recent new delevelopments concerning the sparse representation of possibly high-dimensional functions exhibiting strong anisotropic features and low regularity in isotropic Sobolev or Besov scales. Specifically, we focus on the solution of transport equations which exhibit propagation of singularities where, additionally, high-dimensionality enters when the convection field, and hence the solutions, depend on parameters varying over some compact set. Important constituents of our approach are directionally adaptive discretization concepts motivated by compactly supported shearlet systems, and well-conditioned stable variational formulations that support trial spaces with anisotropic refinements with arbitrary directionalities. We prove that they provide tight error-residual relations which are used to contrive rigorously founded adaptive refinement schemes which converge in $L_2$. Moreover, in the context of parameter dependent problems we discuss two approaches serving different purposes and working under different regularity assumptions. For frequent query problems, making essential use of the novel well-conditioned variational formulations, a new Reduced Basis Method is outlined which exhibits a certain rate-optimal performance for indefinite, unsymmetric or singularly perturbed problems. For the radiative transfer problem with scattering a sparse tensor method is presented which mitigates or even overcomes the curse of dimensionality under suitable (so far still isotropic) regularity assumptions. Numerical examples for both methods illustrate the theoretical findings.

preprint2014arXiv

Multi-level quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients

Quasi-Monte Carlo (QMC) methods are applied to multi-level Finite Element (FE) discretizations of elliptic partial differential equations (PDEs) with a random coefficient, to estimate expected values of linear functionals of the solution. The expected value is considered as an infinite-dimensional integral in the parameter space corresponding to the randomness induced by the random coefficient. We use a multi-level algorithm, with the number of QMC points depending on the discretization level, and with a level-dependent dimension truncation strategy. In some scenarios, we show that the overall error is $\mathcal{O}(h^2)$, where $h$ is the finest FE mesh width, or $\mathcal{O}(N^{-1+δ})$ for arbitrary $δ>0$, where $N$ is the maximal number of QMC sampling points. For these scenarios, the total work is essentially of the order of one single PDE solve at the finest FE discretization level. The analysis exploits regularity of the parametric solution with respect to both the physical variables (the variables in the physical domain) and the parametric variables (the parameters corresponding to randomness). Families of QMC rules with "POD weights" ("product and order dependent weights") which quantify the relative importance of subsets of the variables are found to be natural for proving convergence rates of QMC errors that are independent of the number of parametric variables.

preprint2013arXiv

Complexity Analysis of Accelerated MCMC Methods for Bayesian Inversion

We study Bayesian inversion for a model elliptic PDE with unknown diffusion coefficient. We provide complexity analyses of several Markov Chain-Monte Carlo (MCMC) methods for the efficient numerical evaluation of expectations under the Bayesian posterior distribution, given data $δ$. Particular attention is given to bounds on the overall work required to achieve a prescribed error level $\varepsilon$. Specifically, we first bound the computational complexity of "plain" MCMC, based on combining MCMC sampling with linear complexity multilevel solvers for elliptic PDE. Our (new) work versus accuracy bounds show that the complexity of this approach can be quite prohibitive. Two strategies for reducing the computational complexity are then proposed and analyzed: first, a sparse, parametric and deterministic generalized polynomial chaos (gpc) "surrogate" representation of the forward response map of the PDE over the entire parameter space, and, second, a novel Multi-Level Markov Chain Monte Carlo (MLMCMC) strategy which utilizes sampling from a multilevel discretization of the posterior and of the forward PDE. For both of these strategies we derive asymptotic bounds on work versus accuracy, and hence asymptotic bounds on the computational complexity of the algorithms. In particular we provide sufficient conditions on the regularity of the unknown coefficients of the PDE, and on the approximation methods used, in order for the accelerations of MCMC resulting from these strategies to lead to complexity reductions over "plain" MCMC algorithms for Bayesian inversion of PDEs.}

preprint2013arXiv

Covariance structure of parabolic stochastic partial differential equations

In this paper parabolic random partial differential equations and parabolic stochastic partial differential equations driven by a Wiener process are considered. A deterministic, tensorized evolution equation for the second moment and the covariance of the solutions of the parabolic stochastic partial differential equations is derived. Well-posedness of a space-time weak variational formulation of this tensorized equation is established.