Learning Elliptic Partial Differential Equations with Randomized Linear Algebra

Abstract

Given input–output pairs of an elliptic partial differential equation (PDE) in three dimensions, we derive the first theoretically rigorous scheme for learning the associated Green’s function G. By exploiting the hierarchical low-rank structure of G, we show that one can construct an approximant to G that converges almost surely and achieves a relative error of O(Γϵ-1/2log3(1/ϵ)ϵ)$$\mathcal {O}(\varGamma _\epsilon ^{-1/2}\log ^3(1/\epsilon )\epsilon )$$ using at most O(ϵ-6log4(1/ϵ))$$\mathcal {O}(\epsilon ^{-6}\log ^4(1/\epsilon ))$$ input–output training pairs with high probability, for any 0<ϵ<1$$0<\epsilon <1$$. The quantity 0<Γϵ≤1$$0<\varGamma _\epsilon \le 1$$ characterizes the quality of the training dataset. Along the way, we extend the randomized singular value decomposition algorithm for learning matrices to Hilbert–Schmidt operators and characterize the quality of covariance kernels for PDE learning.