Spectral regularization algorithms for learning large incomplete matrices. (English) Zbl 1242.68237

Summary: 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 of order linear in the matrix dimensions. Our semidefinite-programming algorithm is readily scalable to large matrices; for example SOFT-IMPUTE takes a few hours to compute low-rank approximations of a \(10^{6}\times 10^{6}\) incomplete matrix with \(10^{7}\) observed entries, and fits a rank-\(95\) approximation to the full Netflix training set in \(3.3\) hours. Our methods achieve good training and test errors and exhibit superior timings when compared to other competitive state-of-the-art techniques.


68T05 Learning and adaptive systems in artificial intelligence
62H12 Estimation in multivariate analysis
15A83 Matrix completion problems
90C25 Convex programming
Full Text: Link