Cabos

Spectral Regularization Algorithms for Learning Large Incomplete Matrices
Rahul Mazumder
Department of Statistics Stanford University [e-mail]

Trevor Hastie
Statistics Department and Department of Health, Research and Policy Stanford University

[e-mail]

Robert Tibshirani
Department of Health, Research and Policy and Statistics Department Stanford University

[e-mail]

Editor: Submitted for publication July 30, 2009

Abstract
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 106 × 106 incomplete matrix with 105 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.

1. Introduction
In many applications measured data can be represented in a matrix Xm×n , for which only a relatively small number of entries are observed. The problem is to “complete” the matrix based on the observed entries, and has been dubbed the matrix completion problem [CCS08, CR08, RFP07,