16
$\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$
  • $\begingroup$ Is this a homework problem? $\endgroup$ – Omer Mar 14 '14 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$ – Paul Christiano Mar 15 '14 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 '14 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$ – Douglas Zare Mar 18 '14 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$ – Paul Christiano Mar 18 '14 at 22:59
11
+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$
  • $\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$ – Paul Christiano Mar 19 '14 at 3:04
  • $\begingroup$ I switched the norm used for $u$ to fix the minor issue $\endgroup$ – George Lowther Mar 19 '14 at 10:49
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$
  • $\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$ – Paul Christiano Mar 18 '14 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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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