CIF: Medium: Collaborative Research: Nonconvex Optimization for High-Dimensional Signal Estimation: Theory and Fast Algorithms

高维信号估计在医学成像、视频和网络监控等各种工程和科学应用中具有重要的应用价值。同时保持统计和计算效率的评估程序具有很大的实用价值，这转化为患者需要花费更少的时间在医疗扫描仪上，更快地对网络攻击做出反应，以及处理非常大的数据集的能力。虽然许多信号估计任务自然而然地被描述为非凸优化问题，但现有的非凸方法的结果有几个基本的局限性，并且当前的技术状态仍然受限于何时、为什么以及哪些非凸方法对给定问题有效。这项研究的目标是显著加深和拓宽对高维信号估计的非凸优化的理解和应用。在这个项目中，研究人员将通过直接优化非凸的和潜在的非光滑的损失函数来研究高维信号估计，而不是诉诸于凸松弛。这项研究将探索信号估计中常见的非凸函数所共有的几何结构，并研究这些结构在决定算法收敛方面所起的基本作用。这些结果将被用作开发快速和可证明正确的算法的指南，用于估计具有物理诱导结构的高维信号和流数据观测下的高维信号。具体地说，研究计划包括三个主要方面：(1)了解重要的非凸损失曲面的几何结构，并表征它们对优化算法收敛的影响；(2)开发快速算法和相关的结构化低阶矩阵恢复理论；(3)设计新的在线算法，在流环境下具有时间和空间效率，具有检测和跟踪感兴趣的时变信号的能力。

High-dimensional signal estimation plays fundamental roles in various engineering and science applications, such as medical imaging, video and network surveillance. Estimation procedures that maintain both statistical and computational efficacy are of great practical value, which translate into desiderata such as less time patients need to spend in a medical scanner, faster response to cyber attacks, and capabilities to handle very large datasets. While a lot of signal estimation tasks are naturally formulated as nonconvex optimization problems, existing results for nonconvex methods have several fundamental limitations, and the current state of the art is still limited in terms of when, why and which nonconvex approaches are effective for a given problem. The goal of this research program is to significantly deepen and broaden the understanding and applications of nonconvex optimization for high-dimensional signal estimation.In this project, the investigators will study high-dimensional signal estimation via direct optimization of nonconvex, and potentially nonsmooth, loss functions, without resorting to convex relaxation. This research will explore geometric structures shared by nonconvex functions commonly encountered in signal estimation, and study the fundamental roles these structures play in determining the algorithmic convergence. These results will then be exploited as guidelines to develop fast and provably correct algorithms for estimating high-dimensional signals with physically induced structures and under streaming data observations. Specifically, the research program consists of three major thrusts: (1) understanding the geometric structures of important classes of nonconvex loss surfaces, and characterizing their impact on the convergence of optimization algorithms; (2) developing fast algorithms and the associated theory for the recovery of structured low-rank matrices; (3) designing new online algorithms that are time and space efficient under a streaming setting, with the capability of detecting and tracking the time-varying signals of interest.