# Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

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

- [Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach](https://mlsanity.com/paper/2109.11135/) (2021)
- [Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses](https://mlsanity.com/paper/2104.14562/) (2021)
- [Recovery of Joint Probability Distribution from one-way marginals: Low rank Tensors and Random Projections](https://mlsanity.com/paper/2103.11864/) (2021)
- [Checking the Sufficiently Scattered Condition using a Global Non-Convex Optimization Software](https://mlsanity.com/paper/2402.06019/) (2024)
- [Learning From Crowdsourced Noisy Labels: A Signal Processing Perspective](https://mlsanity.com/paper/2407.06902/) (2024)
- [Joint Probability Estimation Using Tensor Decomposition and Dictionaries](https://mlsanity.com/paper/2203.01667/) (2022)
- [Estimating Joint Probability Distribution With Low-Rank Tensor Decomposition, Radon Transforms and Dictionaries](https://mlsanity.com/paper/2304.08740/) (2023)
- [Time series forecasting from partial observations via Non-negative Matrix Factorization](https://mlsanity.com/paper/2102.05314/) (2021)
- [Joint Bayesian Parameter and Model Order Estimation for Low-Rank Probability Mass Tensors](https://mlsanity.com/paper/2410.06329/) (2024)
- [Robustness of Minimum-Volume Nonnegative Matrix Factorization under an Expanded Sufficiently Scattered Condition](https://mlsanity.com/paper/2511.04291/) (2025)

## Abstract (arXiv)

Learning the joint probability of random variables (RVs) is the cornerstone of statistical signal processing and machine learning. However, direct nonparametric estimation for high-dimensional joint probability is in general impossible, due to the curse of dimensionality. Recent work has proposed to recover the joint probability mass function (PMF) of an arbitrary number of RVs from three-dimensional marginals, leveraging the algebraic properties of low-rank tensor decomposition and the (unknown) dependence among the RVs. Nonetheless, accurately estimating three-dimensional marginals can still be costly in terms of sample complexity, affecting the performance of this line of work in practice in the sample-starved regime. Using three-dimensional marginals also involves challenging tensor decomposition problems whose tractability is unclear. This work puts forth a new framework for learning the joint PMF using only pairwise marginals, which naturally enjoys a lower sample complexity relative to the third-order ones. A coupled nonnegative matrix factorization (CNMF) framework is developed, and its joint PMF recovery guarantees under various conditions are analyzed. Our method also features a Gram--Schmidt (GS)-like algorithm that exhibits competitive runtime performance. The algorithm is shown to provably recover the joint PMF up to bounded error in finite iterations, under reasonable conditions. It is also shown that a recently proposed economical expectation maximization (EM) algorithm guarantees to improve upon the GS-like algorithm's output, thereby further lifting up the accuracy and efficiency. Real-data experiments are employed to showcase the effectiveness.