An efficient gauss-newton algorithm for symmetric low-rank product matrix approximations
An efficient gauss-newton algorithm for symmetric low-rank product matrix approximations
复制标题
对称低秩乘积矩阵近似的高效高斯-牛顿算法
DOI：
10.1137/140971464
复制
发表时间：
2015
影响因子：
3.1
通讯作者：
Zhang Yin
中科院分区：
文献类型：
--
作者：
Liu Xin;Wen Zaiwen;Zhang Yin
我们推导并研究了计算对称低秩积$XX^{{T}}$的高斯—牛顿方法，其中$X \in{\mathbb{R}}^{n\乘以k}$对于$k<n$，在Frobenius范数中最接近给定的对称矩阵$ a \in{\mathbb{R}}^{n\乘以n}$。当$A=B^{{T}} B$（或$BB^{{T}} $）时，这个问题本质上简化为寻找$B$的截断奇异值分解。我们的高斯-牛顿方法具有特别简单的形式，当$k \ n$时，它与梯度方法具有相同的迭代复杂度阶，但在广泛的问题上可以显着更快。在本文中，我们证明了该算法的全局收敛性和$Q$线性收敛率，并对各种测试问题进行了数值实验，包括最近活跃的矩阵补全和鲁棒主成分分析领域的测试问题。数值结果表明，本文提出的算法在求解精度较高的应用问题时，比Krylov子空间方法具有明显的速度优势。
We derive and study a Gauss--Newton method for computing a symmetric low-rank product $XX^{{T}}$, where $X \in{\mathbb{R}}^{n\times k}$ for $k<n$, that is the closest to a given symmetric matrix $A \in{\mathbb{R}}^{n\times n}$ in Frobenius norm. When $A=B^{{T}} B$ (or $BB^{{T}} $), this problem essentially reduces to finding a truncated singular value decomposition of $B$. Our Gauss--Newton method, which has a particularly simple form, shares the same order of iteration-complexity as a gradient method when $k \ll n$, but can be significantly faster on a wide range of problems. In this paper, we prove global convergence and a $Q$-linear convergence rate for this algorithm and perform numerical experiments on various test problems, including those from recently active areas of matrix completion and robust principal component analysis. Numerical results show that the proposed algorithm is capable of providing considerable speed advantages over Krylov subspace methods on suitable application problems where hi...