Universal Scalable Robust Solvers from Computational Information Games and fast eigenspace adapted Multiresolution Analysis

Abstract

We show how the discovery of robust scalable numerical solvers for arbitrary bounded linear operators can be automated as a Game Theory problem by reformulating the process of computing with partial information and limited resources as that of playing underlying hierarchies of adversarial information games. When the solution space is a Banach space $B$ endowed with a quadratic norm $\Vert \cdot \Vert$, the optimal measure (mixed strategy) for such games (e.g. the adversarial recovery of $u\in B$, given partial measurements $[{\varphi }_i,u]$ with ${\varphi }_i\in B^{\ast }$, using relative error in $\Vert \cdot \Vert$-norm as a loss) is a centered Gaussian field $\xi$ solely determined by the norm $\Vert \cdot \Vert$, whose conditioning (on measurements) produces optimal bets. When measurements are hierarchical, the process of conditioning this Gaussian field produces a hierarchy of elementary bets (gamblets). These gamblets generalize the notion of Wavelets and Wannier functions in the sense that they are adapted to the norm $\Vert \cdot \Vert$ and induce a multi-resolution decomposition of $B$ that is adapted to the eigensubspaces of the operator defining the norm $\Vert \cdot \Vert$. When the operator is localized, we show that the resulting gamblets are localized both in space and frequency and introduce the Fast Gamblet Transform (FGT) with rigorous accuracy and (near-linear) complexity estimates. As the FFT can be used to solve and diagonalize arbitrary PDEs with constant coefficients, the FGT can be used to decompose a wide range of continuous linear operators (including arbitrary continuous linear bijections from $H_0^s$ to $H^{-s}$ or to $L^2$) into a sequence of independent linear systems with uniformly bounded condition numbers and leads to $\mathcal{O}(N\mathrm{polylog}N)$ solvers and eigenspace adapted Multiresolution Analysis (resulting in near linear complexity approximation of all eigensubspaces).

142 pages. 14 Figures. Presented at AFOSR (Aug 2016), DARPA (Sep 2016), IPAM (Apr 3, 2017), Hausdorff (April 13, 2017) and ICERM (June 5, 2017)

References in corpus (5)

• An analysis of a class of variational multiscale methods based on subspace decomposition
• Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
• Quantum mechanics: The Bayesian theory generalised to the space of Hermitian matrices
• Computation of quasilocal effective diffusion tensors and connections to the mathematical theory of homogenization
• A sparse decomposition of low rank symmetric positive semi-definite matrices

Cited by in corpus (8)

• Kernel Flows: from learning kernels from data into the abyss
• Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
• Self-Powered Solar Aerial Vehicles: Towards Infinite Endurance UAVs
• On testing the simulation theory
• Accelerated scale bridging with sparsely approximated Gaussian learning
• Fast eigenpairs computation with operator adapted wavelets and hierarchical subspace correction
• A Fast Hierarchically Preconditioned Eigensolver Based On Multiresolution Matrix Decomposition
• Sparse operator compression of higher-order elliptic operators with rough coefficients