Suma de productos vectoriales de matrices

Question

Consideremos una secuencia de $n$ por $n$ matrices $A_i$ cuyas entradas se eligen entre $\{0,1\}$ y una secuencia de aleatorios independientes $n$ vectores dimensionales $x_i$ cuyas entradas también se eligen independientemente de $\{0,1\}$ . Supongamos que $n$ es grande.

Sabemos que $H(A_ix_i) = n$ . Esto se debe a que $A_i$ es invertible y por tanto $A_ix_i$ nos dice con precisión cuáles son los valores de $x_i$ son.

Estoy interesado en $$y=H\left(\sum_{i=1}^{\ell} A_ix_i\right)$$ y, en particular, en qué circunstancias $y$ mucho mayor que $n$ ?

Sabemos que si cada $A_i$ es idéntica y cada una es simplemente la matriz identidad, entonces $y = nh_B(\ell)$ eran $h_B(t) = H(B(t,1/2))$ . Por lo tanto, en estas circunstancias $y \approx C_1n\log_2{\ell}$ para alguna constante $C_1 >0$ .

¿Qué propiedades tienen las matrices $A_i$ tienen que tener para $y$ sea de la forma $C_2n\ell$ para alguna constante $C_2>0$ ?

Parece plausible que al menos las matrices $A_i$ debe ser denso para garantizar que el rango de valores de cada entrada de $A_ix_i$ puede tomar es lo suficientemente grande. Pero, ¿es suficiente?

Answer 1

Una sugerencia (boceto):

1. El problema (dejando de lado la no singularidad de $A_i$ que no debería ser necesario - debería ser un resultado) se puede poner en esta forma equivalente: que $x$ sea la concatenación de $\ell$ casos de $x_i$ Así que $w=Bx$ donde $B$ es un binario $ n\times m$ matriz, $m=n \ell$ (en la declaración original $\ell = \lfloor\log_2{n}\rfloor $ pero no lo impondremos). (Puede ser preferible utilizar $\{-1,1\}$ en lugar de $\{0,1\}$ para $x$ y/o para $B$ ).

2. Para grandes $n$ , $w$ tiende a una gaussiana multivariante, su entropía tiende a $H(w)=\frac{1}{2}\log(|2 \pi e B B^t|)$ . La tarea, entonces, es maximizar $|B B^t|$ sometido a $B$ ser binario. [*]

3. Véase aquí (página 2, problema 2)

[*] Actualización: Tal vez esto pueda ser más convincente en la formulación original: $w =B x = \sum_{i=1}^\ell A_i x_i=\sum_{i=1}^\ell w_i$ donde $A_i$ son cuadrados $n\times n$ . Entonces, suponiendo $x_i \in\{-1,1\}$ , $E(w_i)=0$ , $Cov(w_i)=A_i A_i^t$ Entonces podemos aplicar el CLT multivariante para demostrar que $w$ tiende a un $N(0,\sum_i A_i A_i^t)$ distribución.