Matrix completion and low-rank SVD via fast alternating least squares

Trevor Hastie, Rahul Mazumder, Jason D. Lee, Reza ZadehJMLR 2015 · OpenReview

TL;DR

This paper introduces softImpute-ALS, a novel algorithm that unifies two popular matrix completion approaches (nuclear-norm regularization and maximum-margin matrix factorization) into a single, efficient framework. This new method significantly outperforms existing algorithms in terms of speed and scalability, particularly for large, incomplete matrices, and is made available as an R package.

What Problem Does This Paper Address?

Matrix completion, the task of filling in missing entries in a partially observed matrix, is a fundamental problem with applications ranging from recommender systems (like Netflix) to signal processing. Two prominent methods for this task are:

  1. Nuclear-norm regularization: This approach seeks a low-rank matrix that best explains the observed data, often formulated as a convex optimization problem.
  2. Maximum-margin matrix factorization (MMMF): This method frames the problem as finding low-rank factors (matrices A and B such that their product approximates the original matrix) and is typically solved using alternating minimization.

While both methods aim to find low-rank solutions, they employ distinct algorithms. The challenge addressed here is to bridge these two approaches, leveraging their strengths to create a more efficient and scalable algorithm for large-scale matrix completion. The paper also aims to provide a unified theoretical understanding of these methods.

Methods

The core contribution is the softImpute-ALS algorithm, which combines ideas from both nuclear-norm regularization and MMMF. It's built upon the alternating least squares (ALS) framework but incorporates "soft-thresholding" (a key component of nuclear-norm methods) into the updates.

Key aspects of the method include:

  • Unification of Objectives: The algorithm effectively optimizes a problem that bridges the nuclear-norm objective and the MMMF objective.
  • Alternating Ridge Regression: Instead of directly computing SVDs at each step (which can be computationally expensive for large matrices), softImpute-ALS uses alternating ridge regressions. This is more efficient, especially when combined with the "sparse-plus-low-rank" representation of the data.
  • Warm Starts: The algorithm benefits from using previous iterates as "warm starts" for subsequent computations, significantly speeding up convergence.
  • Sparse-Plus-Low-Rank Representation: For efficiency, especially with large and sparse matrices, the algorithm utilizes a representation that combines sparse matrices with low-rank components.
  • Distributed Implementation: A distributed version of softImpute-ALS is developed using Apache Spark, enabling it to handle extremely large matrices that don't fit into a single machine's memory.

Datasets

The paper evaluates its methods on:

  • Simulated Datasets: Three simulation examples of increasing size and missingness percentage are used.
  • MovieLens 100K Dataset: A publicly available dataset for movie recommendations.
  • Netflix Competition Data: A very large and sparse dataset from the Netflix Prize competition, used to compare softImpute-ALS with hardImpute.

Key Insights and Ideas

  • Synergy of Approaches: Unifying nuclear-norm regularization and MMMF leads to a more powerful algorithm than either method alone. The "soft-thresholding" aspect of nuclear-norm methods, when integrated into an ALS framework, provides a significant speedup.
  • Efficiency of Alternating Ridge Regression: Replacing full SVD computations with alternating ridge regressions, especially when leveraging the sparse-plus-low-rank structure, is a crucial optimization for large matrices.
  • Warm Starts are Critical: The effectiveness of the algorithm is greatly enhanced by using warm starts, allowing it to converge much faster in later iterations.
  • Scalability is Achievable: The development of a distributed version using Spark demonstrates that matrix completion can be scaled to massive datasets.

Key Results

  • Speedup: softImpute-ALS consistently outperforms standard ALS and the original softImpute algorithm in timing experiments across various datasets. For instance, on the Netflix data, softImpute-ALS is significantly faster than ALS.
  • Performance on Netflix Data: softImpute-ALS achieves a competitive test-set RMSE (0.943) on the Netflix data, showing a 1% improvement over the "Cinematch" score.
  • Convergence: The paper provides theoretical guarantees for the convergence of softImpute-ALS to a stationary point, with finite-time convergence rates established.
  • Rank Truncation: The algorithm naturally produces low-rank solutions, and a final step can effectively truncate the rank, similar to soft-thresholding.

Limitations and Future Work

  • Optimality Guarantees: While the algorithm converges to a stationary point, it's noted that this point may not always be the global minimum of the convex problem (1), especially if the chosen rank r is smaller than the true rank of the optimal solution.
  • Parameter Tuning: The choice of the regularization parameter λ and the operating rank r can influence performance and the quality of the solution. The paper mentions using trial-and-error for selecting λ in experiments.
  • Future Work: The paper highlights the potential for further optimization and exploration of the algorithm's properties, including its application to other related problems. The distributed implementation is a significant step towards handling even larger datasets. The authors also mention a "sparse-plus-low-rank" representation that could be useful for other applications beyond matrix completion.

Summary updated

Abstract

The matrix-completion problem has attracted a lot of attention, largely as a result of the celebrated Net flix 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 softImpute in R for implementing our approaches, and a distributed version for very large matrices using the Spark cluster programming environment.
BibTeX
@article{hastie2015matrix,
  author = {Trevor Hastie and Rahul Mazumder and Jason D. Lee and Reza Zadeh},
  title = {{Matrix completion and low-rank SVD via fast alternating least squares}},
  journal = {J. Mach. Learn. Res.},
  year = {2015},
  url = {https://openreview.net/forum?id=fL1cHwwBaEo},
}
Figure