# One-Sided Matrix Completion from Ultra-Sparse Samples

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 58 references that are in the map.
- First posted on arXiv 18 Jan 2026.

## Builds on (most cited first, 25 of 25)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Bridging Language and Items for Retrieval and Recommendation: Benchmarking LLMs as Semantic Encoders](https://mlsanity.com/paper/2403.03952/) (2024)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guarantees](https://mlsanity.com/paper/2206.02659/) (2022)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Fast Differentially Private Matrix Factorization](https://mlsanity.com/paper/1505.01419/) (2015)
- [Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approach](https://mlsanity.com/paper/2306.08553/) (2023)
- [Towards Quantifying the Hessian Structure of Neural Networks](https://mlsanity.com/paper/2505.02809/) (2025)
- [Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization](https://mlsanity.com/paper/1802.07372/) (2018)
- [Data-Driven Switchback Experiments: Theoretical Tradeoffs and Empirical Bayes Designs](https://mlsanity.com/paper/2406.06768/) (2024)
- [Learning Mixtures of Low-Rank Models](https://mlsanity.com/paper/2009.11282/) (2020)
- [Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent](https://mlsanity.com/paper/1709.08114/) (2017)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimation](https://mlsanity.com/paper/2511.12779/) (2025)
- [Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion](https://mlsanity.com/paper/2402.06756/) (2024)
- [Target PCA: Transfer Learning Large Dimensional Panel Data](https://mlsanity.com/paper/2308.15627/) (2023)
- [Scalable methods for nonnegative matrix factorizations of near-separable tall-and-skinny matrices](https://mlsanity.com/paper/1402.6964/) (2014)
- [Matrix Completion from O(n) Samples in Linear Time](https://mlsanity.com/paper/1702.02267/) (2017)
- [One-sided Matrix Completion from Two Observations Per Row](https://mlsanity.com/paper/2306.04049/) (2023)
- [Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion](https://mlsanity.com/paper/1504.06817/) (2015)

## Abstract (arXiv)

Matrix completion is a classical problem that has received recurring interest across a wide range of fields. In this paper, we revisit this problem in an ultra-sparse sampling regime, where each entry of an unknown, n× d matrix M (with n ≥ d) is observed independently with probability p = C / d, for a fixed integer C ≥ 2. This setting is motivated by applications involving large, sparse panel datasets, where the number of rows far exceeds the number of columns. When each row contains only C entries -- fewer than the rank of M -- accurate imputation of M is impossible. Instead, we estimate the row span of M or the averaged second-moment matrix T = Mtop M / n. The empirical second-moment matrix computed from observed entries exhibits non-random and sparse missingness. We propose an unbiased estimator that normalizes each nonzero entry of the second moment by its observed frequency, followed by gradient descent to impute the missing entries of T. The normalization divides a weighted sum of n binomial random variables by the total number of ones. We show that the estimator is unbiased for any p and enjoys low variance. When the row vectors of M are drawn uniformly from a rank-r factor model satisfying an incoherence condition, we prove that if n ≥ O(d r5 ε-2 C-2 log d), any local minimum of the gradient-descent objective is approximately global and recovers T with error at most ε2. Experiments on both synthetic and real-world data validate our approach. On three MovieLens datasets, our algorithm reduces bias by 88% relative to baseline estimators. We also empirically validate the linear sampling complexity of n relative to d on synthetic data. On an Amazon reviews dataset with sparsity 10-7, our method reduces the recovery error of T by 59% and M by 38% compared to baseline methods.