40 votos

¿Prueba de "entropía" de la desigualdad de Brunn-Minkowski?

He leído en una teoría de la información de libros de texto de la Brunn-Minkowski desigualdad se sigue de la Entropía de Alimentación de la desigualdad.

La primera dice que si $A,B$ son polígonos convexos en $\mathbb{R}^d$, luego

$$ m(A+B)^{1/d} \geq m(A)^{1/d} + m(B)^{1/d} $$

donde $A+B = \{ a+b: a \in A, b \in B\}$ es la suma de Minkowski.

La entropía de alimentación de la desigualdad indica que si $X$ e $Y$ son independientes de las variables aleatorias, y $H(X) = \int f(x) \ln f(x) \, dx$ luego

$$ e^{2H(X+Y)/d} \geq e^{2H(X)/d}+ e^{2H(Y)/d}$$

Si el enchufe en Gaussiano aleatorio de las variables con sus respectivas matrices de covarianza $X = N(0,C_1)$ e $Y = N(0,C_2)$ luego de obtener la versión de los cuadros:

$$ \det(C_1+C_2)^{1/d} \geq \det(C_1)^{1/d} + \det(C_2)^{1/d}$$

Me gustaría entender mejor por qué la geometría Convexa debe tener nada que ver con la teoría de la información, y que los naturales de las distribuciones de probabilidad asociadas a un conjunto convexo.


El artículo de Gardner tiene el "antepasado" de la Brunn-Minkowski de la desigualdad como el Brascamp-Lieb la desigualdad, mientras que la Entropía de alimentación de la desigualdad se sigue de la desigualdad de Young.

En ese caso, mi pregunta es, ¿qué función convexa de los polígonos que tienen allí?


enter image description here

Me visto parece una "bombilla" en estos difíciles que las desigualdades de análisis funcional se basa en la intuición de la geometría convexa - especialmente ya que nadie saca fotos en un análisis funcional de libros de texto.

30voto

steevc Puntos 211

La similitud entre la entropía de alimentación de la desigualdad y la Brunn-Minkowski de la desigualdad no está directamente relacionada con la convexidad - después de todo, Brunn-Minkowski puede ser generalizada para delimitada abrir los conjuntos que no son necesariamente convexa. (Sin embargo, muchas de las pruebas de ambas desigualdades utilizar las ideas de la convexidad de la teoría, por supuesto.)

Tomando el microestado (es decir, Boltzmann) interpretación de la entropía, uno puede de forma heurística de vista de la entropía de alimentación de la desigualdad como una de alta-dimensional de "99%" analógica de Brunn-Minkowski, en el que se considera el "99%-sumset" $A \stackrel{99\%}{+} B$ de dos grandes dimensiones de los conjuntos a y B (esto es un poco vagamente definido el concepto, pero a grandes rasgos es que el grueso del apoyo de dos variables aleatorias distribuidas en a y B respectivamente), en lugar de las "100%-sumset" a+B. sin Embargo, gracias a la concentración de medir el fenómeno, el 99%-sumset es considerablemente menor que el 100%-sumset en altas dimensiones, que conduce a la adicional exponente de 2 en la entropía de alimentación de la desigualdad. Por ejemplo, considere por alto las dimensiones de dos bolas $B(0,R)$, $B(0,r)$ de radios $R,r$ respectivamente. Su 100%-sumset es $B(0,R+r)$ del curso. Pero si uno toma un elemento aleatorio de $B(0,R)$ y se agrega un elemento aleatorio de $B(0,r)$, la suma se concentra en una parte mucho más pequeña bola de asintóticamente, $B(0,\sqrt{R^2+r^2})$ (de hecho, se concentra en el límite de esta bola). Esto se reduce al hecho básico de que los pares de vectores en alto dimensiones normalmente son casi ortogonal a cada uno de los otros. Así que uno moralmente ha

$$ B(0,R) \stackrel{99\%}{+} B(0,r) = B(0,\sqrt{R^2+r^2}) \qquad (1)$$

en la alta dimensión límite.

De todos modos, la EPI puede ser pensado como una rigurosa formulación de un `99% de Brunn-Minkowski de la desigualdad"

$$ |A \stackrel{99\%}{+} B|^{1/N} \geq \sqrt{ (|A|^{1/N})^2 + (|B|^{1/N})^2 } \qquad (2)$$

en la alta dimensión límite de $N \to \infty$ (con $A,B \subset \mathbb{R}^N$ variando adecuadamente con $N$), que por supuesto es consistente con (1). Para ver esta interpretación, se observa desde el microestado de interpretación de la entropía que si $X$ es una variable aleatoria continua en $\mathbb{R}^n$ con una buena función de distribución (por ejemplo,$C^\infty_c$), y $M$ es grande, y luego tomar las $M$ copias independientes $X_1,\dots,X_M$ de % de $X$ da un vector aleatorio $X^{\otimes M} := (X_1,\dots,X_M)$ en $\mathbb{R}^{N}$ para $N := Mn$ que (por el asintótica equipartition propiedad) se concentra en un subconjunto de $\mathbb{R}^N$ de medida $e^{M (H(X)+o(1))}$ en el límite de $M \to \infty$ (este es un buen cálculo mediante la fórmula de Stirling; puede ayudar, en primer lugar, el caso cuando la distribución de probabilidad de $X$ es una función simple en lugar de una función de prueba). Del mismo modo, si $Y$ es otra variable aleatoria independiente de $X$,, a continuación, $Y^{\otimes M}$ se concentran en un conjunto de medida $e^{M(H(Y)+o(1))}$, mientras que $(X+Y)^{\otimes M}$ se concentra en un conjunto de medida $e^{M(H(X+Y)+o(1))}$. EPI es entonces moralmente consecuencia de (2) en el límite de $M \to \infty$.

A pesar de las diferencias significativas entre las $99\%$-sumset y $100\%$-sumset en altas dimensiones, es bueno pensar en estos conceptos estrechamente análogas, de modo que casi cualquier sumset la desigualdad debe tener una entropía de contraparte y viceversa (aunque en la mayoría de los casos no tenemos una directa implicación lógica entre la sumset la desigualdad y la entropía de la desigualdad; en su lugar, las desigualdades suelen tener análoga, pero no es totalmente idéntico, pruebas). Ver, por ejemplo, este artículo reciente de Kontoyiannis y Madiman (y las referencias a la misma) para algunos casos de esto.

EDIT: por supuesto, por la delimitación de la $99\%$-sumset por la $100\%$-sumset uno puede conseguir algunos de conexión entre los dos tipos de desigualdades, pero por lo general uno obtiene una estimación inferior cuando uno utiliza este enfoque ignora por completo el efecto de la concentración de la medida), por lo que esta no es la manera "correcta" para relacionar sumset desigualdades con su entropía contrapartes. Por ejemplo, por la aplicación directa de los EPI a los uniformes de las variables aleatorias en $A,B \subset \mathbb{R}^n$ y, a continuación, utilizando la desigualdad de Jensen, solamente se obtiene una forma débil $$ |A+B|^{1/n} \geq \sqrt{ (|A|^{1/n})^2 + (|B|^{1/n})^2 }$$ de la Brunn-Minkowski desigualdad (comparar con (2)). El problema aquí, por supuesto, es que la suma de dos distribuidos de manera uniforme independiente de variables aleatorias es casi nunca distribuidos de manera uniforme.

20voto

Daryl Puntos 41

$\newcommand{\R}{\mathbb{R}}$, En realidad, para los subconjuntos compactos $A, B\subset \R^n$, la desigualdad \begin{equation*} m(A+B)^{1/n} \ge m(A)^{1/n} + m(B)^{1/n} \end{ecuación*} es en última instancia nada pero la convexidad de $\log(1+e^x)$ in disguise (cuya convexidad a su vez se sigue inmediatamente de la AM-GM de la desigualdad).

Esta idea, y todo el inductivo pruebas se pueden encontrar en el Teorema de 2.3.9, Nociones de Convexidad, L. Hörmander (2007, Birkhäuser); este es un excelente libro que cualquier persona con interés en la convexidad definitivamente deben propio!

La idea de la prueba es mostrar esta desigualdad al $A$ e $B$ son los sindicatos de un número finito de distintos productos de los intervalos, por inducción sobre el número de intervalos que componen $A$ e $B$.

Sólo voy a citar el caso base: aquí $A$ e $B$ son los intervalos de longitudes de lado $a_1,\ldots,a_k$ e $b_1,\ldots,b_k$, luego

\begin{equation*} m(A)^{1/n} +m(B)^{1/n} = \prod\nolimits_j a_j^{1/n} + \prod\nolimits_j b_j^{1/n} \le \prod\nolimits_j (a_j+b_j)^{1/n}, \end{ecuación*} donde la última desigualdad se sigue de la homogeneidad de los términos en ambos lados de la desigualdad en combinación con la convexidad de $\log(1+e^x)$.

7voto

Alicia Puntos 6

En cuanto a tu pregunta "me gustaría entender mejor por qué la geometría Convexa debe tener nada que ver con la teoría de la información, y que los naturales de las distribuciones de probabilidad asociadas a un conjunto convexo.", James Melbourne, Peng Xu y recientemente escribí un artículo (https://arxiv.org/abs/1604.04225) que explora exhaustivamente paralelismos entre la teoría de la información y convexa de la geometría, en particular, en la semejanza entre el Brunn-Minkowski desigualdad (IMC) y la entropía de alimentación de la desigualdad (EPI).

Permítanme aclarar algunos de los puntos clave:

1) Como Terry señala, a priori, la semejanza entre las dos desigualdades no tiene nada que ver con la convexidad. De hecho, el IMC tiene arbitrarias de conjuntos de Borel en $\mathbb{R}^d$, mientras que la EPI tiene arbitrarias de Borel medidas de probabilidad en $\mathbb{R}^d$. (Para esto último, se debe utilizar la convención que $N(X)=e^{2h(X)/d}$ se establece en 0 si la entropía $h(X)=-\int f\log f$ con $f$ la densidad de $X$ no está definido o si la distribución de los $X$ no tiene una densidad. Ver Bobkov y Chistyakov, "la Entropía de Alimentación de la Desigualdad de la Entropía de Rényi", IEEE Trans. en la Info. Teoría, 2015, de por qué esta convención es esencial.)

2) Tanto el IMC y la EPI puede ser visto como casos especiales de la entropía de Rényi desigualdades-- una forma de ver esto es a través de los Jóvenes de la desigualdad, con fuertes constante como se ha señalado por Ofer (de hecho, Dembo-Cover-Thomas señaló que los Jóvenes-Beckner la desigualdad puede escribirse en una forma similar a la EPI, pero con tres diferentes Rényi entropías aparecer), y la otra es verlo a través de una reorganización basada en la unificación desarrollado en este trabajo de Liyao Wang y yo: https://arxiv.org/abs/1307.6018. El último de la unificación, que se basa en el Rogers-Brascamp-Lieb-Luttinger de reordenamiento de la desigualdad, tiene el siguiente bien cuidada formulación: $$ (1) \quad\quad\quad h_p(X_1 + \cdots + X_k)\geq h_p(X_1^* + \cdots + X_k^*) $$ donde $h_p(X)=\frac{1}{1-p}\log \int f^p$ es la entropía de Rényi $X$ orden $p$, y para cualquier $X$ con densidad $f$, $X^*$ es un vector aleatorio extraído de la densidad de $f^*$ que es la esféricamente simétrica, la disminución de reordenamiento de $f$. Tenga en cuenta que $h_1(X)$ es sólo el de la entropía de Shannon $h(X)$, $h_0(X)=\log |K|$ si $K$ es el apoyo de $X$, e $h_\infty(X)=\log \|f\|_\infty$.

3) Para ver que (1) es válida la unificación, la siguiente observación es útil. El IMC puede escribirse en la forma $|A_1 +A_2|\geq |B_1+B_2|$ donde $B_i$ son Euclidiana bolas de satisfacciones $|B_i|=|A_i|$ por cada $i$. Del mismo modo la EPI puede reescribirse en la forma $N(X_1+X_2)\geq N(Z_1+Z_2)$ donde $Z_i$ son independientes, esféricamente simétrica aleatoria Gaussiana vectores de satisfacciones $N(X_i)=N(Z_i)$ por cada $i$. Ahora vemos que el $p=0$ caso de la desigualdad (1) es, precisamente, esta forma alternativa de la IMC. Además, como se muestran en nuestro papel con Wang, la EPI puede ser derivado de la $p=1$ versión de (1) (que a su vez puede ser visto como un refuerzo de la EPI, en el sentido de que se inserta el plazo $h(X_1^* + \cdots + X_k^*)$ entre los términos de $h(X_1 + \cdots + X_k)$ e $h(Z_1 + \cdots + Z_k)$ que aparecen en la forma alternativa de la EPI).

4) Hay una función especial para convexidad en la Brunn-Minkowski mundo, por supuesto. Aunque el índice de masa corporal en sí mismo tiene mucho más general, establece, muchos de los más sofisticados resultados en geometría convexa (los ejemplos incluyen el Rogers-Shephard la desigualdad, mezcla de volúmenes y la Alexandrov-Fenchel teoría, y la inversa de Brunn-Minkowski desigualdad de V. Milman que juega un papel importante en geometría análisis funcional) son especiales para conjuntos convexos. No es, como se sospecha, un análogo en el mundo de la probabilidad de medidas. De hecho, C. Borell desarrollado en la década de 1970 una hermosa e históricamente menospreciada teoría de la "convexo medidas"-- de los cuales el más conocido de la clase de registro-cóncavo medidas de forma un distinguido subconjunto. Digamos (yo soy la omisión de algunos puntos finos para no hacer que esta respuesta es demasiado largo) que una medida es registro-cóncavo cuando el logaritmo de su densidad es de registro-cóncavo; por lo tanto log-cóncava medidas incluyen todos los Gaussiano medidas, medidas uniformes en cuerpos convexos, exponencial, medidas, etc. Luego resulta que muchas de las desigualdades que se mantenga para conjuntos convexos, pero no en general los conjuntos análogos que puede enunciarse de la entropía de las desigualdades de retención para el registro-cóncavo probabilidad de medidas, pero no en general la probabilidad de medidas. Esta historia es sólo parcialmente desarrollado y sigue habiendo muchos interesantes preguntas abiertas; todo lo que se sabe hasta finales de 2016, junto con muchas preguntas abiertas se describen en nuestra encuesta en https://arxiv.org/abs/1604.04225.

6voto

xelurg Puntos 1655

Esta no es una respuesta completa, sino más bien una demasiado larga comentario:

Tanto la entropía de alimentación de la desigualdad (EPI) y la (en general, no sólo para conjuntos convexos) Brunn-Minkowski desigualdad seguir de los Jóvenes de la desigualdad. Véase la sección III-B en http://www-isl.stanford.edu/people/cover/papers/dembo_cover_thomas_91.pdf Así que no es que ellos vienen de diferentes básica de las desigualdades.

Por otro lado, como usted señala, EPI implica la desigualdad de Minkowski $$|\det (a+B)|^{1/n} \geq |\det (A)|^{1/n}+|\det (B)|^{1/n}$$ for positive definite $a,B$. En los giros, se implica el BM para las cajas. Hay un argumento (el Hadwiger-Ohmann interseccion, consulte la página 12 en el artículo de Gardner que usted cita) que las transferencias de la desigualdad a lo finito de la unión de las cajas, y, por tanto, en general los conjuntos de Borel. Sin embargo, no hay nada especial acerca de conjuntos convexos en este argumento.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X