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

从噪声、非线性和不完整的观测中估计未知对象是数据科学中的一个基本问题。标准解决方案首先假设未知对象遵循结构化的数学表示，然后开发用于恢复表示参数的优化算法。此外，严格的分析表明，一些这样的算法在统计上是最优的。然而，尽管在统计理解方面取得了这些进步，但计算的作用却远没有得到很好的理解；在许多情况下，即使是最好的方法也会导致计算时间与数据大小的高次多项式成正比。因此，为了在涉及海量数据的应用中充分利用这些方法，需要新的算法方法。本研究项目介绍了在线性运行时间内学习结构化数据表示的新理论和计算工具。新的算法方法基于这样一种直觉，即如果答案仅仅是近似的，而不是精确的，则可以规避数据分析中遇到的具有挑战性的优化问题。在统计性能、近似质量和运行时间之间建立精确的权衡是重点。有了这种直觉，该项目解决了三个具体问题：(i)从非线性观测中重建信号和图像。从局部观测中恢复图形，例如线性草图或节点间距离测量。（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.