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

arXiv: https://arxiv.org/abs/1410.2596 · HTML: https://mlsanity.com/paper/1410.2596/

## Key facts

- Cited by 104 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2014.

## Built on by (most cited first, 30 of 104)

- [HyperImpute: Generalized Iterative Imputation with Automatic Model Selection](https://mlsanity.com/paper/2206.07769/) (2022)
- [Generating and Imputing Tabular Data via Diffusion and Flow-based Gradient-Boosted Trees](https://mlsanity.com/paper/2309.09968/) (2023)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [ReMasker: Imputing Tabular Data with Masked Autoencoding](https://mlsanity.com/paper/2309.13793/) (2023)
- [Transformed Distribution Matching for Missing Value Imputation](https://mlsanity.com/paper/2302.10363/) (2023)
- [DiffPuter: Empowering Diffusion Models for Missing Data Imputation](https://mlsanity.com/paper/2405.20690/) (2024)
- [Multiple Imputation via Generative Adversarial Network for High-dimensional Blockwise Missing Value Problems](https://mlsanity.com/paper/2112.11507/) (2021)
- [Data Imputation with Iterative Graph Reconstruction](https://mlsanity.com/paper/2212.02810/) (2022)
- [On Speeding Up Language Model Evaluation](https://mlsanity.com/paper/2407.06172/) (2024)
- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [Numerical Optimizations for Weighted Low-rank Estimation on Language Model](https://mlsanity.com/paper/2211.09718/) (2022)
- [Deep Weight Factorization: Sparse Learning Through the Lens of Artificial Symmetries](https://mlsanity.com/paper/2502.02496/) (2025)
- [Handling Missing Data via Max-Entropy Regularized Graph Autoencoder](https://mlsanity.com/paper/2211.16771/) (2022)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices](https://mlsanity.com/paper/2105.10360/) (2021)
- [Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization](https://mlsanity.com/paper/2210.12579/) (2022)
- [Recursive Video Lane Detection](https://mlsanity.com/paper/2308.11106/) (2023)
- [Fairness in Missing Data Imputation](https://mlsanity.com/paper/2110.12002/) (2021)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [A Context-Aware Approach for Enhancing Data Imputation with Pre-trained Language Models](https://mlsanity.com/paper/2405.17712/) (2024)
- [Explainability of Machine Learning Models under Missing Data](https://mlsanity.com/paper/2407.00411/) (2024)
- [Low-rank Matrix Recovery With Unknown Correspondence](https://mlsanity.com/paper/2110.07959/) (2021)
- [AmGCL: Feature Imputation of Attribute Missing Graph via Self-supervised Contrastive Learning](https://mlsanity.com/paper/2305.03741/) (2023)
- [Unmasking Trees for Tabular Data](https://mlsanity.com/paper/2407.05593/) (2024)
- [CACTI: Leveraging Copy Masking and Contextual Information to Improve Tabular Data Imputation](https://mlsanity.com/paper/2506.02306/) (2025)
- [One Pipeline, Many Transformers: Pattern-Specific Imputation Specialists for Tabular Missing Data](https://mlsanity.com/paper/2510.02625/) (2025)
- [Wasserstein Graph Neural Networks for Graphs with Missing Attributes](https://mlsanity.com/paper/2102.03450/) (2021)
- [Multiple Imputation with Neural Network Gaussian Process for High-dimensional Incomplete Data](https://mlsanity.com/paper/2211.13297/) (2022)
- [Numerical Data Imputation for Multimodal Data Sets: A Probabilistic Nearest-Neighbor Kernel Density Approach](https://mlsanity.com/paper/2306.16906/) (2023)

## Abstract (arXiv)

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 (Candes and Tao, 2009, Mazumder, Hastie and Tibshirani, 2010), and maximum-margin matrix factorization (Srebro, Rennie and Jaakkola, 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.