Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares

By Trevor J. Hastie, Rahul Mazumder, Jason D. Lee, Reza Bosagh Zadeh. 2014

598 citations recorded by the source corpus.

The matrix-completion problem has attracted a lot of attention, largely as a result of the celebrated Netflix competition. Two popular approaches for solving the problem are nuclear-norm-regularized matrix approximation (Candès and Tao, 2009; Mazumder et al., 2010), and maximum-margin matrix factorization (Srebro et al., 2005). These two procedures are in some cases solving equivalent problems, but with quite different algorithms. In this article we bring the two approaches together, leading to an efficient algorithm for large matrix factorization and completion that outperforms both of these. We develop a software package softlmpute in R for implementing our approaches, and a distributed version for very large matrices using the Spark cluster programming environment

How researchers see this paper

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

Citations in the corpus

Principal Components and Regularized Estimation of Factor Models (2017, methodology): “As suggested in Hastie et al. (2015), the algorithm can be modiﬁed to construct robust principal components.”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “…4.1], for | (cid:2) | satisfying (27) with large enough C 0 , we have that with probability at least 1 − 1 /( 2 n 4 ) , P T P (cid:2) P T ( a ) − p P T ( a ) (cid:4) F ≤ 16 p (cid:4) a (cid:4) F (note that this bound holds uniformly for all a ∈ T , thus also holds when a is dependent on (cid:2) ).”
Contextual Bandits with Latent Confounders: An NMF Approach (2016, methodology): “Both these partially incomplete rating matrices are then completed using the Python package fancyimpute [22] using the default settings.”
Generalized Low Rank Models (2014, methodology): “The data matrix A is split entry-wise across many machines, just as in [HMLZ14].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Despite its popularity in practice [105], a clean analysis of the above update rule is still missing to date.”
Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems (2019, background): “Embedding-based approaches, such as matrix factorization (MF) [22, 28, 46] or neural collaborative ﬁltering (NCF) [15, 24] are among the most popular and eﬃcient solutions to matrix completion.”
Multivariate Time Series Imputation with Generative Adversarial Networks (2018, methodology): “The last kind of methods is machine learning based imputation algorithms [4, 19, 34].”
NBER WORKING PAPER SERIES MATRIX COMPLETION METHODS FOR CAUSAL PANEL DATA MODELS (2018, unknown): “The proof of this fact is provided in (Mazumder et al. (2010); Hastie et al. (2015)).”