# Low-Rank Matrix Completion: A Contemporary Survey

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2019.

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

- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms](https://mlsanity.com/paper/2406.02832/) (2024)
- [Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions](https://mlsanity.com/paper/2303.14226/) (2023)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices](https://mlsanity.com/paper/2105.10360/) (2021)
- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [Temporal Graph Signal Decomposition](https://mlsanity.com/paper/2106.13517/) (2021)
- [Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss](https://mlsanity.com/paper/2202.02063/) (2022)
- [Higher-order Spatio-temporal Physics-incorporated Graph Neural Network for Multivariate Time Series Imputation](https://mlsanity.com/paper/2405.10995/) (2024)
- [Rotation Synchronization via Deep Matrix Factorization](https://mlsanity.com/paper/2305.05268/) (2023)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition](https://mlsanity.com/paper/2204.14067/) (2022)
- [Doubly Robust Inference in Causal Latent Factor Models](https://mlsanity.com/paper/2402.11652/) (2024)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function](https://mlsanity.com/paper/2503.23832/) (2025)
- [Multilinear Kernel Regression and Imputation via Manifold Learning](https://mlsanity.com/paper/2402.03648/) (2024)
- [4CNet: A Diffusion Approach to Map Prediction for Decentralized Multi-Robot Exploration](https://mlsanity.com/paper/2402.17904/) (2024)
- [Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks](https://mlsanity.com/paper/2502.02766/) (2025)
- [On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical Similarity Graphs](https://mlsanity.com/paper/2109.05408/) (2021)
- [Weighted Low-Rank Matrix Approximation: Acceleration and Applications](https://mlsanity.com/paper/2109.11057/) (2021)
- [Gradual Federated Learning with Simulated Annealing](https://mlsanity.com/paper/2110.05178/) (2021)
- [Adaptive Sampling for Discovery](https://mlsanity.com/paper/2205.14829/) (2022)
- [Faster Convergence of Riemannian Stochastic Gradient Descent with Increasing Batch Size](https://mlsanity.com/paper/2501.18164/) (2025)
- [A Taxonomy of Structure from Motion Methods](https://mlsanity.com/paper/2505.15814/) (2025)
- [Image Reconstruction using Superpixel Clustering and Tensor Completion](https://mlsanity.com/paper/2305.09564/) (2023)
- [Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing](https://mlsanity.com/paper/2310.15549/) (2023)
- [Discrete Aware Matrix Completion via Convexized ℓ0-Norm Approximation](https://mlsanity.com/paper/2405.02101/) (2024)
- [Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders](https://mlsanity.com/paper/2405.03651/) (2024)
- [DKDL-Net: A Lightweight Bearing Fault Detection Model via Decoupled Knowledge Distillation and Low-Rank Adaptation Fine-tuning](https://mlsanity.com/paper/2406.06653/) (2024)
- [ClusterSC: Advancing Synthetic Control with Donor Selection](https://mlsanity.com/paper/2503.21629/) (2025)

## Abstract (arXiv)

As a paradigm to recover unknown entries of a matrix from partial observations, low-rank matrix completion (LRMC) has generated a great deal of interest. Over the years, there have been lots of works on this topic but it might not be easy to grasp the essential knowledge from these studies. This is mainly because many of these works are highly theoretical or a proposal of new LRMC technique. In this paper, we give a contemporary survey on LRMC. In order to provide better view, insight, and understanding of potentials and limitations of LRMC, we present early scattered results in a structured and accessible way. Specifically, we classify the state-of-the-art LRMC techniques into two main categories and then explain each category in detail. We next discuss issues to be considered when one considers using LRMC techniques. These include intrinsic properties required for the matrix recovery and how to exploit a special structure in LRMC design. We also discuss the convolutional neural network (CNN) based LRMC algorithms exploiting the graph structure of a low-rank matrix. Further, we present the recovery performance and the computational complexity of the state-of-the-art LRMC techniques. Our hope is that this survey article will serve as a useful guide for practitioners and non-experts to catch the gist of LRMC.