NSF-BSF: Modern Techniques for Signal Reconstruction from Moments

现代科学应用产生了大量的测量，每一次测量都被多个误差源污染。值得注意的例子包括最先进的生物医学分子成像技术--例如使用冷冻电子显微镜、X射线自由电子激光和X射线结晶学的单粒子重建--这些技术产生了对药物设计过程至关重要的知识，并扩大了我们对生命机制的理解。拟议的研究将开发各种计算和数学工具，以处理和分析大规模和复杂的数据集。特别是，设计的算法将帮助研究人员从现代设备获取的数据中提取和分析信息，以充分发挥其潜力。一个具体的重点是建立一个坚实的理论框架，以解决这类数据集引起的数学挑战。用户友好的软件将在公共存储库中提供，供科学界使用。研究的第一部分研究了矩方法在科学和工程领域出现的各种模型中的应用。矩方法是一种处理和分析大规模数据集的有吸引力的计算技术。这一部分包括为具有内在代数结构的模型推导信息论极限和建立可证明的算法，例如，群和卷积作用，以及高噪声水平。研究的第二部分提出了从信号的矩恢复信号的数值技术，需要求解多项式方程组。该项目的新颖性在于开发了新的计算方法，配备了健全的数学理论，可以从信号的统计时刻恢复信号；重点是涉及大规模、高度损坏的数据集的问题。这项研究将为突出的信号和图像处理任务提供各种容噪解决方案，如对准、分类、检测、超分辨率和相位恢复。具体目标包括修改矩方法以支持具有离群值的海量和噪声数据集，开发从不变多项式和近似不变多项式中恢复信号的可伸缩计算方案，求解大型多项式方程组的数值方法，在极端噪声水平下为高维数据推导新的信息论界限，以及分析非凸优化算法。这些建议的方法有可能成为解决当今一些领先科学问题的领先技术。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Modern scientific applications produce an immense number of measurements, each contaminated by multiple sources of error. Notable examples include state-of-the-art technologies for imaging of biomedical molecules - such as single-particle reconstruction using cryo-electron microscopy, X-ray free-electron lasers, and X-ray crystallography - that produce vital knowledge to the process of drug design and expand our understanding of the mechanisms of life. The proposed research will develop various computational and mathematical tools to process and analyze massively large and complex datasets. In particular, the devised algorithms will assist researchers in extracting and analyzing information from data acquired by modern devices to exploit their full potential. A specific focus is given to establishing a solid theoretical framework to address the mathematical challenges arising from such datasets. User-friendly software will be made available in public repositories for the use of the scientific community.The first part of the research studies applications of the method of moments, an appealing computational technique to process and analyze massively large datasets, to a variety of models that appear in scientific and engineering fields. This part includes deriving information-theoretic limits and establishing provable algorithms for models with intrinsic algebraic structures, for example, group and convolution actions, and high noise levels. The second part of the research advances numerical techniques to recover signals from their moments, entailing solving systems of polynomial equations. The novelty of the project lies in the development of new computational methods, equipped with sound mathematical theory, to recover signals from their statistical moments; the focus is on problems that involve massively large, highly corrupted datasets. The study will provide a variety of noise-tolerant solutions for prominent signal and image processing tasks, such as alignment, classification, detection, super-resolution, and phase retrieval. Particular objectives include modifying the method of moments to sustain massive and noisy datasets with outliers, developing scalable computational schemes for recovering signals from invariant and approximately invariant polynomials, numerical methods for solving large systems of polynomial equations, deriving new information-theoretic bounds for high-dimensional data in extreme noise levels, and analyzing non-convex optimization algorithms. These proposed methods have the potential to become leading techniques for solving some of today's leading scientific problems.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.