论文标题
低级矩阵估计的快速梯度方法
Fast gradient method for Low-Rank Matrix Estimation
论文作者
论文摘要
预计的梯度下降及其Riemannian变体属于低级矩阵估计的典型方法。本文提出了一种新的Nesterov通过有效的拼字缩回和切线空间投影加速加速的Riemannian梯度算法。低级矩阵歧管上的迭代和推断序列之间的子空间关系提供了计算便利。通过对截短的奇异值分解和两次缩回的扰动分析，我们系统地分析了欧几里得和里曼尼亚设置中梯度算法和Nesterov变体的局部收敛性。从理论上讲，我们使用光谱半径以封闭形式估算不同参数下局部线性收敛的确切速率，并给出最佳收敛速率和相应的动量参数。当参数未知时，自适应重新启动方案可以避免高动量引起的振荡问题，从而接近最佳收敛速率。广泛的数值实验证实了收敛速率的估计，并证明所提出的算法具有具有矩阵完成和矩阵传感的一阶方法的竞争力。
Projected gradient descent and its Riemannian variant belong to a typical class of methods for low-rank matrix estimation. This paper proposes a new Nesterov's Accelerated Riemannian Gradient algorithm by efficient orthographic retraction and tangent space projection. The subspace relationship between iterative and extrapolated sequences on the low-rank matrix manifold provides a computational convenience. With perturbation analysis of truncated singular value decomposition and two retractions, we systematically analyze the local convergence of gradient algorithms and Nesterov's variants in the Euclidean and Riemannian settings. Theoretically, we estimate the exact rate of local linear convergence under different parameters using the spectral radius in a closed form and give the optimal convergence rate and the corresponding momentum parameter. When the parameter is unknown, the adaptive restart scheme can avoid the oscillation problem caused by high momentum, thus approaching the optimal convergence rate. Extensive numerical experiments confirm the estimations of convergence rate and demonstrate that the proposed algorithm is competitive with first-order methods for matrix completion and matrix sensing.
