We show how, the discovery/design of robust scalable numerical solvers for arbitrary bounded linear operators, can, to some degree, be addressed/automated as a Game/Decision 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, $\mathcal{B}$, is a Banach space endowed with a quadratic norm $\|\cdot\|$, optimal mixed and pure strategies coincide and are obtained by conditioning Gaussian fields on $\mathcal{B}$ with respect to computable information and elementary gambles/bets (gamblets) form a multi-resolution basis of $\mathcal{B}$. These gamblets generalize the notion of Wavelets and Wannier basis functions in the sense that they are adapted to the norm $\|\cdot\|$ and induce a multi-resolution decomposition of $\mathcal{B}$ that is adapted to the eigensubspaces of the operator $Q: \mathcal{B}^* \rightarrow \mathcal{B}$ defining the norm $\|\cdot\|$. 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 bounded linear operator (which include arbitrary bounded invertible differential operators mapping $H^s_0(\Omega)$ to $H^{-s}(\Omega)$ or $H^s_0(\Omega)$ to $L^2(\Omega)$) into a sequence of independent linear systems with uniformly bounded condition numbers and leads to $\mathcal{O}(N \operatorname{polylog}(N))$ solvers and eigenspace adapted MRA (resulting in near linear complexity PCA, SVD, active subspace decomposition, etc...).
Copyright. All Rights Reserved.