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

该项目旨在开发能够快速生成最佳可能的简单解决方案的几个困难的计算问题的广泛兴趣的计算方法。 作为一个例子，开发的计算方法将包括一个算法，用于快速找到一个给定的函数的许多变量的最佳可能的简单近似，从几个函数的评估。 如果，例如，人们关心的函数是作为当前海洋温度、风速、大气压力等的函数的在两周内在佛罗里达发生极端降雨事件的概率。那么这样的方法可以帮助提供用于快速建立简单模型的通用框架，以帮助基于减少数量的昂贵天气观测和气候模拟来预测这种极端降雨事件。 作为本项目的一部分，将开发的数值方法的第二个例子包括可证明准确的方法，用于生成正确的图像，例如，从现实的重叠关联成像数据的微观材料特征。 这样的方法可以帮助保证可以使用微观物体特征（其太小而不能用肉眼看到）的精心规划的重叠关联扫描获得的图像实际上看起来像扫描的真实物体，而不是例如，一个扭曲的，假的，甚至伪装的真实物体的版本，恰好产生类似的扫描结果。 更一般地说，该项目将开发快速计算方法，支持严格的理论保证，涉及学习非常大和高维信号从严重欠定测量的几个问题。开发的数值方法将包括：（i）改进的和广义的次线性时间稀疏傅立叶变换（SFT）算法，其能够快速逼近在任何给定的有界正交归一化乘积基中表现出稀疏性的许多变量的任何函数，（ii）FFT时间和可证明准确的提升相位恢复算法，用于近似恢复compensator支持的函数（直到全局相位因子）以及新的甚至更快的基于SFT的压缩相位恢复方法，其仅在次线性时间内运行，以及（iii）新的、快速的、低存储器的开发，以及用于大型多模态数据集和张量的高度并行分布式密度估计算法。开发用于上述问题的所有三组算法的共同困难源于存储器的剪切大小和/或其标准解决方案方法所需的处理能力，这限制了它们的适用性以及获得完全确定的信号测量集以供它们在许多设置中使用的能力。在所有这三种情况下，将开发新的和计算上易处理的算法，这些算法利用上述每个应用中隐藏的简化结构（例如，在第一种情况下是广义傅立叶稀疏，在第二种情况下是固有低秩数据，和第三个中的内在低维几何结构）从而提供了能够解决几类大型问题的数值方法，这些问题的数值解目前超出了我们的集体能力。该奖项反映了NSF的法定使命，并通过利用基金会的智力价值进行评估，更广泛的影响审查标准。

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.