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.