¿Es "proyección aleatoria" estrictamente hablando no una proyección?

Las implementaciones actuales del algoritmo de proyección aleatoria reducen la dimensionalidad de las muestras de datos al mapearlas de $\mathbb R^d$ a $\mathbb R^k$ usando una matriz de proyección $d\times k$$R$ cuyas entradas son iid de una distribución adecuada (por ejemplo, de $\mathcal N(0,1)$ ):

$x^\prime = \frac{1}{\sqrt k}xR$

Convenientemente, existen pruebas teóricas que muestran que este mapeo conserva aproximadamente las distancias por pares.

Sin embargo, recientemente encontré estas notas donde el autor afirma que este mapeo con una matriz aleatoria no es una proyección en el sentido estrictamente algebraico lineal de la palabra (página 6). De las explicaciones dadas allí, esto se debe a que las columnas de $R$ no son estrictamente ortogonales cuando sus entradas se eligen independientemente de $\mathcal N(0,1)$ . Por lo tanto, las versiones anteriores de RP donde se aplicaba la ortogonalidad de las columnas de $R$ pueden considerarse como una proyección.

¿Puede proporcionar una explicación más detallada de (1) cuál es la definición de una proyección en este sentido estricto y (2) por qué no es una proyección RP bajo esta definición?

1. ¿Cuál es la definición de una proyección en este sentido estricto (algebraico lineal) (de la palabra)

   https://en.wikipedia.org/wiki/Projection_(linear_algebra)

   En álgebra lineal y análisis funcional, una proyección es una transformación lineal $P$ desde un espacio de vector a sí mismo que tales $P^2 = P$ . Es decir, cuando $P$ se aplica dos veces a cualquier valor, da el mismo resultado que si se aplicara una vez (idempotente).

   Para la proyección ortogonal o la proyección vectorial, tiene eso

   https://en.wikipedia.org/wiki/Projection_(linear_algebra)

   Una proyección ortogonal es una proyección para la cual el rango U y el espacio nulo V son subespacios ortogonales.

2. ¿Por qué no es RP una proyección bajo esta definición?

   Michael Mahoney escribe en sus notas de clase que depende de cómo se construya el RP , si el RP es o no una proyección en el sentido algebraico lineal tradicional. Esto lo hace en los puntos tercero y cuarto:

   Tercero, si los vectores aleatorios fueran exactamente ortogonales (como en realidad estaban en las construcciones JL originales), entonces tendríamos que la proyección JL era una proyección ortogonal

   ...

   pero aunque esto es falso para los gaussianos, las variables aleatorias $\lbrace \pm \rbrace$ y la mayoría de las otras construcciones, se puede demostrar que los vectores resultantes tienen aproximadamente una longitud unitaria y aproximadamente ortogonales

   ...

   esto es "suficientemente bueno".

   Por lo tanto, podría hacer, en principio, la proyección aleatoria con una construcción diferente que se limita a las matrices ortogonales (aunque no es necesario). Ver por ejemplo el trabajo original:

   Johnson, William B. y Joram Lindenstrauss. "Extensiones de mapeos de Lipschitz en un espacio de Hilbert". Matemáticas contemporáneas 26.189-206 (1984): 1.

   ... si uno elige al azar una proyección ortogonal de rango $k$ en $l_2^n$

   ...

   $Q$$k$$l_2^n$$\sigma$$O(n)$$l_2^n$

   $$f: (O(n), \sigma) \to L(l_2^n)$$ $$f(u) = U^\star Q U$$ $k$

   La entrada de wikipedia describe la proyección aleatoria de esta manera (lo mismo se menciona en las notas de clase en las páginas 10 y 11)

   https://en.wikipedia.org/wiki/Random_projection#Gaussian_random_projection

   $S^{d − 1}$

   Pero generalmente no obtienes esta ortogonalidad cuando tomas todas las entradas de matriz en la matriz variables aleatorias e independientes con una distribución normal (como Whuber mencionó en su comentario con una consecuencia muy simple "si las columnas siempre fueran ortogonales, sus entradas podrían no ser independiente ").

   $R$$P = R^TR$$b = R^T x$$x' = Rb = R^TRx$$R^TR$

   $P=R^TR$$U$

   $range(P^T P)$$\lbrace 0, 1 \rbrace$

   ^{$P$$R$$P = R^TR$$R$}

   Entonces, la proyección aleatoria de diferentes construcciones, como el uso de entradas aleatorias en la matriz, no es exactamente igual a una proyección ortogonal. Pero es computacionalmente más simple y, según Michael Mahoney, es "lo suficientemente bueno".

Eso es correcto: "proyección aleatoria" es estrictamente hablando, no una proyección.

$P$$P^2 = P$

$d\times k$$R$$k\ll d$

$R$$d\times k$$U$

$d\times k$$R$$R$$x\in \mathbb R^d$$R$

$p = xR(R^TR)^{-1}R^T$$p\in\mathbb R^d$

$R$$R^TR = I\in \mathbb R^{k\times k}$$x$$R$

$p = xRR^T$$p\in\mathbb R^d$

$RR^T\in\mathbb R^{d\times d}$$(RR^T)^2=RR^TRR^T=RR^T$

$R$$\mathbb R^k$$\mathbb R^d$$x\in\mathbb R^d$$xRR^T$$R$$RR^T$

Le agradecería que pudiera confirmar / corregir mi razonamiento aquí.

Referencia:

[1] http://www.dankalman.net/AUhome/classes/classesS17/linalg/projections.pdf

Si utiliza el cambio de signo aleatorio o la permutación antes de la transformación Fast Walsh Hadamard, la proyección aleatoria es ortogonal.