CIF: Small: Optimal Iterative Estimation in Signal Processing, Information Theory and Machine Learning

CIF：小：信号处理、信息论和机器学习中的最优迭代估计

• 批准号: 1319979
• 负责人: Andrea Montanari
• 金额: $ 41.62万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-06-01 至 2018-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319979&HistoricalAwards=false
• 关键词: CIF; Small; Optimal; Iterative; Estimation

Modern imaging devices, sensors, data acquisition systems allow to gather data with unprecedented speed andaccuracy. Most of the times, however, we are not interested in accumulating data per se, but rather touncover some hidden patterns in the data. For instance, given a large network, we might want to discover a small subset of notes that are tightly connected to each other. Such highly connected substructuresare of interest in biological datasets, but also in social network analysis, and in signal processing. Finding such patterns requires highly efficient algorithms that can process large amount of data anduncover tenuous statistical signatures. The investigators develop new algorithms that simultaneously optimizeboth metrics: statistical efficiency and computational efficiency.Consider in particular the problem of finding an anomalous submatrix in a large data matrix with independent random entries. If the anomalous submatrix has entries with a different distribution, this can be done via principal component analysis, as long as the submatrix has dimensions of the order of the square root ofthe ambient dimensions. The investigators introduce a class of first order methods with linear complexity,and determine the optimal algorithm within this class. This appears to provably outperform existing approaches. The same framework is generalized to several other classes of high-dimensional estimation problems. Optimal iterative procedures are developed under strict computational constraints.

现代成像设备、传感器、数据采集系统能够以前所未有的速度和精度收集数据。然而，大多数时候，我们对积累数据本身并不感兴趣，而是发现数据中隐藏的一些模式。例如，给定一个大型网络，我们可能希望发现彼此紧密连接的音符的一个小子集。这种高度连接的子结构不仅在生物数据集中很有意义，而且在社会网络分析和信号处理中也很有意义。找到这样的模式需要高效的算法，可以处理大量的数据和发现脆弱的统计特征。研究人员开发了新的算法，同时优化这两个指标：统计效率和计算效率。特别考虑在一个大的数据矩阵中找到一个异常的子矩阵与独立的随机条目的问题。如果异常子矩阵有不同分布的条目，这可以通过主成分分析来完成，只要子矩阵的维度是环境维度的平方根的数量级。研究者引入了一类具有线性复杂度的一阶方法，并确定了该类方法的最优算法。这似乎证明优于现有的方法。同样的框架推广到其他几类高维估计问题。在严格的计算约束条件下，最佳的迭代程序。

项目成果

How well do local algorithms solve semidefinite programs?

局部算法求解半定程序的效果如何？

• DOI: 10.1145/3055399.3055451
• 发表时间: 2017
• 期刊: STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Fan, Zhou;Montanari, Andrea
• 通讯作者: Montanari, Andrea