08:30
MS34: Randomized algorithms and parametrized PDE (Part 1)
Chair: Oliver Zahm
08:30
25 mins
|
Randomized Optimisation Algorithms for Large-scale PDE Inverse Problems
Fred Roosta
Abstract: PDE constrained optimization is an important ingredient for many inverse problems arising in scientific and engineering applications. Faced with the typical high-dimensional and large-scale nature of these problems, many of the classical and deterministic optimization algorithms might prove to be inefficient, if applicable at all. In this light, recent research efforts have been centred around designing variants which, by employing randomized approximations of the objective, its gradient and/or its Hessian, improve upon the cost-per-iteration, while maintaining the original iteration complexity. At the heart of these approximations lie randomized numerical linear algebra subroutines ranging from approximately computing the trace of an implicit matrix to evaluating matrix-matrix multiplications. In this talk, we will present an overview of several of these randomized approximation algorithms as they relate to devising highly-efficient optimization algorithms.
|
08:55
25 mins
|
A probabilistic view on sparse Cholesky factorization
Florian Schaefer, Tim J Sullivan, Matthias Katzfuß, Houman Owhadi
Abstract: In this talk we will explore how probabilistic interpretations of the well-known Cholesky factorization motivate novel, fast, and simple algorithms for classical problems in numerical analysis.
\newline
In the first part of the talk we show that many dense kernel matrices arising in statistics, machine learning, and scientific computing have almost sparse Cholesky factors, under a suitable elimination ordering that is motivated by the conditional near-independence of the associated Gaussian process.
By using recent results on operator adapted wavelets, we can prove rigorously that kernel matrices obtained from evaluations of Green's functions of elliptic boundary value problems at pairs of $N$ points in a domain $\Omega \subset \mathbb{R}^d$ have\ $\epsilon$-approximate Cholesky factors with $O(N\log(N)\log^d(N/\epsilon))$ nonzero entries, that can be computed in complexity $O(N\log^2(N)\log^{2d}(N/\epsilon))$ by standard zero fill-in incomplete Cholesky factorization.
\newline
In the second part of the talk we show that the problem of finding the best sparse approximate (in KL-divergence) inverse-Cholesky factor of a given positive definite matrix has a simple closed form solution, recovering algorithms that were used previously (without knowledge of their KL-optimality) in the fields of spatial statistics and sparse approximate inverses.
This allows us to compute $\epsilon$-approximate inverse-Cholesky factors of Green's matrices of elliptic boundary value problems in computational complexity $O(N\log^d(N/\epsilon))$ in space, and $O(N\log^{2d}(N/\epsilon))$ in time.
To the best of our knowledge, this is the best asymptotic complexity for this problem.
We conclude with a discussion of the practical advantages of the resulting algorithm, including its almost embarrassing parallelism.
|
09:20
25 mins
|
Error bounds for some approximate posterior measures in Bayesian inference
Han Cheng Lie, T.J. Sullivan, Aretha Teckentrup
Abstract: Many Bayesian inverse problems require evaluating a forward model, by solving a partial differential equation (PDE). In many applications however, the PDE is computationally expensive to solve. This motivated the development of computationally cheaper approximations of such forward models, with approximations based on Gaussian processes or kriging being typical examples. Until recently, the theoretical validation of such random approximations was lacking. The work of Stuart and Teckentrup (Math. Comput., 2017) partially addressed the need for rigorous convergence results, by establishing error bounds in the Hellinger metric for random approximate posterior measures that arise from the particular class of Gaussian process approximations. In this talk, we present error bounds that apply to a more general class of random approximations, and illustrate how the theory may be applied to problems that involve high-dimensional data and to parameter inference problems.
|
09:45
25 mins
|
High-Dimensional Estimators for Parametric Transport Maps
Ricardo Baptista, Olivier Zahm, Youssef Marzouk
Abstract: Transport maps characterize continuous and non-Gaussian probability distributions by coupling a reference and target density with a deterministic transformation. These maps can be computed quickly using convex optimization [Spantini et. al., 2018], and can be enriched in complexity to capture non-Gaussian features. However, estimating these nonlinear transformations in high-dimensions is challenging given few samples from the unknown target density. In this presentation we exploit sparse parametric structure to estimate certain classes of transport maps with a sample size that only scales logarithmically with the ambient dimension. Furthermore, we show that the resulting estimators for the approximate density have bounded Kullback-Leibler divergence. To minimize the estimation error in practice, we propose an algorithm that finds a rotation of the input variables followed by a sparse transport map via regularization. The numerical performance of this algorithm is presented on a series of test problems and datasets from non-Gaussian random fields and data assimilation problems.
|
|
