On Deterministically Computing Total Variation Distance via Zonotope Compression
En palabras de los autores
We study deterministic relative approximation of the total variation distance between high-dimensional distributions given by succinct descriptions. We develop an abstract deterministic approximation framework based on representing the total variation distance as a support function of a low-dimensional zonotope. As applications, we obtain FPTASs for several models. Given two mixtures of product distributions over with a total of component distributions, our algorithm approximates their TV-distance within a factor of in time . We also give an FPTAS for mixtures of -step Markov chains over with a total of component distributions, with running time . Finally, for two latent-tree Ising models with the same underlying tree topology, we give an FPTAS for the TV-distance between their leaf marginals in time .
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.