# Poisson Matrix Recovery and Completion

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

## Key facts

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

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

- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)
- [Beyond Maximum Likelihood: Variational Inequality Estimation for Generalized Linear Models](https://mlsanity.com/paper/2511.03087/) (2025)
- [A Generalized Latent Factor Model Approach to Mixed-data Matrix Completion with Entrywise Consistency](https://mlsanity.com/paper/2211.09272/) (2022)
- [Under-Counted Tensor Completion with Neural Incorporation of Attributes](https://mlsanity.com/paper/2306.03273/) (2023)
- [Spectral gap-based deterministic tensor completion](https://mlsanity.com/paper/2306.06262/) (2023)
- [Learning to Recommend Using Non-Uniform Data](https://mlsanity.com/paper/2110.11248/) (2021)
- [eRPCA: Robust Principal Component Analysis for Exponential Family Distributions](https://mlsanity.com/paper/2310.19787/) (2023)
- [Negative Binomial Matrix Completion](https://mlsanity.com/paper/2408.16113/) (2024)
- [Near-Efficient and Non-Asymptotic Multiway Inference](https://mlsanity.com/paper/2511.05368/) (2025)

## Abstract (arXiv)

We extend the theory of low-rank matrix recovery and completion to the case when Poisson observations for a linear combination or a subset of the entries of a matrix are available, which arises in various applications with count data. We consider the usual matrix recovery formulation through maximum likelihood with proper constraints on the matrix M of size d1-by-d2, and establish theoretical upper and lower bounds on the recovery error. Our bounds for matrix completion are nearly optimal up to a factor on the order of O(log(d1 d2)). These bounds are obtained by combing techniques for compressed sensing for sparse vectors with Poisson noise and for analyzing low-rank matrices, as well as adapting the arguments used for one-bit matrix completion citedavenport20121 (although these two problems are different in nature) and the adaptation requires new techniques exploiting properties of the Poisson likelihood function and tackling the difficulties posed by the locally sub-Gaussian characteristic of the Poisson distribution. Our results highlight a few important distinctions of the Poisson case compared to the prior work including having to impose a minimum signal-to-noise requirement on each observed entry and a gap in the upper and lower bounds. We also develop a set of efficient iterative algorithms and demonstrate their good performance on synthetic examples and real data.