  Estimating the joint probability mass function (PMF) of a set of random
variables lies at the heart of statistical learning and signal processing.
Without structural assumptions, such as modeling the variables as a Markov
chain, tree, or other graphical model, joint PMF estimation is often considered
mission impossible - the number of unknowns grows exponentially with the number
of variables. But who gives us the structural model? Is there a generic,
`non-parametric' way to control joint PMF complexity without relying on a
priori structural assumptions regarding the underlying probability model? Is it
possible to discover the operational structure without biasing the analysis up
front? What if we only observe random subsets of the variables, can we still
reliably estimate the joint PMF of all? This paper shows, perhaps surprisingly,
that if the joint PMF of any three variables can be estimated, then the joint
PMF of all the variables can be provably recovered under relatively mild
conditions. The result is reminiscent of Kolmogorov's extension theorem -
consistent specification of lower-dimensional distributions induces a unique
probability measure for the entire process. The difference is that for
processes of limited complexity (rank of the high-dimensional PMF) it is
possible to obtain complete characterization from only three-dimensional
distributions. In fact not all three-dimensional PMFs are needed; and under
more stringent conditions even two-dimensional will do. Exploiting multilinear
algebra, this paper proves that such higher-dimensional PMF completion can be
guaranteed - several pertinent identifiability results are derived. It also
provides a practical and efficient algorithm to carry out the recovery task.
Judiciously designed simulations and real-data experiments on movie
recommendation and data classification are presented to showcase the
effectiveness of the approach.
