45 votos

¿Anticoncentración destinada a permanentes de matrices gaussianas?

En un trabajo reciente con Alex Arkhipov en "La Complejidad Computacional Lineal Óptica," necesitamos asumir una razonable sonido probabilística de la conjetura: a saber, que la permanente de una matriz de yo.yo.d. Gauss entradas es "demasiado concentrada alrededor de 0." He aquí una declaración formal de nuestra conjetura:

Existe un polinomio $p$ tal que para todos los $n$ e $\delta>0$, $\Pr_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[\left\vert \operatorname*{Per}\left( X\right) \right\vert \leq \frac{\sqrt{n!}}{p\left( n/\delta\right) }\right] \leq \delta. $

Esta conjetura parece muy interesante, incluso fuera de nuestra aplicación, así que me quiso llevar a la atención de la gente-tal vez hay una sencilla/conocido prueba de que estamos perdiendo!

Aquí es lo que sabemos:

  1. La expectativa de Per(X) es de curso 0 (por simetría), mientras que la desviación estándar es $\sqrt{n!}$. Por lo tanto, nuestra conjetura, básicamente, dice que "Por(X) es exponencialmente más pequeño que su desviación estándar sólo un 1/poli(n) de la fracción del tiempo."
  2. Recientemente, Terry Tao y Van Vu resultó ser un maravilloso anti-concentración obligado para los permanentes de Bernoulli matrices, que puede ser enunciada de la siguiente manera: para todos los $\varepsilon > 0$ y suficientemente grande n, $\Pr_{X\in\left\{ -1,1\right\} ^{n\times n}}\left[ \left\vert \operatorname*{Por}\left( X\right) \right\vert \leq \frac{\sqrt{n!}% }{n^{\varepsilon n}}\right] \leq \frac{1}{n^{0.1}}.$ Por desgracia, su resultado se queda corto de lo que necesitamos en tres aspectos. En primer lugar, es de Bernoulli matrices en lugar de Gauss de las matrices. (Aunque, por supuesto, el de Gauss caso bien podría ser más fácil que en el caso de Bernoulli, que es nuestra principal razón para el optimismo!) Segundo, y más importante, el Tao y el Vu solo demostrar que Por(X) es de al menos 1/nes la fracción de su desviación estándar, con alta probabilidad, mientras que necesitamos que al menos un 1/poli(n) de la fracción. Tercero, ellos-límite superior de la probabilidad de un "evento malo" por 1/n0.1, mientras que nos gustaría-límite superior es por 1/p(n) para cualquier polinomio p.
  3. La evidencia numérica que hemos obtenido es muy consistente con nuestra conjetura de ser verdad (ver figura de abajo).
  4. Podemos demostrar que nuestra conjetura tiene el factor determinante en el lugar de la permanente. Para ello, utilizamos el hecho de que si X es Gaussiana, entonces, debido a la rotación de la invariancia de la Gaussiana de la medida, no hay una fórmula explícita para todos los momentos de Det(X) -- incluso las fracciones y la inversa momentos.
  5. Uno podría preguntarse si también podemos calcular los momentos de orden superior de Per(X), y el uso que para probar nuestra conjetura. De hecho, se puede demostrar que $\operatorname*{E}_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[ \left\vert \operatorname*{Per}\left( X\right)\right\vert ^{4}\right] =\left( n!\right) ^{2}\left( n+1\right)$, lo que implica entonces la siguiente débil contra la concentración de la envolvente: para todos β<1, $\Pr_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[ \left\vert \operatorname*{Por}\left( X\right) \right\vert \geq \beta\sqrt{n!}\right] \geq\frac{\left( 1-\beta^{2}\right) ^{2}}{n+1}$. Por desgracia, la informática, la 6ª, 8ª, y más momentos parece difícil.

Consulte la sección 8 de nuestro papel para las pruebas 4 y 5.

Corto de probar nuestros anti-concentración de conjeturas, aquí hay dos más fáciles de preguntas cuyas respuestas también sería de mucho interés:

  • Podemos, al menos, redarguye Tao y Vu enlazado Gaussiana matrices en lugar de Bernoulli matrices? En su artículo, Tao y Vu decir que el resultado se mantiene para "prácticamente ninguna (no degenerado) distribución discreta." Yo no creo que la distribución Gaussiana presente graves dificultades, pero no estoy seguro.
  • ¿El pdf de Per(X) difieren en el origen? (No sabemos la respuesta a esa pregunta en el caso de Det(X).) No sé de ningún formal implicaciones entre esta pregunta y la anti-concentración pregunta, pero sería de gran respuesta de todos modos.

alt text(fuente: Wayback Machine)

43voto

steevc Puntos 211

Hice un análisis preliminar de viabilidad de nuestros métodos, y es posible que uno puede ser capaz de ajustar nuestros $n^\epsilon$ de pérdida a algo más parecido a $\exp( \sqrt{n} )$ en el caso Gaussiano, pero esto es todavía muy por debajo de lo que usted desea. El principal obstáculo es el potencial de acoplamiento entre los permanentes de los menores de edad, que no fueron capaces de evitar.

Aquí está la heurística de cálculo. Supongamos que una Gaussiana $k \times k$ permanente tiene algunos distribución $P_k$. A continuación, una Gaussiana $k+1 \times k+1$ fijos $P_{k+1}$, por cofactor de expansión, parece

$$ P_{k+1} = \sum_{i=1}^{k+1} (-1)^i x_i P_k^{(i)}$$

donde $x_i$ son iid Gaussianas y el $P_k^{(i)}$ son copias de $P_k$ correspondiente a las diversas $k \times k$ menores de la $k+1 \times k+1$ matriz.

Como las entradas de la $k+1 \times k+1$ matriz son iid, el $x_i$ son independientes de la $P_k^{(i)}$, por lo que para valores fijos de $P_k^{(i)}$, podemos ver que $P_{k+1}$ se distribuye normalmente con media cero y varianza $\sum_{i=1}^{k+1} |P_k^{(i)}|^2$, lo que podemos reescribir como

$$ P_{k+1} = (\sum_{i=1}^{k+1} |P_k^{(i)}|^2)^{1/2} \cdot N_{k+1}\qquad (1)$$

donde $N_{k+1}$ es una variable aleatoria normal estándar (independiente de la $P_k^{(i)}$).

Ahora nos encontramos con el problema clave: la $P_k^{(i)}$ son idénticamente distribuidas, pero no de forma conjunta independiente, porque hay una gran cantidad de superposición entre las $k \times k$ menores de edad. Así, mientras que de forma heurística que uno espera de la concentración de medida para patear en y $(\sum_{i=1}^{k+1} |P_k^{(i)}|^2)^{1/2}$ más concentrado que el de cualquiera de las $P_k^{(i)}$, no sabemos cómo prevenir enorme correlaciones suceda. En el peor de los casos, todas las $P_k^{(i)}$ están perfectamente correlacionados entre sí y, a continuación, (1), podría convertirse en algo más parecido a

$$ P_{k+1} = (k+1)^{1/2} |P_k| \cdot N_{k+1}.$$

Este multiplicativo proceso normal llevaría a $P_n$ a concentrarse entre el $\sqrt{n!} \exp(-O(\sqrt{n}))$ e $\sqrt{n!} \exp(O(\sqrt{n}))$, como puede verse por la toma de los registros y aplicando el teorema del límite central.

Pero esta peor de los casos en realidad no puede ser la verdad - entre otras cosas, que contradice el segundo momento de cálculo. Así que debe haber alguna forma de evitar esta correlación. Por desgracia, mi papel con Van completamente evade este problema - tratamos de llegar tan lejos como podemos simplemente del hecho obvio de que la desunión los menores de edad son independientes el uno del otro. Esta es la razón por la que nuestros límites son significativamente peor que la de $\exp(O(\sqrt{n}))$ a partir de la verdad.

Como usted dice, la situación es mucho mejor que el determinante de una Gaussiana iid de la matriz. Aquí, se puede utilizar la base de veces la altura de la fórmula para expresar el determinante de un producto de $\prod_{i=1}^n \hbox{dist}(X_i,V_i)$ donde $X_i$ es el $i^{th}$ fila y $V_i$ es el lapso de la primera $i-1$ filas. Con todo lo que se Gaussiano, $\hbox{dist}(X_i,V_i)^2$ es una distribución chi-squared, que es una martingala en $i$, y, como consecuencia, se puede obtener el factor determinante dentro de $\exp(O(\sqrt{\log n}))$ de % de$\sqrt{(n-1)!}$, lo que le dará lo que usted desea. Por desgracia, no hay nada como la base de veces la altura de la fórmula para la permanente...

Por último, estoy bastante seguro de que, en el nivel de $n^{-\epsilon n}$ de pérdidas, se puede replicar nuestro papel en el caso de Bernoulli para el caso Gaussiano. No creo que el $n^{-\epsilon n}$ de pérdida es mucho mejor en ese caso, pero el $\frac{1}{n^{0.1}}$ bound debe mejorar sustancialmente.

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