Spectral Regularization Algorithms for Learning Large Incomplete Matrices
Spectral Regularization Algorithms for Learning Large Incomplete Matrices
复制标题
DOI：
10.5555/1756006.1859931
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
R. Mazumder;T. Hastie;R. Tibshirani
中科院分区：
文献类型：
--
作者：
R. Mazumder;T. Hastie;R. Tibshirani
我们使用凸松弛技术提供了一个序列的正则化低秩解决方案的大型矩阵完成问题。使用核范数作为正则化，我们提供了一个简单的和非常有效的凸算法，最大限度地减少重建误差的核范数的约束。我们的算法软输入迭代替换丢失的元素与软阈值SVD得到的。通过热启动，这允许我们在正则化参数的值的网格上有效地计算解的整个正则化路径。我们的算法的计算密集的部分是在计算一个低秩的SVD的稠密矩阵。利用问题的结构，我们表明，该任务可以执行的复杂性线性矩阵维数。我们的半定编程算法很容易扩展到大型矩阵：例如，它可以在2.5小时内获得10（6）× 10（6）不完整矩阵的秩80近似，其中有10（5）个观察条目，并且可以在6.6小时内将秩40近似拟合到完整的Netflix训练集。我们的方法在训练和测试误差方面都表现出非常好的性能，与其他具有竞争力的最先进的技术相比。
We use convex relaxation techniques to provide a sequence of regularized low-rank solutions for large-scale matrix completion problems. Using the nuclear norm as a regularizer, we provide a simple and very efficient convex algorithm for minimizing the reconstruction error subject to a bound on the nuclear norm. Our algorithm Soft-Impute iteratively replaces the missing elements with those obtained from a soft-thresholded SVD. With warm starts this allows us to efficiently compute an entire regularization path of solutions on a grid of values of the regularization parameter. The computationally intensive part of our algorithm is in computing a low-rank SVD of a dense matrix. Exploiting the problem structure, we show that the task can be performed with a complexity linear in the matrix dimensions. Our semidefinite-programming algorithm is readily scalable to large matrices: for example it can obtain a rank-80 approximation of a 10(6) × 10(6) incomplete matrix with 10(5) observed entries in 2.5 hours, and can fit a rank 40 approximation to the full Netflix training set in 6.6 hours. Our methods show very good performance both in training and test error when compared to other competitive state-of-the art techniques.