CRII: CIF: Towards Linear-Time Computation of Structured Data Representations

从噪声、非线性和不完整的观测中估计未知对象是数据科学中的一个基本问题。标准解决方案首先假设未知对象服从结构化的数学表示，然后开发用于恢复表示的参数的优化算法。此外，严格的分析表明，一些这样的算法是统计上最优的。然而，尽管在统计理解方面取得了这些进展，但计算的作用远没有得到很好的理解;在许多情况下，即使是最好的方法也会导致计算时间与数据大小的高次多项式成比例。因此，为了在涉及海量数据的应用中充分利用这些方法的优势，需要新的算法方法。这个研究项目介绍了新的理论和计算工具，用于在线性运行时间内学习结构化数据表示。新的算法方法是基于这样一种直觉，即如果答案仅仅是近似的，而不是精确的，那么在数据分析中遇到的具有挑战性的优化问题可以被规避。在统计性能、近似质量和运行时间之间建立精确的权衡是一个关键的焦点。基于这种直觉，该项目解决了三个具体问题：（i）从非线性观测中重建信号和图像。(ii)从部分观测恢复图形，如线性草图或节点间距离测量。(iii)从随机样本估计多维概率分布。在项目范围内开发的算法影响了医学成像、计算机网络监控、社交网络分析和无损评估（NDE）等应用。所有出版物、数据和源代码都是公开的。该项目涉及研究生和本科生的积极参与，并使他们接触到一系列领域，包括数学，统计学，计算机科学和优化。

Estimating an unknown object from noisy, nonlinear, and incomplete observations constitutes a basic problem in data science. Standard solutions first assume that the unknown object obeys a structured mathematical representation, and then develop optimization algorithms for recovering the parameters of the representation. Moreover, rigorous analysis reveals that several such algorithms are statistically optimal. However, despite these advances in statistical understanding, the role of computation is far less well understood; in many cases, even the best methods incur a computation time proportional to a high-degree polynomial in terms of the data size. Therefore, to reap the full benefits of these methods in applications involving massive data, new algorithmic approaches are necessary. This research project introduces new theory and computational tools for learning structured data representations in linear running time. The new algorithmic approaches are based on the intuition that challenging optimization problems encountered in data analysis can be circumvented if the answers are merely approximate, rather than exact. Establishing precise tradeoffs between statistical performance, approximation quality, and running time is a key focus. With this intuition, the project addresses three specific problems: (i) Reconstructing signals and images from nonlinear observations. (ii) Recovering graphs from partial observations, such as linear sketches or inter-node distance measurements. (iii) Estimating multidimensional probability distributions from random samples. Algorithms developed within the scope of the project impact applications ranging from medical imaging, computer network monitoring, social network analysis, and non-destructive evaluation (NDE). All publications, data, and source code are publicly available. The project involves the active participation of both graduate and undergraduate students, and exposes them to a span of areas including mathematics, statistics, computer science, and optimization.