# Missing Not at Random in Matrix Completion: The Effectiveness of Estimating Missingness Probabilities Under a Low Nuclear Norm Assumption

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

## Key facts

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

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

- [ImputeFormer: Low Rankness-Induced Transformers for Generalizable Spatiotemporal Imputation](https://mlsanity.com/paper/2312.01728/) (2023)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Identifiable Generative Models for Missing Not at Random Data Imputation](https://mlsanity.com/paper/2110.14708/) (2021)
- [Enhanced Doubly Robust Learning for Debiasing Post-click Conversion Rate Estimation](https://mlsanity.com/paper/2105.13623/) (2021)
- [Correcting Exposure Bias for Link Recommendation](https://mlsanity.com/paper/2106.07041/) (2021)
- [Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions](https://mlsanity.com/paper/2303.14226/) (2023)
- [TenIPS: Inverse Propensity Sampling for Tensor Completion](https://mlsanity.com/paper/2101.00323/) (2021)
- [FragmGAN: Generative Adversarial Nets for Fragmentary Data Imputation and Prediction](https://mlsanity.com/paper/2203.04692/) (2022)
- [Doubly Robust Inference in Causal Latent Factor Models](https://mlsanity.com/paper/2402.11652/) (2024)
- [Fine-Grained Dynamic Framework for Bias-Variance Joint Optimization on Data Missing Not at Random](https://mlsanity.com/paper/2405.15403/) (2024)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [Sequential Nature of Recommender Systems Disrupts the Evaluation Process](https://mlsanity.com/paper/2205.13681/) (2022)
- [Bilateral Self-unbiased Learning from Biased Implicit Feedback](https://mlsanity.com/paper/2207.12660/) (2022)
- [How Low Can We Go: Trading Memory for Error in Low-Precision Training](https://mlsanity.com/paper/2106.09686/) (2021)
- [Learning Counterfactual Distributions via Kernel Nearest Neighbors](https://mlsanity.com/paper/2410.13381/) (2024)
- [Optimal Transfer Learning for Missing Not-at-Random Matrix Completion](https://mlsanity.com/paper/2503.00174/) (2025)
- [Exploiting Observation Bias to Improve Matrix Completion](https://mlsanity.com/paper/2306.04775/) (2023)
- [Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion](https://mlsanity.com/paper/2411.12965/) (2024)
- [Prediction in the presence of response-dependent missing labels](https://mlsanity.com/paper/2103.13555/) (2021)
- [Matrix Completion of World Trade](https://mlsanity.com/paper/2109.03930/) (2021)
- [Learning to Recommend Using Non-Uniform Data](https://mlsanity.com/paper/2110.11248/) (2021)
- [Regression with Sensor Data Containing Incomplete Observations](https://mlsanity.com/paper/2304.13415/) (2023)
- [Deep Generative Imputation Model for Missing Not At Random Data](https://mlsanity.com/paper/2308.08158/) (2023)
- [Collaborative Imputation of Urban Time Series through Cross-city Meta-learning](https://mlsanity.com/paper/2501.11306/) (2025)
- [N2: A Unified Python Package and Test Bench for Nearest Neighbor-Based Matrix Completion](https://mlsanity.com/paper/2506.04166/) (2025)
- [Generalization Bounds for Semi-supervised Matrix Completion with Distributional Side Information](https://mlsanity.com/paper/2511.13049/) (2025)
- [Causal Matrix Completion under Multiple Treatments via Mixed Synthetic Nearest Neighbors](https://mlsanity.com/paper/2603.11942/) (2026)
- [Identifiable Deep Latent Variable Models for MNAR Data](https://mlsanity.com/paper/2603.24771/) (2026)
- [Synthetic Nearest Neighbors: Extending Synthetic Controls for Matrix Completion with Missing Not at Random Data](https://mlsanity.com/paper/2609.13586/) (2026)

## Abstract (arXiv)

Matrix completion is often applied to data with entries missing not at random (MNAR). For example, consider a recommendation system where users tend to only reveal ratings for items they like. In this case, a matrix completion method that relies on entries being revealed at uniformly sampled row and column indices can yield overly optimistic predictions of unseen user ratings. Recently, various papers have shown that we can reduce this bias in MNAR matrix completion if we know the probabilities of different matrix entries being missing. These probabilities are typically modeled using logistic regression or naive Bayes, which make strong assumptions and lack guarantees on the accuracy of the estimated probabilities. In this paper, we suggest a simple approach to estimating these probabilities that avoids these shortcomings. Our approach follows from the observation that missingness patterns in real data often exhibit low nuclear norm structure. We can then estimate the missingness probabilities by feeding the (always fully-observed) binary matrix specifying which entries are revealed or missing to an existing nuclear-norm-constrained matrix completion algorithm by Davenport et al. [2014]. Thus, we tackle MNAR matrix completion by solving a different matrix completion problem first that recovers missingness probabilities. We establish finite-sample error bounds for how accurate these probability estimates are and how well these estimates debias standard matrix completion losses for the original matrix to be completed. Our experiments show that the proposed debiasing strategy can improve a variety of existing matrix completion algorithms, and achieves downstream matrix completion accuracy at least as good as logistic regression and naive Bayes debiasing baselines that require additional auxiliary information.