Fast and Robust Algorithms for Signal Recovery from Underdetermined Measurements: Generalized Sparse Fourier Transforms, Inverse Problems, and Density Estimation

Michigan State University, East Lansing MI

Investigators

Abstract

This project aims to develop computational methods capable of quickly generating best-possible simple solutions for several difficult computational problems of wide interest. As an example, the developed computational methods will include an algorithm for rapidly finding the best possible simple approximation of a given function of many variables from just a few function evaluations. If, e.g., the function one cares about is the probability of having an extreme rain event in Florida in two weeks as a function of current ocean temperatures, wind speeds, atmospheric pressures, etc. then such a method could help to provide a generic framework for quickly building up simple models to help predict such extreme rain events based on a reduced number of costly weather observations and climate simulations. A second example of the numerical methods to be developed as part of this project include provably accurate methods for producing correct pictures of, e.g., microscopic material features from realistic ptychographic imaging data. Such methods can help guarantee that the images one can obtain using well-planned ptychographic scans of microscopic object features (that are too small to see with the naked eye) actually look like the true object one scanned as opposed to, e.g., a distorted, fake, or even disguised version of the true object which just so happens to produce similar scan results. More generally, this project will develop fast computational methods, supported by rigorous theoretical guarantees, for several problems that involve learning extremely large and high dimensional signals from severely underdetermined measurements. The developed numerical methods will include: (i) improved and generalized sublinear-time Sparse Fourier Transform (SFT) algorithms capable of rapidly approximating any function of many variables that exhibits sparsity in any given bounded orthonormal product basis, (ii) FFT-time and provably accurate lifted phase retrieval algorithms for approximately recovering compactly supported functions (up to a global phase factor) from their spectrogram measurements as well as new and even faster SFT-based compressive phase retrieval methods which run in only sublinear-time, and (iii) the development of new, fast, low-memory, and highly-parallel distributed density estimation algorithms for large multimodal datasets and tensors. A common difficulty in developing all three sets of algorithms for the problems above stems from the shear size of the memory and/or processing power required by their standard solution approaches, which limits both their applicability as well as one's ability to obtain fully determined sets of signal measurements for their use in many settings. In all three cases, new and computationally tractable algorithms will be developed that take advantage of hidden simplifying structure in each application above (e.g., generalized Fourier sparsity in the first case, intrinsically low rank data in the second case, and intrinsic low-dimensional geometric structure in the third) thereby providing numerical approaches capable of solving several types of large problems whose numerical solution currently lies beyond our collective capabilities. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.