Poisson Matrix Recovery and Completion

Abstract

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 $d_1$-by-$d_2$, 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 $\mathcal{O}(\log (d_1{d}_2))$. 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 \cite{davenport20121} (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.

Submitted to IEEE Journal. Parts of the paper have appeared in GlobalSIP 2013, GlobalSIP 2014, and ISIT 2015. arXiv admin note: substantial text overlap with arXiv:1501.06243

References in corpus (2)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Minimax Optimal Rates for Poisson Inverse Problems with Physical Constraints

Cited by in corpus (17)

• An overview of low-rank matrix recovery from incomplete observations
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• HePPCAT: Probabilistic PCA for Data with Heteroscedastic Noise
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Biwhitening Reveals the Rank of a Count Matrix
• Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising
• Low-rank matrix completion and denoising under Poisson noise
• Multi-sample Estimation of Bacterial Composition Matrix in Metagenomics Data
• Maximum entropy low-rank matrix recovery
• Cross: Efficient Low-rank Tensor Completion
• Learning Markov models via low-rank optimization
• Categorical Matrix Completion
• High-dimensional Log-Error-in-Variable Regression with Applications to Microbial Compositional Data Analysis
• Reconstruction Error Bounds for Compressed Sensing under Poisson or Poisson-Gaussian Noise Using Variance Stabilization Transforms
• Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros
• Reconstruction Error Bounds for Compressed Sensing under Poisson Noise using the Square Root of the Jensen-Shannon Divergence
• Tensor Kernel Recovery for Spatio-Temporal Hawkes Processes