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