Source-linked AI summary
The total variation distance between high-dimensional Gaussians with the same mean
Luc Devroye, Abbas Mehrabian, Tommy Reddad
TL;DR
The paper tackles the lack of a closed-form characterization of total variation distance for high-dimensional Gaussians. It proves constant-factor lower and upper bounds when the means agree, while for different means it gives only a lower bound.
Problem
Total variation distance generally has no known closed form, and finding constant-factor bounds for high-dimensional Gaussians is posed as an open problem.
Source: §1 · p. 2Method
The paper derives bounds for Gaussian total variation, treating the same-mean case and the different-mean case separately.
Source: §1 · pp. 2–3Results
For Gaussians with the same mean, the closed-form lower and upper bounds are within a constant factor; for different means, the paper proves only a lower bound.
Source: §1 · p. 2Takeaways & Limitations
The same-mean case has a constant-factor characterization, while a tight characterization for different means remains open.
Source: §1 · p. 2The treatment excludes disjoint affine supports, where total variation is 1, and identical distributions, where it is 0; common-support singular cases can be treated in their affine subspace.
Source: §1 · pp. 2–3
Abstract
from arXiv · showhide
Given two high-dimensional Gaussians with the same mean, we prove a lower and an upper bound for their total variation distance, which are within a constant factor of one another.
1 Introduction
The paper addresses the lack of a closed-form characterization of total variation distance between high-dimensional Gaussians. It gives constant-factor lower and upper bounds for Gaussians with the same mean, but only a lower bound when their means differ.
1 Introduction
- For Gaussians with the same mean, the paper gives closed-form lower and upper bounds within a constant factor; for different means, it gives only a lower bound and leaves tight characterization open.The paper frames the same-mean result as addressing an open problem about high-dimensional Gaussians.Source: §1 · p. 2
- The same-mean bounds cover positive-definite covariances and positive-semidefinite covariances with equal ranges and ranks.For the latter case, the theorem uses eigenvalues formed from covariance matrices restricted to their shared range.Source: §1 · p. 2
- For different means, the lower bound uses covariance information restricted to the subspace orthogonal to the difference between the means.The theorem defines the mean-difference vector and eigenvalues from the covariances projected onto that orthogonal subspace.Source: §1 · p. 3
- The paper also gives bounds for one-dimensional Gaussians and states a symmetric version because the lower and upper bounds are not symmetric.The symmetric version strengthens the one-dimensional bounds by swapping the Gaussian inputs.Source: §1 · pp. 3–4
- For the same-mean theorem, swapping the covariance matrices changes the estimate of total variation distance by at most a factor of 2.This gives a bound on the asymmetry of the estimate despite the symmetry of total variation distance.Source: §1 · p. 4
2 Preliminaries
The preliminaries introduce total variation distance and its coupling characterization, then collect Gaussian and matrix facts used to derive bounds through KL and Hellinger distances.
Matrix definitions and Hellinger bounds
- The Frobenius norm is the square root of the sum of squared matrix entries, while for symmetric matrices its squared value is the sum of squared eigenvalues.The section also introduces the Hellinger distance and combines its known relation to total variation with the closed form for Gaussian pairs.Source: §2 · pp. 4–5
The coupling characterization of the total variation distance
- A coupling makes total variation at most t exactly when the coupled variables disagree with probability at most t, and measurable maps cannot increase that distance.For invertible maps, including full-rank affine maps, the distance is unchanged.Source: §2 · p. 4
Gaussian transformations
- Linear transformations preserve Gaussianity, and a positive-semidefinite covariance can be represented using its square root applied to a standard Gaussian.The stated covariance transformation also includes the terms induced by the affine shift.Source: §2 · p. 4
Known bounds using statistical distances
- Pinsker’s inequality and the closed form for Gaussian KL-divergence yield a total variation upper bound for Gaussian pairs.The passages combine these known relations; they do not provide the resulting bound’s full expression.Source: §2 · p. 5
3 The same-mean case: proof of Theorem 1.1
The proof treats full-rank covariances by bounding total variation through eigenvalue deviations, then handles shared-range singular covariances by reducing to the full-rank case.
Auxiliary lemmas
- Lemma 3.2 supplies a one-dimensional separation step: λ² ≥ 0.01 implies TV(N(0,1), N(0,1 + λ)) > 0.01.The proof also develops an auxiliary inequality by controlling mean-zero terms and an exponential moment.Source: §3 · pp. 6–7
Full-rank covariances
- The proof establishes the theorem’s upper bound by handling the case where some λi < −2/3 trivially and, otherwise, applying Proposition 2.1.Source: §3 · p. 8
- The lower-bound proof splits into three cases: a large eigenvalue deviation, uniformly small deviations with small aggregate deviation, and uniformly small deviations with larger aggregate deviation.For the first case, projecting onto the coordinate with |λ_i| ≥ 0.1 reduces the comparison to one dimension; Lemma 3.2 gives a positive distance when λ² ≥ 0.01.Source: §3 · pp. 8–9
Shared-range singular covariances
- For positive-semidefinite covariances with the same range, an invertible coordinate map sends that range to R^r, where the compressed covariances are positive definite and the full-rank result applies.The map is v ↦ Π^T v, with inverse w ↦ Π(Π^TΠ)^−1w.Source: §3 · p. 9
4 The one-dimensional case: proof of Theorem 1.3
The one-dimensional proof obtains an upper bound from a Gaussian KL-divergence bound and establishes the lower bound through two component bounds.
Upper bound
- The upper bound follows from Proposition 2.1 after bounding the variance-ratio expression by a squared deviation and including the squared mean difference.The displayed fragment identifies the terms as σ₂²/σ₁² − 1 − log(σ₂²/σ₁²) and (μ₁ − μ₂)²/σ₁².Source: §4 · p. 9
Lower bound
- The lower bound is assembled from two lower bounds, with one proof ordering the means and variances and using the one-dimensional density form.That argument introduces a constant c depending on σ₁ and σ₂.Source: §4 · pp. 9–10
- The remaining lower-bound step uses symmetry to assume μ₁ ≤ μ₂.The proof then begins with X distributed as N(μ₁, σ₂²).Source: §4 · p. 10
5 The general case: proof of Theorem 1.2
The general-case proof decomposes vectors into components along the mean-difference direction and its orthogonal complement, then bounds the two projected comparisons separately.
Directional decomposition
- The proof decomposes each vector into a component along v = μ₁ − μ₂ and an orthogonal component, using P = I_d − vv^T/v^Tv for the orthogonal projection.This decomposition defines the maps used to compare the Gaussian pairs.Source: §5 · p. 10
Projected comparisons
- The coupling characterization bounds the original distance through the two mapped comparisons; Theorem 1.3 handles the directional component and Theorem 1.1 handles the shared-range orthogonal component.The orthogonal projections have covariance matrices PΣ₁P and PΣ₂P, with the same range.Source: §5 · p. 11