19
$\begingroup$

If two Gaussians disagree on one moment, it seems like this should imply that they have a large variation distance--equivalently, if two Gaussians are close in variation distance it's hard for their moments to differ very much. But I'm having trouble proving this without getting into a terrible mess and ending up with weak bounds. I'm hoping someone here can offer a slick proof or point me to one.

Suppose that $\Sigma_1$ and $\Sigma_2$ are two positive-semidefinite matrices, with diagonal entries bounded by 1, and that $\Sigma_1$ and $\Sigma_2$ differ by at least $\delta$ in one of their entries.

Can we lower-bound the total variation distance between the multivariate gaussians with covariance matrices $\Sigma_1$ and $\Sigma_2$? In particular, is this distance at least $\Theta(\delta)$? It seems like it ought to be, since the gaussians are pretty well concentrated. But trying to formalize the obvious approach seems to create a bit of a mess.

Edit: Douglas Zare and guest point out that you can trivially reduce to the 2 dimensional case by projecting onto the relevant subspace. So we can restrict attention to that case.

$\endgroup$
5
  • $\begingroup$ Is this a homework problem? $\endgroup$
    – Omer
    Mar 14, 2014 at 23:38
  • 2
    $\begingroup$ No; together with the strong concavity of the entropy it might give an alternative and conceptually clearer proof of this claim, in which I am once again interested. What suggests this might be a homework problem? $\endgroup$ Mar 15, 2014 at 17:24
  • $\begingroup$ for the lazy amongst us, could you write out a formula (after simplifying the stuff that is unimportant for the bound) for this TV distance? $\endgroup$
    – Suvrit
    Mar 18, 2014 at 17:44
  • $\begingroup$ If the entry is on the diagonal, projecting to this coordinate gives $1$-dimensional Gaussians (where you can compute the total variation distance explicitly). If the entry is off the diagonal, projecting to the two coordinates involved reduces this to a problem on $2$-dimensional Gaussians. $\endgroup$ Mar 18, 2014 at 18:21
  • $\begingroup$ Suvrit: it's a big integral, of the absolute value of the difference between the Gaussian densities. I don't really see how to simplify it usefully, and writing it out is a mess. $\endgroup$ Mar 18, 2014 at 22:59

4 Answers 4

12
+100
$\begingroup$

Letting $\mu_{a,\Sigma}$ be the Gaussian measure with covariance matrix $\Sigma$ and mean $a$. Then (double) the variation distance can be written as $$ \left\lVert\mu_{a_1,\Sigma_1}-\mu_{a_2,\Sigma_2}\right\rVert_1 = \max_f\left\lvert\mu_{a_1,\Sigma_1}(f)-\mu_{a_2,\Sigma_2}(f)\right\rvert, $$ where the maximum is taken over functions $f\colon\mathbb{R}^n\to\mathbb{C}$ with $\lvert f\rvert\le1$. Taking $f(x)=\exp(ix\cdot u)$ for a fixed $u\in\mathbb{R}^n$, plugging in the characteristic function for Gaussian distributions, $$ \begin{align} \left\lVert\mu_{a_1,\Sigma_1}-\mu_{a_2,\Sigma_2}\right\rVert_1&\ge\max_{u\in\mathbb{R}^n}\left\lvert e^{ia_1\cdot u-\frac12 u^t\Sigma_1u}-e^{ia_2\cdot u-\frac12 u^t\Sigma_2u}\right\rvert\\ &\ge\max_{u\in\mathbb{R}^n}\left\lvert e^{-\frac12 u^t\Sigma_1u}-e^{-\frac12 u^t\Sigma_2u}\right\rvert\\ &=\max_{u\in\mathbb{R}^n,\lVert u\rVert_1=1}\max_{\lambda\ge0}\left\lvert e^{-\frac12 \lambda^2u^t\Sigma_1u}-e^{-\frac12 \lambda^2u^t\Sigma_2u}\right\rvert. \end{align} $$ Note that, for any $1\ge\alpha > \beta > 0$, we can consider $\lambda=1/\sqrt{\alpha}$ to get the following bound, $$ \max_{\lambda\ge0}\left(e^{-\lambda^2\beta}-e^{-\lambda^2\alpha}\right)\ge e^{-\frac\beta\alpha}-e^{-1}=\Theta\left(1-\frac\beta\alpha\right)=\Theta(\alpha-\beta). $$ Hence, as we are assuming $\Sigma_i$ are positive semidefinite with diagonal entries bounded by 1, we have $1\ge u^t\Sigma_iu\ge0$ for $u\in\mathbb{R}^n$ with $\lVert u\rVert_1=1$ and, $$ \left\lVert\mu_{a_1,\Sigma_1}-\mu_{a_2,\Sigma_2}\right\rVert_1=\Theta\left(\max_{\lVert u\rVert_1=1}\left\lvert u^t(\Sigma_1-\Sigma_2)u\right\rvert\right) $$ For any symmetric matrix $M$ we have $2M_{ij}=(e_i+e_j)^tM(e_i+e_j)-e_i^tMe_i-e_j^tMe_j$ where $e_i$ is the unit vector along coordinate dimension $i$, from which we get $$ \left\lVert\mu_{a_1,\Sigma_1}-\mu_{a_2,\Sigma_2}\right\rVert_1=\Theta\left(\lVert\Sigma_1-\Sigma_2\rVert_\infty\right) $$

$\endgroup$
3
  • $\begingroup$ Thanks! I'll give this the bounty unless a significantly cleaner solution crops up (unless there is some etiquette about this I don't know). Minor (I think) issue: the covariance matrices can have eigenvalues more than 1. But you only need to apply this bound for sparse vectors, so it looks like you are good. $\endgroup$ Mar 19, 2014 at 3:04
  • $\begingroup$ I switched the norm used for $u$ to fix the minor issue $\endgroup$ Mar 19, 2014 at 10:49
  • $\begingroup$ Can you explain why the first equality holds? (why is the L1 norm equal to sup over functions that satisfy |f| <=1 ?) $\endgroup$ Oct 28, 2019 at 15:08
3
$\begingroup$

(This is actually more of a comment, but I do not have that privilege. Since it may be useful, I post it as an answer. If someone can make this a comment, please do so.)

Section IV of the paper Total Variation Distance and the Distribution of Relative Information states some lower bounds on total variation in terms of KL divergence, which may be helpful as KL divergence of normal variables has a closed form.

$\endgroup$
2
$\begingroup$

Here's another comment. I'm assuming the gaussians are mean 0. If you pick some linear combination of the gaussians, you get in each of cases 1 and 2 a mean 0 gaussian with a variance depending on the covariance matrix entries. A lower bound on the variation distance between these univariate gaussians is a lower bound on the variation distance between the multivariate gaussians. This doesn't seem too tough. Is it the approach that was problematic?

$\endgroup$
1
  • $\begingroup$ I certainly should have made that observation... I don't see how to do this nicely even in the case of 2 dimensional Gaussians, but upon consideration it does seem like that should be much easier. $\endgroup$ Mar 18, 2014 at 22:55
0
$\begingroup$

Suppose entry $i,j$ differs by $\delta$. For one of $X_i$, or $X_j$, or $X_i+X_j$, the variance differs by at least $\delta/2$ under the two measures, which brings the problem to the 1 dimensional case, which is easy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.