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

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

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.