Low-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence
Low-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence
复制标题
DOI：
10.1007/s10208-020-09490-9
复制
发表时间：
2021-01-28
影响因子：
3
通讯作者：
Drusvyatskiy, Dmitriy
中科院分区：
文献类型：
--
作者：
Charisopoulos, Vasileios;Chen, Yudong;Drusvyatskiy, Dmitriy
从其嘈杂的线性测量中恢复低级矩阵的任务在计算科学中起着核心作用。该问题的平滑表述通常表现出不希望的现象：经典定义的状况数在环境空间的尺寸下缩放较差。相比之下，我们在这里表明，在各种具体情况下，非平滑的惩罚表述不会遭受相同类型的弊端。因此，当在解决方案的恒定相对误差中初始初始化时，用于非平滑优化的标准算法（例如亚级别和代理线性方法）以快速尺寸独立的速率收敛。此外，非平滑配方自然对异常值具有强大的稳健性。我们的框架包含了重要的计算任务，例如相位检索，盲卷积，二次传感，矩阵完成和鲁棒的PCA。关于这些问题的数值实验说明了所提出的方法的好处。
The task of recovering a low-rank matrix from its noisy linear measurements plays a central role in computational science. Smooth formulations of the problem often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension of the ambient space. In contrast, we here show that in a variety of concrete circumstances, nonsmooth penalty formulations do not suffer from the same type of ill-conditioning. Consequently, standard algorithms for nonsmooth optimization, such as subgradient and prox-linear methods, converge at a rapid dimension-independent rate when initialized within constant relative error of the solution. Moreover, nonsmooth formulations are naturally robust against outliers. Our framework subsumes such important computational tasks as phase retrieval, blind deconvolution, quadratic sensing, matrix completion, and robust PCA. Numerical experiments on these problems illustrate the benefits of the proposed approach.