Discrete Mixture Models

We develop the “method of synthetic bits” for solving discretem mixtures of product distributions, giving a exponential time complexity improvement (in the number of sources). The algorithm involves a reduction to the $k$-MixIID case.

We use Prony’s method to solve the $k$-MixIID problem, which gives improved sample and time complexity via a new stability analysis.