# Approximating the Total Variation Distance between Gaussians

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 14 Mar 2025.

## Builds on (most cited first, 11 of 11)

- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning](https://mlsanity.com/paper/2002.05378/) (2020)
- [On Approximating Total Variation Distance](https://mlsanity.com/paper/2206.07209/) (2022)
- [Discriminative Estimation of Total Variation Distance: A Fidelity Auditor for Generative Data](https://mlsanity.com/paper/2405.15337/) (2024)
- [On Computing the Total Variation Distance of Hidden Markov Models](https://mlsanity.com/paper/1804.06170/) (2018)
- [A simple polynomial-time approximation algorithm for the total variation distance between two product distributions](https://mlsanity.com/paper/2208.00740/) (2022)
- [On Deterministically Approximating Total Variation Distance](https://mlsanity.com/paper/2309.14696/) (2023)
- [Total Variation Distance Meets Probabilistic Inference](https://mlsanity.com/paper/2309.09134/) (2023)
- [Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians](https://mlsanity.com/paper/2109.01064/) (2021)
- [Bit Complexity of Jordan Normal Form and Spectral Factorization](https://mlsanity.com/paper/2109.13956/) (2021)
- [The Complexity of Diagonalization](https://mlsanity.com/paper/2305.10575/) (2023)

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

- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)

## Abstract (arXiv)

The total variation distance is a metric of central importance in statistics and probability theory. However, somewhat surprisingly, questions about computing it algorithmically appear not to have been systematically studied until very recently. In this paper, we contribute to this line of work by studying this question in the important special case of multivariate Gaussians. More formally, we consider the problem of approximating the total variation distance between two multivariate Gaussians to within an ε-relative error. Previous works achieved a fixed constant relative error approximation via closed-form formulas. In this work, we give algorithms that given any two n-dimensional Gaussians D1,D2, and any error bound ε > 0, approximate the total variation distance D := dTV(D1,D2) to ε-relative accuracy in poly(n,frac1ε,log frac1D) operations. The main technical tool in our work is a reduction that helps us extend the recent progress on computing the TV-distance between discrete random variables to our continuous setting.