Skip to content
DraconiticResearch
Search Sources API
181,713 studies31 sourcesUpdated 39 min ago
PreprintCC BY 4.0arXiv

On Deterministically Computing Total Variation Distance via Zonotope Compression

  • Yucheng Fu
Open at sourcePDFDOICite

Abstract

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 [q]n with a total of K component distributions, our algorithm approximates their TV-distance within a factor of 1+ε in time ÕK(nq(n/ε)2K). We also give an FPTAS for mixtures of n-step Markov chains over [q]n with a total of K component distributions, with running time ÕK(nq2(n/ε)2K). 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 O(|V|13ε−12).

Related

  1. DiffLyap-MEC: Diffusion-Guided Lyapunov Optimization for Joint Offloading, Semantic Compression, and Resource Allocation in ISAC-Enabled 6G Edge Computing
    Abrar S. Alhazmi, Mohammed M. Alenazi
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  2. Total Variation Distance between Product Distributions: an Analytic Proxy
    Ariel Avital, Aryeh Kontorovich, Roman Vershynin +1
    arXivPreprintarXiv licenceFull textProbabilityStatisticsarXiv
  3. Total Variation Distance Estimation through Domain Reduction
    Arnab Bhattacharyya, Graham Cormode, Yucheng Fu +1
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  4. Stability of optimal transport maps and second variation of the 2-Monge-Kantorovich distance
    F. -U. Caja-Lopez, Matias G. Delgadino, Jun Kitagawa
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  5. Euclidean SVP is deterministically NP-hard to approximate within any constant factor
    Daqing Wan
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{fu2026deterministically,
  title = {{On Deterministically Computing Total Variation Distance via Zonotope Compression}},
  author = {Yucheng Fu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.24235},
  eprint = {2609.24235},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.24235},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On Deterministically Computing Total Variation Distance via Zonotope Compression
AU  - Yucheng Fu
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2609.24235
UR  - https://arxiv.org/abs/2609.24235
AB  - 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 [q]^n with a total of K component distributions, our algorithm approximates their TV-distance within a factor of 1+ε in time Õ_K(nq(n/ε)^2K). We also give an FPTAS for mixtures of n-step Markov chains over [q]^n with a total of K component distributions, with running time Õ_K(nq^2(n/ε)^2K). 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 O(|V|^13ε^−12).
ER  -