Learning Elliptic Partial Differential Equations with Randomized Linear Algebra
Nicolas Boullé, Alex Townsend
Abstract
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 $$\mathcal {O}(\varGamma _\epsilon ^{-1/2}\log ^3(1/\epsilon )\epsilon )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msubsup> <mml:mi>Γ</mml:mi> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msubsup> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>3</mml:mn> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>ϵ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> using at most $$\mathcal {O}(\epsilon ^{-6}\log ^4(1/\epsilon ))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>6</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>4</mml:mn> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>ϵ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> input–output training pairs with high probability, for any $$0<\epsilon <1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo><</mml:mo> <mml:mi>ϵ</mml:mi> <mml:mo><</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . The quantity $$0<\varGamma _\epsilon \le 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo><</mml:mo> <mml:msub> <mml:mi>Γ</mml:mi> <mml:mi>ϵ</mml:mi> </mml:msub> <mml:mo>≤</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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.