2
$\begingroup$

I was wondering whether or not there's an intuitive way of understanding the Gaussian isoperimetric inequality. I have been studying the Classical isoperimetric inequality and I finally understand it. I want to move to advance isoperimetric inequalities. I am interested in the Gaussian isoperimetric as it seems to have nice and practical applications in information theory.

I have no background in measure theory, but I understand that the concept of measure is a generalization of the notions of length, area and volume. I also understand that the Gaussian measure is a probability measure, meaning that it has the additional property of being normalized.

I've also looked at the definition of half spaces. I understand what a half space is. Most resources I've found do not explain the intuition behind the inequality, like the Wikipedia page , they simply provide the definition which is not easy not to understand.

How do you interpret the inequality?

$\endgroup$
0
$\begingroup$

The screenshots below come from the book Mathematical Foundations of Infinite-Dimensional Statistical Models.

The classical isoperimetric inequality is well-known: given a fixed perimeter, a circle achieves the largest area, or, given a fixed area, a circle achieves the smallest perimeter among other shapes. If we recall that perimeter can be seen as the derivative of the area, this is like saying

$$ \mu(C+\epsilon O_2)\le\mu(A+\epsilon O_2) $$ where $\mu$ is Lebesgue measure, $A$ is a measurable set, $C$ is a circle with $\mu(C)=\mu(A)$, $O_2$ is the 2D unit disk, and the "$+$" is Minkowski addition. To see why, one can subtract $\mu(C)=\mu(A)$ from both two sides, divide them by $\epsilon$, and let $\epsilon\to0^+$, then he/she will get the usual form of isoperimetric inequality.

It turns out that this form of isoperimetric inequality is more convenient to generalize: we can allow higher dimensions, Riemannian manifolds equipped with some geodesic distances other than $\mathbb{R}^2$, or other measures. For example, we can have

enter image description here

where $A_\epsilon\triangleq A+\epsilon O_n$ and same for $C_\epsilon$.

We can interpret isoperimetric inequalities from the perspective of concentration inequality: it answers that if you perturb a set with some ϵ in distance/metric, how large its size will (at least) change. In the context of probabilistic measures, the change of "size" becomes a probability.

We need the following lemma to have a better understanding of or to prove Gaussian isoperimetric inequality:

enter image description here

where $\gamma_n$ is the standard Gaussian measure on $\mathbb{R}^n$. One can verify the claim via doing simulation for, say $n=1$, by projecting points uniformly distributed on $\sqrt{m}S^{m+1}$ onto $\mathbb{R}^1$. If in Python:

import numpy as np
import matplotlib.pyplot as plt

def runif_s(n_samples, n, m):
    rnorm = np.random.randn(n_samples, n + m + 1)
    return np.sqrt(m) * rnorm / np.linalg.norm(rnorm, axis=1)[..., np.newaxis]

def proj_hist(data, **kwargs):
    n = 1
    plt.figure()
    plt.hist(data[:, :n], density=True, **kwargs)
    plt.title('m = %d' % (data.shape[1] - n - 1))

if __name__ == '__main__':
    n = 1
    n_figures = 5
    n_samples = 10**4
    [proj_hist(runif_s(n_samples, n, int(m)), bins='auto') for m in np.logspace(0, 2, n_figures)]
    plt.show()

And you may see the projected distribution is visually close to the normal distribution when $m$ grows large: enter image description here

Let's return to Gaussian isoperimetric inequality. The inequality is a version of isoperimetric inequality w.r.t. Gaussian measure, by which we roughly mean, finding the counterpart of a "circle" under Gaussian measure. Recall that we already have an isoperimetrc inequality for $S^{m+n}$ w.r.t. Lebesgue measure (Theorem 2.2.1), and a relation between this measure and the standard Gaussian measure on $\mathbb{R}^n$ (Lemma 2.2.2), so all we have to do is to project the cap on $S^{m+n}$ back to $\mathbb{R}^n$, and let $m\to\infty$. For the convenience of doing projection, we choose the cap "perpendicular" to $\mathbb{R}^n$. If we look into the case of $n=1$ to gain intuition, the cap will be symmetric around $\mathbb{R}^1$ with the pole lying at $-\sqrt{m}$.

Let's say we now have a measurable set $A$ on $\mathbb{R}^1$, then we can find the cap $C$ on $S^{m+1}$ with $\mu(C)=\gamma_1(A)$. The projection of the cap onto $\mathbb{R}^1$ is the interval $[-\sqrt{m},b(m)]$ for some $b(m)$. By taking $m\to\infty$, the interval becomes $(-\infty,b(\infty)]$, and according to Lemma 2.2.2, we know that $b(\infty)=\Phi^{-1}(\gamma_1(A))$, giving the "circle" w.r.t. $\gamma_1$ being $\{x:x\le \Phi^{-1}(\gamma_1(A))\}$.

The proof of the general Gaussian isoperimetric inequality follows the same intuition, except that we need to replace the ray $\{x:x\le \Phi^{-1}(\gamma_1(A))\}$ with the hyperplane $\{x:\langle x,u \rangle\le\Phi^{-1}(\gamma_n(A))\}$, where $u$ is an arbitrary unit vector in $\mathbb{R}^n$. Finally we will have

enter image description here

and its countably-infinite-dimensional version

enter image description here where $\mathcal{C}$ is the cylindrical $\sigma$-algebra on $\mathbb{R}^\mathbb{N}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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