Spectral Regularization Algorithms for Learning Large Incomplete Matrices

• Activity Number: 211
• Type: Invited
• Date/Time: Monday, August 2, 2010 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Rahul Mazumder*+ and Trevor Hastie and Rob Tibshirani
• Companies: Stanford University and Stanford University and Stanford University
• Keywords: recommender systems ; SVD ; missing data ; L1 regularization ; nuclear norm ; sparsity

Abstract

We develop efficient convex relaxations for large-scale (Netflix data sized) matrix completion. Assuming the underlying matrix is low-rank, we use a nuclear norm regularizer to provide a simple and very efficient convex algorithm for minimizing the reconstruction error. 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, which can be done very efficiently exploiting the problem structure. Our semidefinite-programming algorithm can fit a rank 60 approximation to the full Netflix training set in 9.7 hours. We propose extensions to the case where the underlying matrix has larger rank with sparse left and right singular vectors and develop efficient convex algorithms for the purpose.