## 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.

### MSC:

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

### Software:

softImpute; impute; PROPACK; SLEP
Full Text: