Evaluar la aproximación del ACP a partir de algoritmos aleatorios

Question

He estado comparando diferentes implementaciones de PCA (algunas mediante el cálculo explícito de la matriz de covarianza, otras con SVD aleatorio/truncado) en términos de velocidad, y ahora quería comparar lo bueno diferentes algoritmos aleatorios aproximan la solución exacta (a la precisión numérica) a través de la matriz de covarianza.

¿Hay alguna métrica sugerida para evaluar la similitud de dos bases de vectores propios resultantes, es decir, la $k$ ¿vectores propios devueltos?

Mi intuición sería afirmar que los vectores tienen la misma "dirección general" (es decir, en caso de que la primera dimensión no coincida con las direcciones, un vector estaría volteado), y luego calcular

1. la norma de Frobenius de la matriz de valor absoluto $abs(A)=abs(X-V)$ , donde $X$ es la solución exacta y $V$ la matriz resultante de un algoritmo aleatorio que contiene los vectores propios, o
2. Una versión modificada/ponderada de la distancia euclidiana, sobre los vectores pares. Es decir, $$ \mathcal{L}(X,V)=\sum_{j=0}^k \omega_j \sum_{i=0}^n \sqrt{(a_{ji}-x_{ji})^2}$$ donde $\omega_j$ es un peso para el $j$ -Cuarto PC, $n$ la dimensión de los vectores propios, y $a_{ji}$ y $x_{ji}$ los elementos de las matrices de vectores propios, respectivamente.

La razón de la segunda versión podría ser que quiero tener una mejor aproximación para los primeros componentes (ya que explican más de la varianza; tal vez incluso ponderarlos en función de esa varianza explicada), y no preocuparme tanto por el último porcentaje de varianza restante repartido en múltiples dimensiones, acumulando potencialmente una gran pérdida.

Answer 1

Por lo general, en este tipo de cosas lo que realmente importa es la similitud de los subespacios en lugar de los vectores de base particulares, ya que se podría mantener el subespacio igual pero cambiar los vectores propios particulares en gran medida.

He aquí un ejemplo: suponga que sus características no están correlacionadas, de modo que acaba teniendo una matriz de covarianza de $C :=\text{diag}(1,1,0)$ . Tomar los dos primeros vectores propios es razonable en este caso. Pero, ¿qué son? Se trata de un espacio propio bidimensional, así que, por ejemplo $$ B_1 = \left(\begin{array}{cc}1 & 0 \\ 0 & 1 \\ 0 & 0\end{array}\right), B_2 = \frac{1}{\sqrt 2}\left(\begin{array}{cc}1 & 1 \\ -1 & 1 \\ 0 & 0\end{array}\right) $$ ambos proporcionan bases ortonormales. Así que si sólo miras las entradas, podrías calcular $\|B_1-B_2\|_F = 2$ pero eso es injusto porque en realidad ambas son bases exactamente correctas para el mismo espacio.

Esa es la motivación de esta distancia: para dos matrices $A$ y $B$ con columnas ortonormales, considere $$ d(A, B) := \|P_A - P_B\| $$ donde $\|\cdot\|$ denota la norma del operador y para una matriz $X$ , $P_X = X(X^TX)^{-1}X^T$ es la matriz que se proyecta en el espacio de columnas de $X$ . Tenga en cuenta que $$ AA^T = A(A^TA)^{-1}A^T = P_A $$ y de forma similar para $B$ por lo que al tener columnas ortonormales obtenemos $$ d(A,B) = \|AA^T-BB^T\|. $$

Supongamos que $A$ y $B$ tienen exactamente los mismos espacios de columna. Para una matriz $M$ , $\|M\|^2 = \lambda_{\max}(M^TM)$ así que considera $$ (P_A - P_B)^T(P_A - P_B) = P_A + P_B - P_BP_A - P_AP_B $$ por ser las matrices de proyección simétricas e idempotentes. $P_A$ está completamente en el espacio de columnas de $A$ y de forma similar para $P_B$ Así que si $A$ y $B$ tienen el mismo espacio de columna entonces $P_BP_A = P_B$ y $P_AP_B = P_A$ en cuyo caso $$ P_A + P_B - P_BP_A - P_AP_B = 0. $$ Para comprobarlo, se puede calcular que $B_1B_1^T -B_2B_2^T = 0$ .

Además, dejemos que $Q$ sea una rotación de las columnas y la aplique a $B$ , digamos, a través de $BQ$ . Entonces $$ P_A - P_{BQ} = AA^T - BQ(Q^TB^TBQ)^{-1}Q^TB^T = P_A - P_B $$ por lo que esta métrica es invariante a las rotaciones de los vectores base. Es una buena propiedad para este tipo de cosas.

Este $d$ aparece como una métrica en el Grassmanian (ver aquí en particular) aunque sé muy poco sobre la teoría general de estas cosas, pero eso podría darte algún lugar donde buscar más.

Otra referencia que probablemente sea útil para trabajar con este tipo de cosas es el libro de Stewart y Sun Teoría de la Perturbación Matricial ya que el efecto del ruido en las proyecciones es exactamente el tipo de cosa que estudia la teoría de perturbaciones matriciales.