Accelerated singular value thresholding for matrix completion
Accelerated singular value thresholding for matrix completion
复制标题
DOI：
10.1145/2339530.2339581
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
Yao Hu;Debing Zhang;Jun Liu;Jieping Ye;Xiaofei He
中科院分区：
文献类型：
--
作者：
Yao Hu;Debing Zhang;Jun Liu;Jieping Ye;Xiaofei He
从一个小的子集恢复一个大的矩阵是一个具有挑战性的问题，出现在许多真实的世界的应用，如推荐系统和图像修补。这些问题可以用公式表示为一般的矩阵完备化问题。奇异值保持（SVT）算法是一种简单有效的一阶矩阵补齐方法，用于恢复原始数据矩阵为低秩时的缺失值。SVT已成功应用于许多应用中。然而，当数据矩阵的大小很大时，SVT在计算上是昂贵的，这显著地限制了其适用性。本文提出了一种加速奇异值保持算法（ASVT），它将SVT的收敛速度从O（1/N）提高到O（1/N2），其中N是优化过程中的迭代次数。具体地说，核范数最小化问题的对偶问题的推导和自适应线搜索方案被引入到解决这个对偶问题。因此，可以很容易地从对偶问题的最优解中得到原问题的最优解。我们已经进行了一系列的实验上的合成数据集，距离矩阵数据集和大型电影评级数据集。实验结果证明了该算法的有效性和实用性。
Recovering a large matrix from a small subset of its entries is a challenging problem arising in many real world applications, such as recommender system and image in-painting. These problems can be formulated as a general matrix completion problem. The Singular Value Thresholding (SVT) algorithm is a simple and efficient first-order matrix completion method to recover the missing values when the original data matrix is of low rank. SVT has been applied successfully in many applications. However, SVT is computationally expensive when the size of the data matrix is large, which significantly limits its applicability. In this paper, we propose an Accelerated Singular Value Thresholding (ASVT) algorithm which improves the convergence rate from O(1/N) for SVT to O(1/N2), where N is the number of iterations during optimization. Specifically, the dual problem of the nuclear norm minimization problem is derived and an adaptive line search scheme is introduced to solve this dual problem. Consequently, the optimal solution of the primary problem can be readily obtained from that of the dual problem. We have conducted a series of experiments on a synthetic dataset, a distance matrix dataset and a large movie rating dataset. The experimental results have demonstrated the efficiency and effectiveness of the proposed algorithm.