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

CRII：CIF：走向结构化数据表示的线性时间计算

• 批准号: 1566281
• 负责人: Chinmay Hegde
• 金额: $ 17.33万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-04-15 至 2019-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1566281&HistoricalAwards=false
• 关键词: CRII; CIF; Towards; Linear; Time

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.

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