A Caltech Library Service

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

Owhadi, Houman and Scovel, Clint (2017) Universal Scalable Robust Solvers from Computational Information Games and fast eigenspace adapted Multiresolution Analysis. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 ∥⋅∥, the optimal measure (mixed strategy) for such games (e.g. the adversarial recovery of u ∈ B, given partial measurements [ϕ_i,u] with ϕ_i ∈ B^∗, using relative error in ∥⋅∥-norm as a loss) is a centered Gaussian field ξ solely determined by the norm ∥⋅∥, 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 ∥⋅∥ and induce a multi-resolution decomposition of B that is adapted to the eigensubspaces of the operator defining the norm ∥⋅∥. 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^s_0 to H^(−s) or to L^2) into a sequence of independent linear systems with uniformly bounded condition numbers and leads to O(NpolylogN) solvers and eigenspace adapted Multiresolution Analysis (resulting in near linear complexity approximation of all eigensubspaces).

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Owhadi, Houman0000-0002-5677-1600
Scovel, Clint0000-0001-7757-3411
Additional Information:(Submitted on 31 Mar 2017 (v1), last revised 29 May 2017 (this version, v2)) The authors gratefully acknowledges this work supported by the Air Force Office of Scientific Research and the DARPA EQUiPS Program under award number FA9550-16-1-0054 (Computational Information Games).
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0054
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Record Number:CaltechAUTHORS:20170710-085210757
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78885
Deposited By: Ruth Sustaita
Deposited On:10 Jul 2017 16:35
Last Modified:03 Oct 2019 18:13

Repository Staff Only: item control page