Fast Algorithms via Compressed Moment Representations

Many high-dimensional or infinite-dimensional scientific computing problems can be effectively approximated by truncated moment expansions. However, a common challenge is that the resulting moments are often large, dense, and expensive to form or manipulate directly. This dissertation develops fast algorithms that address this challenge by constructing compressed moment representations to solve three computational problems. The first part of the thesis introduces a fast method of moments for ab initio cryo-electron microscopy reconstruction. We compress the first three statistical moments of the 2-D projection images of the unknown 3-D molecular structure using low-rank tensor decompositions and randomized numerical linear algebra, and solve the reduced moment matching problem via numerical optimization. The proposed method enables efficient ab initio reconstruction of molecular structures even in extremely low signal-to-noise regimes. The second part develops a fast moment-based approach for learning Markov operators that describe high-dimensional stochastic dynamics. By projecting the operator onto structured basis functions and exploiting compressible structures in the resulting moment matrices, we compress the operator and use it to achieve efficient prediction of time-dependent distributions and solution of boundary value problems. The final part of the thesis focuses on fast algorithms for boundary value problems arising from studying wave propagation with infinitely long interfaces, gratings, or obstacles, where the classical fast algorithms cannot be applied efficiently. Based on analytic continuation of certain special function identities, a new fast multipole method is developed for efficient evaluation of moment operators defined on complex-coordinate boundaries, allowing us to solve large-scale problems in two and three dimensions.