Rank-One Matrix Pursuit for Matrix Completion
Rank-One Matrix Pursuit for Matrix Completion
复制标题
DOI：
--
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Z. Wang;M. Lai;Zhaosong Lu;Wei Fan;H. Davulcu;Jieping Ye
中科院分区：
文献类型：
--
作者：
Z. Wang;M. Lai;Zhaosong Lu;Wei Fan;H. Davulcu;Jieping Ye
低阶矩阵补全在协同过滤、图像修复、微阵列数据填充等机器学习应用中得到了广泛的应用。然而，许多现有的算法不能扩展到大规模问题，因为它们涉及到计算奇异值分解。本文提出了一种高效的、可伸缩的矩阵补全算法。其核心思想是将著名的正交匹配追踪法从向量情形推广到矩阵情形。在每一次迭代中，我们追求由当前逼近残差的顶部奇异向量对生成的一阶矩阵基，并更新到当前迭代之前获得的所有一阶矩阵的权重。我们进一步提出了一种新的权重更新规则来降低时间和存储复杂度，使所提出的算法可扩展到大型矩阵。我们证明了所提算法的线性收敛性质。由于提出了矩阵基的构造和权值的估计，从而实现了快速收敛。我们在许多真实的大规模数据集上对所提出的算法进行了实证评估。结果表明，该算法在预测性能接近或更好的情况下，比现有的矩阵补全算法有更高的效率。
Low rank matrix completion has been applied successfully in a wide range of machine learning applications, such as collaborative filtering, image inpainting and Microarray data imputation. However, many existing algorithms are not scalable to large-scale problems, as they involve computing singular value decomposition. In this paper, we present an efficient and scalable algorithm for matrix completion. The key idea is to extend the well-known orthogonal matching pursuit from the vector case to the matrix case. In each iteration, we pursue a rank-one matrix basis generated by the top singular vector pair of the current approximation residual and update the weights for all rank-one matrices obtained up to the current iteration. We further propose a novel weight updating rule to reduce the time and storage complexity, making the proposed algorithm scalable to large matrices. We establish the linear convergence of the proposed algorithm. The fast convergence is achieved due to the proposed construction of matrix bases and the estimation of the weights. We empirically evaluate the proposed algorithm on many real-world large-scale datasets. Results show that our algorithm is much more efficient than state-of-the-art matrix completion algorithms while achieving similar or better prediction performance.