# Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 26 references that are in the map.
- First posted on arXiv 29 Feb 2024.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Matrix Completion via Max-Norm Constrained Optimization](https://mlsanity.com/paper/1303.0341/) (2013)
- [Universal Matrix Completion](https://mlsanity.com/paper/1402.2324/) (2014)
- [Computational Limits for Matrix Completion](https://mlsanity.com/paper/1402.2331/) (2014)

## Built on by (most cited first, 1 of 1)

- [Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows](https://mlsanity.com/paper/2409.03980/) (2024)

## Abstract (arXiv)

Low-rank matrix completion concerns the problem of estimating unobserved entries in a matrix using a sparse set of observed entries. We consider the non-uniform setting where the observed entries are sampled with highly varying probabilities, potentially with different asymptotic scalings. We show that under structured sampling probabilities, it is often better and sometimes optimal to run estimation algorithms on a smaller submatrix rather than the entire matrix. In particular, we prove error upper bounds customized to each entry, which match the minimax lower bounds under certain conditions. Our bounds characterize the hardness of estimating each entry as a function of the localized sampling probabilities. We provide numerical experiments that confirm our theoretical findings.