CIF: Small: High-Dimensional Analysis of Stochastic Iterative Algorithms for Signal Estimation

CIF：小：信号估计随机迭代算法的高维分析

• 批准号: 1718698
• 负责人: Yue Lu
• 金额: $ 51.56万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1718698&HistoricalAwards=false
• 关键词: CIF; Small; Dimensional; Analysis; Stochastic

Optimization lies at the heart of modern signal and information processing. In recent years, the soaring quantity of information that is being acquired and becoming available makes computational and algorithmic issues increasingly important. This project contributes to an understanding of the fundamental limits of various stochastic optimization algorithms when dealing with high-dimensional data. Since such algorithms are the workhorse in many estimation, inference, and machine learning tasks, this research is well-posed to make significant and broad impact on many applications. Examples include real-time or low-latency medical image reconstructions, distributed computation on power grids, and the training of artificial neural networks for image understanding.In this project, the PI studies a family of efficient stochastic iterative algorithms for solving large-scale convex and nonconvex optimization problems that arise in various signal estimation tasks. The broad goal in this project is to analyze the exact dynamics of these stochastic iterative algorithms in the high-dimensional limit. This asymptotic analysis provides a complete characterization of the typical behavior of the algorithms. The theoretical investigation draws upon techniques from the statistical physics of mean-field interactive particle systems, the weak convergence theory of stochastic processes, signal processing, information theory, and optimization. The theoretical analysis can be used to clarify the effectiveness of such stochastic methods for large-scale optimization and to establish their fundamental performance bounds. The insights obtained from the analysis can also be used to guide the design of new scalable algorithms to achieve optimal trade-offs between estimation accuracy, sample complexity, and computational complexity.

优化是现代信号和信息处理的核心。近年来，信息量的激增使得计算和算法问题变得越来越重要。该项目有助于理解各种随机优化算法在处理高维数据时的基本限制。由于这些算法是许多估计，推理和机器学习任务中的主力，因此这项研究很好地对许多应用产生了重大而广泛的影响。例如，实时或低延迟医学图像重建、电网分布式计算以及用于图像理解的人工神经网络训练。在本项目中，PI研究了一系列有效的随机迭代算法，用于解决各种信号估计任务中出现的大规模凸和非凸优化问题。这个项目的主要目标是分析这些随机迭代算法在高维极限下的精确动力学。这种渐近分析提供了一个完整的表征的典型行为的算法。理论研究借鉴了平均场相互作用粒子系统的统计物理学，随机过程的弱收敛理论，信号处理，信息论和优化技术。理论分析可以用来阐明这种随机方法的有效性，为大规模优化，并建立其基本的性能界限。从分析中获得的见解也可以用来指导新的可扩展算法的设计，以实现估计精度，样本复杂性和计算复杂性之间的最佳权衡。

项目成果

A Modern Perspective on Streaming PCA and Subspace Tracking: The Missing Data Case

流式 PCA 和子空间跟踪的现代视角：丢失数据案例

• 发表时间: 2018
• 期刊: Proceedings of the IEEE
• 影响因子: 20.6
• 作者: Chi, Y.;Balzano, L;Lu, Y. M.
• 通讯作者: Lu, Y. M.

Fundamental limits of phasemax for phase retrieval: A replica analysis

• DOI: 10.1109/camsap.2017.8313210
• 发表时间: 2017-08
• 期刊: 2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)
• 作者: Oussama Dhifallah;Yue M. Lu

Optimal Spectral Initialization for Signal Recovery With Applications to Phase Retrieval

• DOI: 10.1109/tsp.2019.2904918
• 发表时间: 2019-05-01
• 期刊: IEEE TRANSACTIONS ON SIGNAL PROCESSING
• 影响因子: 5.4
• 作者: Luo, Wangyu;Alghamdi, Wael;Lu, Yue M.
• 通讯作者: Lu, Yue M.

The scaling limit of high-dimensional online independent component analysis

• DOI: 10.1088/1742-5468/ab39d6
• 发表时间: 2017-10
• 期刊: Journal of Statistical Mechanics: Theory and Experiment
• 作者: Chuang Wang;Yue M. Lu

Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization

高维感知器中的泛化误差：用凸优化逼近贝叶斯误差

• 发表时间: 2020
• 期刊: Conference on Neural Information Processing Systems (NeurIPS
• 作者: Aubin, B;Lu, Y. M.;Krzakala, F;Zdeborova, L
• 通讯作者: Zdeborova, L