The total variation distance between high-dimensional Gaussians with the same mean

Introduction

We denote by $N(\mu,\Sigma)$ a random variable with this distribution. Note that if $X\sim\mathcal{N}(\mu,\Sigma)$ then $\mathbf{E}X=\mu$ and $\mathbf{E}XX^{\mathsf{T}}=\Sigma$.

with respect to the $r$-dimensional Lebesgue measure on $\mu+\operatorname{range}(\Sigma)$. The density is zero outside this affine subspace. For general background on high-dimensional Gaussian distributions (also called multivariate normal distributions), see .

If $P$ and $Q$ have densities $p$ and $q$, then it is easy to verify that the set $A\coloneqq\{x:p(x)>q(x)\}$ attains the supremum here, and this observation leads to the identity

that is, the total variation distance is half the $L^{1}$ distance. In the following, we will sometimes write $\operatorname{TV}\left(X,Y\right)$ for $\operatorname{TV}\left(P,Q\right)$, where $X$ and $Y$ are random variables distributed as $P$ and $Q$, respectively. Observe that $\operatorname{TV}\left(P,Q\right)$ is a metric and is always between 0 and 1. For a survey on measures of distance between distributions and inequalities between them, see .

We have seen that the total variation distance can be written as an integral or as a supremum, but in general there is no known closed form for it. In this note, given two Gaussians with the same mean, we give closed-form lower and upper bounds for their total variation distance, which are within a constant factor of one another. If the Gaussians have different means, we give only a lower bound and leave a tight characterization as an open problem.This problem has been solved; see [1, Theorem 1.8].

Open Problem. Find closed-form lower and upper bounds for the total variation distance between two high-dimensional Gaussians that are within a constant factor of one another.

Note that if $\mu_{1}+\operatorname{range}(\Sigma_{1})\neq\mu_{2}+\operatorname{range}(\Sigma_{2})$, in particular if $\operatorname{rank}(\Sigma_{1})\neq\operatorname{rank}(\Sigma_{2})$, then we have $\operatorname{TV}\left(\mathcal{N}(\mu_{1},\Sigma_{1}),\mathcal{N}(\mu_{2},\Sigma_{2})\right)=1$, since the intersection of the supports have zero Lebesgue measure. Another trivial case is when $\mu_{1}=\mu_{2}$ and $\Sigma_{1}=\Sigma_{2}$, in which case the total variation distance is zero. We will not explicitly treat these two cases.

Our first main result concerns the same-mean case. We have not tried to optimize the constants in our results.

If $\Sigma_{1}$ and $\Sigma_{2}$ are positive semi-definite, $\operatorname{range}(\Sigma_{1})=\operatorname{range}(\Sigma_{2})$, and $r=\operatorname{rank}(\Sigma_{1})=\operatorname{rank}(\Sigma_{2})$, then let $\Pi$ be a $d\times r$ matrix that has the same range as $\Sigma_{1}$ and $\Sigma_{2}$ and let $\rho_{1},\dots,\rho_{r}$ denote the eigenvalues of $(\Pi^{\mathsf{T}}\Sigma_{1}\Pi)^{-1}(\Pi^{\mathsf{T}}\Sigma_{2}\Pi)-I_{r}$. Then, we have

The paper proves a bound similar to Theorem 1.1 for Gaussian distributions in a general Hilbert space: if $\Sigma_{1}$ and $\Sigma_{2}$ are positive definite matrices, $\Sigma_{1}^{-1}\Sigma_{2}-I$ has eigenvalues $\lambda_{1},\cdots$, and $\sqrt{\sum\lambda_{i}^{2}}\leq 1/50$, then [2, Corollary 2] gives

This result has the advantage that it covers infinite-dimensional spaces as well, but it holds only when ${\sum\lambda_{i}^{2}}$ is smaller than a threshold.

One can express the quantities $\sum\lambda_{i}^{2}$ and $\sum\rho_{i}^{2}$ in Theorem 1.1 in terms of Frobenius norms of appropriate matrices. For the first case, i.e., when $\Sigma_{1},\Sigma_{2}$ are positive definite, we have

To see this, first note that $\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}$ have the same spectrum as $\Sigma_{1}^{-1}\Sigma_{2}$, because a vector $v$ is an eigenvector for $\Sigma_{1}^{-1}\Sigma_{2}$ with eigenvalue $\alpha$ if and only if $\Sigma_{1}^{1/2}v$ is an eigenvector for $\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}$ with eigenvalue $\alpha$. Thus, the eigenvalues of $\left(\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\right)^{2}$ are $\lambda_{1}^{2},\dots,\lambda_{d}^{2}$, proving the first equality in (2). The second equality follows by noting that the matrix $\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}$ is symmetric. The second case, i.e., when $\Sigma_{1},\Sigma_{2}$ are positive semi-definite, can be handled similarly.

For the case where the means are different, we prove the following lower bound.

Along the way of proving this theorem, we also give bounds for the one-dimensional case.

In the one-dimensional case, $d=1$, we have

Although the total variation distance is symmetric, our lower and upper bounds are not symmetric, so they can be automatically strengthened; for instance, the following symmetric version of Theorem 1.3 holds:

Moreover, for Theorem 1.1, swapping $\Sigma_{1}$ and $\Sigma_{2}$ can change the estimation of the total variation distance by at most a multiplicative factor of 2. Namely, suppose $\Sigma_{1}$ and $\Sigma_{2}$ are positive definite $d\times d$ matrices, $\lambda_{1},\dots,\lambda_{d}$ are the eigenvalues of $\Sigma_{1}^{-1}\Sigma_{2}-I_{d}$, and $\nu_{1},\dots,\nu_{d}$ are the eigenvalues of $\Sigma_{2}^{-1}\Sigma_{1}-I_{d}$. Then elementary calculations give

Some preliminaries and other known bounds for the total variation distance between Gaussians appear in Section 2. We start by proving Theorem 1.1 in Section 3, then we prove Theorem 1.3 in Section 4, and finally we prove Theorem 1.2 in Section 5.

Preliminaries

The $d$-dimensional identity matrix is denoted $I_{d}$. The trace and determinant of a matrix $A$ are denoted $\operatorname{tr}(A)$ and $\det(A)$, respectively. The Frobenius norm (also called the Hilbert–Schmidt norm or the Schur norm) of a matrix $A$ is denoted by $\|A\|_{F}\coloneqq\sqrt{\operatorname{tr}(AA^{\mathsf{T}})}$. Note that $\|A\|_{F}^{2}$ equals the sum of squares of entries of $A$. If $A$ is symmetric, $\|A\|_{F}^{2}$ equals the sum of squares of eigenvalues of $A$. For general background on matrix norms, see [4, Chapter 5].

The coupling characterization of the total variation distance.

For two distributions $P$ and $Q$, a pair $(X,Y)$ of random variables defined on the same probability space is called a coupling for $P$ and $Q$ if $X\sim P$ and $Y\sim Q$. An extremely useful property of the total variation distance is the coupling characterization: for any two distributions $P$ and $Q$, we have $\operatorname{TV}\left(P,Q\right)\leq t$ if and only if there exists a coupling $(X,Y)$ for them such that $\mathbf{P}\left\{{X\neq Y}\right\}\leq t$ (see, e.g., [6, Proposition 4.7]). This characterization implies that for any function $f$ we have $\operatorname{TV}\left(f(X),f(Y)\right)\leq\operatorname{TV}\left(X,Y\right)$. If $f$ is invertible (for instance if $f(v)=Av+b$ where $A$ is full-rank) this also implies $\operatorname{TV}\left(f(X),f(Y)\right)=\operatorname{TV}\left(X,Y\right)$.

An important property of the Gaussian distribution is that any linear transformation of a Gaussian random variable is also Gaussian: if $X\sim\mathcal{N}(\mu,\Sigma)$ then

For a positive semi-definite matrix $\Sigma$ with eigendecomposition $\Sigma=\sum_{i=1}^{d}\lambda_{i}v_{i}v_{i}^{\mathsf{T}}$ where the $v_{i}$ are orthonormal, we define $\Sigma^{1/2}\coloneqq\sum_{i=1}^{d}\sqrt{\lambda_{i}}v_{i}v_{i}^{\mathsf{T}}$ and $\Sigma^{-1/2}\coloneqq\sum_{i=1}^{d}v_{i}v_{i}^{\mathsf{T}}/\sqrt{\lambda_{i}}$. It is easy to observe that if $g\sim\mathcal{N}(0,I)$ then $\Sigma^{1/2}g\sim\mathcal{N}(0,\Sigma)$.

throughout, which implies that for any $x\geq-2/3$ there exists a $b\in$ such that $x-\log(1+x)=bx^{2}$.

We next state some known bounds for the total variation distance between two Gaussians, which may be more convenient than the above bounds for some applications.

For the case when the two Gaussians have the same covariance matrix, [2, Theorem 1] gives

The following bounds follow from known relations between statistical distances.

An upper bound for the total variation distance using the KL-divergence.

and Pinsker’s inequality [11, Lemma 2.5] states that $\operatorname{TV}\left(P,Q\right)\leq\sqrt{\operatorname{KL}\left(P\parallel Q\right)/2}$ for any pair of distributions. The KL-divergence between two Gaussians has a closed form (e.g., [8, Formula (A.23)]):

Combining these gives the following proposition.

If $\Sigma_{1}$ and $\Sigma_{2}$ are positive definite, then

Bounds for the total variation distance using the Hellinger distance.

see [5, page 44]. The Hellinger distance between two Gaussians has a closed form (e.g., [7, Exercises 11 and 14 in Chapter 1]):

Combining these gives the following proposition.

Assume that $\Sigma_{1},\Sigma_{2}$ are positive definite, and let

The same-mean case: proof of Theorem 1.1

In this section we consider the case when both Gaussians have the same mean. For proving the theorem we will need two lemmas.

Suppose $\lambda_{1},\dots,\lambda_{d}\geq-2/3$ and let $\rho\coloneqq\sqrt{\sum_{i=1}^{d}\lambda_{i}^{2}}$. If $C$ is a diagonal matrix with diagonal entries $1+\lambda_{1},\dots,1+\lambda_{d}$, then $\operatorname{TV}\left(\mathcal{N}(0,C^{-1}),\mathcal{N}(0,I_{d})\right)\geq\rho/6-\rho^{2}/8-(e^{\rho^{2}}-1)/2.$

Define a random vector $g=(g_{1},\dots,g_{d})\sim\mathcal{N}(0,I_{d})$. From (1) we have

Since $\lambda_{i}\geq-2/3$ for all $i$, we have $\log(1+\lambda_{i})/2=\lambda_{i}/2-b_{i}\lambda_{i}^{2}/2$ for some $b_{i}\in$, and summing these up we find $\sum_{i=1}^{d}\log(1+\lambda_{i})/2=\sum_{i=1}^{d}\lambda_{i}/2-b\rho^{2}$ for some $b\in$. Also let $h_{i}=1-g_{i}^{2}$ and $X=\sum_{i=1}^{d}\lambda_{i}h_{i}/2$, whence

where the first inequality is the triangle inequality, the second one follows from

and the third one follows from Hölder’s inequality (see, e.g., [3, Lemma 14.8]). We control each term on the right-hand-side of (3). First, observe that since $h_{i}$ is mean-zero, we have $\mathbf{E}h_{i}h_{j}=0$ for all $i\neq j$, and since $\mathbf{E}h_{i}^{2}=2$,

Second, since $\mathbf{E}g_{i}^{2}=1,\mathbf{E}g_{i}^{4}=3,\mathbf{E}g_{i}^{6}=15$, and $\mathbf{E}g_{i}^{8}=105,$ we have $\mathbf{E}h_{i}^{4}=60$; thus,

Finally, for the exponential moment, note that $\mathbf{E}\exp(tg_{i}^{2})=(1-2t)^{-1/2}$ for any $t<1/2$, hence

If $\lambda^{2}\geq 0.01$ then $\operatorname{TV}\left(\mathcal{N}(0,1),\mathcal{N}(0,1+\lambda)\right)>0.01$.

If $\lambda>0$ then $1+\lambda\geq 1.1$, so we have

and if $\lambda<0$ then $1+\lambda\leq 0.9$, so we have

For both parts of the theorem, we may assume that $\mu=0$. We start with the case that $\Sigma_{1}$ and $\Sigma_{2}$ are positive definite, i.e., they have full rank. Recall that $\Sigma_{1}^{-1}\Sigma_{2}$ have eigenvalues $1+\lambda_{1},\dots,1+\lambda_{d}$. Let $\rho\coloneqq\sqrt{\sum_{i=1}^{d}{\lambda_{i}^{2}}}$.

We first prove the upper bound. If some $\lambda_{i}<-2/3$ then trivially

and the upper bound in the theorem is proved.

For proving the lower bound, we first claim that if $C$ is a diagonal matrix with diagonal entries $1+\lambda_{1},\dots,1+\lambda_{d}$, then

To prove this, let $g\sim\mathcal{N}(0,I_{d})$. We first claim if $E$ and $F$ are positive definite matrices with the same spectrum, then $\operatorname{TV}(Eg,g)=\operatorname{TV}(Fg,g)$. To see this, let $s_{1},\dots,s_{d}$ be the eigenvalues of $E$ and $F$, and let $g_{1},\dots,g_{d}$ be the components of $g$. By rotational invariance of the standard Gaussian distribution (see, e.g., [12, Proposition 3.3.2]), both $\operatorname{TV}(Eg,g)$ and $\operatorname{TV}(Fg,g)$ are equal to $\operatorname{TV}((s_{1}g_{1},s_{2}g_{2},\dots,s_{d}g_{d}),(g_{1},g_{2},\dots,g_{d}))$, and the claim is proved. This also implies, for any two positive definite matrices $E$ and $F$ with the same spectrum,

Now $\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}$ has the same spectrum as $\Sigma_{2}^{-1}\Sigma_{1}$, which has the same spectrum as $C^{-1}$, whence (4) is proved.

For proving the lower bound in the theorem we consider three cases.

Case 1: there exists some $i$ with $|\lambda_{i}|\geq 0.1$. Observe that if we project a random variable distributed as $\mathcal{N}(0,C^{-1})$ onto the $i$th component, we obtain a one-dimensional $\mathcal{N}(0,(1+\lambda_{i})^{-1})$ random variable . Since projection can only decrease the total variation distance, using Lemma 3.2 we obtain

as required. The above equality holds because the total variation distance is invariant under any linear transformation.

Case 2: $|\lambda_{i}|<0.1$ for all $i$, and $\rho\leq 0.17$. In this case Lemma 3.1 gives

Case 3: $|\lambda_{i}|<0.1$ for all $i$, and $\rho>0.17$. Define

and observe that $f(x)\geq 0.01$ for $0.1\leq x\leq 0.17$. Let $1\leq j<d$ be the largest index such that $\sum_{i=1}^{j}\lambda_{i}^{2}\leq 0.17^{2}$, and observe that since $|\lambda_{i}|<0.1$ for all $i$, we have $\rho^{\prime 2}\coloneqq\sum_{i=1}^{j}\lambda_{i}^{2}\geq 0.17^{2}-0.1^{2}>0.01$ and so $f(\rho^{\prime})\geq 0.01$. Let $C^{\prime}$ be the diagonal $j\times j$ matrix with diagonal entries $1+\lambda_{1},\dots,1+\lambda_{j}$. If we project a random variable distributed as $\mathcal{N}(0,C^{-1})$ onto the first $j$ coordinates, we obtain a $\mathcal{N}(0,C^{\prime-1})$ random variable. Since projection can only decrease the total variation distance, using Lemma 3.1 we obtain

The matrices $\Pi^{\mathsf{T}}\Sigma_{1}\Pi$ and $\Pi^{\mathsf{T}}\Sigma_{2}\Pi$ are positive definite $r\times r$ matrices, hence the second part of the theorem follows from the first part. ∎

The one-dimensional case: proof of Theorem 1.3

We start with the upper bound. If $\frac{|\sigma_{1}^{2}-\sigma_{2}^{2}|}{\sigma_{1}^{2}}\geq 2/3$, then the right-hand-side is at least 1 and the bound holds because the total variation distance is at most 1. Otherwise, since ${\sigma_{2}^{2}}/{\sigma_{1}^{2}}-1\geq-2/3$, we have ${\sigma_{2}^{2}}/{\sigma_{1}^{2}}-1-\log({\sigma_{2}^{2}}/{\sigma_{1}^{2}})\leq({\sigma_{2}^{2}}/{\sigma_{1}^{2}}-1)^{2}$, so from Proposition 2.1 we have

The lower bound follows from the following two lower bounds:

and then (5) follows from Theorem 1.1. Assume, without loss of generality, that $\sigma_{1}\leq\sigma_{2}$ and $\mu_{1}\leq\mu_{2}$. By the form of the density of the normal distribution, this implies there exists some $c=c(\sigma_{1},\sigma_{2})$ such that

To complete the proof of Theorem 1.3 we need only prove (6). By symmetry, we may assume $\mu_{1}\leq\mu_{2}$. Let $X\sim\mathcal{N}(\mu_{1},\sigma_{1}^{2})$. Then

which proves (6) and completes the proof of the theorem.

The general case: proof of Theorem 1.2

with $P\coloneqq I_{d}-vv^{\mathsf{T}}/v^{\mathsf{T}}v$.

Let $X\sim\mathcal{N}(\mu_{1},\Sigma_{1})$ and $Y\sim\mathcal{N}(\mu_{2},\Sigma_{2})$. Then we have, by the coupling characterization of the total variation distance,

We next claim that $\displaystyle f_{1}(X)\sim\mathcal{N}\left(\frac{1}{2},\frac{v^{\mathsf{T}}\Sigma_{1}v}{(v^{\mathsf{T}}v)^{2}}\right)$. To see this, observe that $f_{1}(X)$ is a linear map of a Gaussian, so it is Gaussian. Its mean and covariance can be computed from those of $X$. Similarly, one can compute $\displaystyle f_{1}(Y)\sim\mathcal{N}\left(-\frac{1}{2},\frac{v^{\mathsf{T}}\Sigma_{2}v}{(v^{\mathsf{T}}v)^{2}}\right)$. So, Theorem 1.3 gives

On the other hand, since $f_{2}(w)=P(w-u)$, both $f_{2}(X)$ and $f_{2}(Y)$ are also Gaussians, with $f_{2}(X)\sim\mathcal{N}(0,P\Sigma_{1}P)$ and $f_{2}(Y)\sim\mathcal{N}(0,P\Sigma_{2}P)$. Note that $\operatorname{range}(P\Sigma_{1}P)=\operatorname{range}(P\Sigma_{2}P)=\operatorname{range}(\Pi)$. Also observe that since each column of $\Pi$ is orthogonal to $v$, we have $\Pi^{\mathsf{T}}P=\Pi$ and $P\Pi=\Pi$. Recall that $\rho_{1},\dots,\rho_{d-1}$ are the eigenvalues of $(\Pi^{\mathsf{T}}\Sigma_{1}\Pi)^{-1}\Pi^{\mathsf{T}}\Sigma_{2}\Pi-I_{d-1}$. Hence the second part of Theorem 1.1 gives

We are grateful to Michael Kohler, Gautam Kamath, Cole Franks, and Shirshendu Ganguly for pointing out inaccuracies in earlier versions of this paper.

References