Cómo calcular el valor esperado de las normas de la matriz de $A^TA$ ?

Question

Deje que $A$ ser un azaroso $m$ por $n$ matriz de signos rectangular, elegida uniformemente al azar, con $m < n$ . Para que quede claro, $A$ es una matriz cuyas entradas se eligen de $\{1,-1\}$ .

Deje que $B = A^T A$ . Sabemos, por ejemplo, que $B$ es un cuadrado y simétrico $n$ por $n$ matriz con todas sus entradas diagonales iguales a $m$ exactamente. Estoy tratando de aprender cómo calcular la esperada Frobenius y norma espectral de $B$ . Podemos asumir que ambos $m$ y $n$ son grandes si eso ayuda a dar una buena estimación.

¿Cómo puedes calcular $ \mathbb {E}(||B||_F)$ y $ \mathbb {E}(||B||_2)$ ?

La esperada norma Frobenius de $B$ se define como

$$ \mathbb {E}(||B||_F)= \mathbb {E} \left ( \sqrt { \sum_ {i=1}^n \sum_ {j=1}^n |b_{ij}|^2} \right ) $$

donde $b_{ij}$ son los elementos de $B$ .

La norma espectral esperada de $B$ se define como

$$ \mathbb {E}(||B||_2)= \mathbb {E} \left ( \max_ {|x|_2 \ne 0} \frac {|Bx|_2}{|x|_2} \right ). $$

---

Se ha puesto en la mira a http://mathoverflow.net/questions/222994/how-to-calculate-expected-value-of-matrix-norms-of-ata ahora. Actualizaré esta pregunta si se añade algo sustancial.

Answer 1

Aquí está un intento. Las entradas de la matriz son variables aleatorias de Bernoulli, que obtienen un valor de $ \pm 1$ . Una variable aleatoria de Bernoulli es una variable subgaussiana media cero con momentos finitos.

Si definimos $ \lambda = m/n$ entonces para grandes valores de $m,n$ :

$ \Vert A \Vert_2 \rightarrow \sqrt {n} \left (1+ \sqrt\lambda \right )$

y por lo tanto, $ \Vert B \Vert_2 \rightarrow n \left (1+ \sqrt\lambda \right )^2$

Asintóticamente, $ \Vert A \Vert_2 = \sqrt m+ \sqrt n$ y $ \Vert B \Vert_2 =( \sqrt m + \sqrt n)^2$ .

Aquí está la referencia que usé: http://www-personal.umich.edu/~romanv/papers/rv-rectangular-matrices.pdf

Otra buena referencia es "El valor singular más pequeño de las matrices aleatorias y la geometría de los politopos aleatorios" de Litvak et al.

Lo intenté en MATLAB y parece que funciona bien:

A = signo(rand(1e5,10)-0.5); c = 10/1e5;

sqrt(1e5)*(1+sqrt(c))

ans =

319.3900

norma(A)

ans =

318.8748

Ahora, para la norma Frobenius. El objetivo es calcular para el inicio $ \mathbb {E}( \Vert B \Vert_F ^2)$ . Dividámoslo en dos casos:

1) La parte diagonal: muy simple, ya que los elementos son siempre $m$ la contribución total de la diagonal es $nm^2$ .

2) La parte fuera de la diagonal ( $i \neq j$ ): observe que $ \mathbb {E}(b_{ij})=0$ para $i \neq j$ así que usando los hechos que las casas rodantes son identificadas, obtenemos..: $ \mathbb {E}(b_{ij}^2)= \mathrm {Var}( \sum_k a_{ik}a_{jk})= \sum_k \mathrm {Var}(a_{ik}a_{jk})=m$ (de nuevo, por $i \neq j$ ). En resumen, $n(n-1)$ elementos fuera de la diagonal.

Resumiendo, todo da: $ \mathbb {E}( \Vert B \Vert_F ^2)=nm^2+n(n-1)m=nm^2+n^2m-mn$ .

Usando la desigualdad de Bernstein para las variables aleatorias de Bernoulli con probabilidad $ \frac {1}{2}$ para las matrices grandes la variación decae exponencialmente, y por lo tanto $ \sqrt { \mathbb {E}( \Vert B \Vert_F ^2)} \rightarrow \mathbb {E}( \Vert B \Vert_F )$