Spectral Regularization Algorithms for Learning Large Incomplete Matrices

By Rahul Mazumder, Trevor J. Hastie, Robert Tibshirani. 2010

1,467 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Mathematical Physics, Numerical Analysis, Optimization & Training, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Mathematical Physics

In Numerical Analysis

In Optimization & Training

In Probabilistic & Bayesian Methods

Citations in the corpus

PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, methodology): “Adding explicit spectral regularization has shown to further improve the performance of such models (Mazumder et al., 2010; Yoshida & Miyato, 2017).”
Recurrent Neural Networks for Multivariate Time Series with Missing Values (2016, neutral): “δ ← x x m [ ; ; ] (9) t n t n t n t n ( ) ( ) ( ) ( )”
Distributed optimization for multi-task learning via nuclear-norm approximation (2015, background): “The estimation of a low-rank matrix from a set of entries, or matrix completion, see, e.g., (Mazumder et al., 2010), also fits naturally in the framework of (6) with nuclearnorm regularization.”
Online linear optimization with the log-determinant regularizer (2017, background): “In this perspective, the policy class is formulated as a restricted set of matrices, say, the set of matrices of bounded trace norm, which is commonly used in collaborative filtering [7, 8, 9, 10].”
Speedup Matrix Completion with Side Information: Application to Multi-Label Learning (2013, methodology): “Several computational algorithms [10, 22, 23, 25, 27, 28, 39] have been developed to efficiently solve the optimization problem of matrix completion.”
Handbook of Big Data (2016, background): “This is known as the matrix completion problem and has been extensively investigated in the context of user recommendation systems (Cai et al., 2010; Mazumder et al., 2010).”
Deep Collaborative Filtering via Marginalized Denoising Auto-encoder (2015, methodology): “The decomposition can be carried out by a variety of methods ranging from SVD based approaches [19] to the relatively new non-negative matrix factorization approach [20].”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “The optimal B is computed efficiently by the SOFT-IMPUTE [260] algorithm and the outlier support S is estimated in polynomial time using graph-cut [38][199].”
A general and flexible method for signal extraction from single-cell RNA-seq data (2017, positive): “This solution is exact when K is at least equal to the rank of the solution of the unconstrained problem (8), which we solve with the softImpute::softImpute() function [51].”
NBER WORKING PAPER SERIES MATRIX COMPLETION METHODS FOR CAUSAL PANEL DATA MODELS (2018, positive): “studied by Mazumder et al. (2010), with the penalty factor λ chosen through crossvalidation that will be described at the end of this section.”
A note on the multiplicative gamma process (2016, methodology): “Examples include tensor factorization (Dunson and Xing, 2009), matrix decomposition (Mazumder et al., 2010), mixture modeling (Hjort et al., 2010) and factor analysis (Knowles and Ghahramani, 2011).”
Deep Partial Multi-View Learning (2020, background): “The missing views are basically blockwise and thus low-rank based completion [12], [13] is not applicable, as has been widely recognized in [5], [14].”
Understanding Alternating Minimization for Matrix Completion (2013, background): “There certainly has been progress on practical algorithms for solving related convex programs [7], [8], [9], [10], [11].”