¿Qué norma del error de reconstrucción es minimizada por la matriz de aproximación de bajo rango obtenida con PCA?

Question

Dada una aproximación PCA (o SVD) de la matriz $X$ con una matriz $\hat X$ sabemos que $\hat X$ es la mejor aproximación de bajo rango de $X$ .

¿Esto está de acuerdo con la inducido $\parallel \cdot \parallel_2$ norma (es decir, la norma del mayor valor propio) o según la norma de Frobenius $\parallel \cdot \parallel_F$ ¿norma?

Answer 1

Respuesta de una sola palabra: Ambos.

---

Empecemos por definir las normas. Para una matriz $X$ , operador $2$ -se define como $$\|X\|_2 = \mathrm{sup}\frac{\|Xv\|_2}{\|v\|_2} = \mathrm{max}(s_i)$$ y la norma de Frobenius como $$\|X\|_F = \sqrt {\sum_{ij} X_{ij}^2} = \sqrt{\mathrm{tr}(X^\top X)} = \sqrt{\sum s_i^2},$$ donde $s_i$ son valores singulares de $X$ es decir, los elementos diagonales de $S$ en la descomposición del valor singular $X = USV^\top$ .

El PCA viene dado por la misma descomposición del valor singular cuando los datos están centrados. $US$ son componentes principales, $V$ son ejes principales, es decir, vectores propios de la matriz de covarianza, y la reconstrucción de $X$ con sólo el $k$ componentes principales correspondientes al $k$ valores singulares más grandes viene dado por $X_k = U_k S_k V_k^\top$ .

Le site Teorema de Eckart-Young dice que $X_k$ es la matriz que minimiza la norma del error de reconstrucción $\|X-A\|$ entre todas las matrices $A$ de rango $k$ . Esto es cierto tanto para la norma de Frobenius como para el operador $2$ -norma. Como señala @cardinal en los comentarios, fue demostrada por primera vez por Schmidt (de la fama de Gram-Schmidt) en 1907 para el caso de Frobenius. Más tarde fue redescubierto por Eckart y Young en 1936 y ahora se asocia principalmente con sus nombres. Mirsky generalizó el teorema en 1958 a todas las normas que son invariantes bajo transformaciones unitarias, y esto incluye la norma 2 del operador.

Este teorema se denomina a veces teorema de Eckart-Young-Mirsky. Stewart (1993) lo llama teorema de aproximación de Schmidt. Incluso he visto que se llama teorema de Schmidt-Eckart-Young-Mirsky.

• Eckart y Young, 1936, La aproximación de una matriz por otra de menor rango
• Mirsky, 1958, Funciones gauge simétricas y normas unitariamente invariantes
• Stewart, 1993, Sobre la historia temprana de la descomposición del valor singular

---

Prueba para el operador $2$ -norma

Dejemos que $X$ ser de rango completo $n$ . Como $A$ es de rango $k$ su espacio nulo tiene $n-k$ dimensiones. El espacio que abarca el $k+1$ vectores singulares derechos de $X$ correspondiente a los mayores valores singulares tiene $k+1$ dimensiones. Así que estos dos espacios deben intersecarse. Sea $w$ sea un vector unitario de la intersección. Entonces obtenemos: $$\|X-A\|^2_2 \ge \|(X-A)w\|^2_2 = \|Xw\|^2_2 = \sum_{i=1}^{k+1}s_i^2(v_i^\top w)^2 \ge s_{k+1}^2 = \|X-X_k\|_2^2,$$ QED.

---

Prueba para la norma de Frobenius

Queremos encontrar la matriz $A$ de rango $k$ que minimiza $\|X-A\|^2_F$ . Podemos factorizar $A=BW^\top$ , donde $W$ tiene $k$ columnas ortonormales. Minimizando $\|X-BW^\top\|^2$ por el hecho de ser fijo $W$ es un problema de regresión con solución $B=XW$ . Conectándolo, vemos que ahora tenemos que minimizar $$\|X-XWW^\top\|^2=\|X\|^2-\|XWW^\top\|^2=\mathrm{const}-\mathrm{tr}(WW^\top X^\top XWW^\top)\\=\mathrm{const}-\mathrm{const}\cdot\mathrm{tr}(W^\top\Sigma W),$$ donde $\Sigma$ es la matriz de covarianza de $X$ es decir $\Sigma=X^\top X/(n-1)$ . Esto significa que el error de reconstrucción se minimiza tomando como columnas de $W$ algunos $k$ vectores ortonormales que maximizan la varianza total de la proyección.

Es bien sabido que estos son los primeros $k$ vectores propios de la matriz de covarianza. En efecto, si $X=USV^\top$ entonces $\Sigma=VS^2V^\top/(n-1)=V\Lambda V^\top$ . Escribir $R=V^\top W$ que también tiene columnas ortonormales, obtenemos $$\mathrm{tr}(W^\top\Sigma W)=\mathrm{tr}(R^\top\Lambda R)=\sum_i \lambda_i \sum_j R_{ij}^2 \le \sum_{i=1}^k \lambda_k,$$ con el máximo alcanzado cuando $W=V_k$ . El teorema se deduce inmediatamente.

Vea los siguientes tres hilos relacionados:

• ¿Cuál es la función objetivo del ACP?
• ¿Por qué el PCA maximiza la varianza total de la proyección?
• Función objetivo del ACP: ¿cuál es la relación entre la maximización de la varianza y la minimización del error?

---

Intento anterior de demostración de la norma de Frobenius

Esta prueba la encontré en algún sitio de internet pero está mal (contiene un hueco), como explica @cardinal en los comentarios.

La norma de Frobenius es invariante bajo transformaciones unitarias, porque no cambian los valores singulares. Así que obtenemos: $$\|X-A\|_F=\|USV^\top - A\| = \|S - U^\top A V\| = \|S-B\|,$$ donde $B=U^\top A V$ . Continuando: $$\|X-A\|_F = \sum_{ij}(S_{ij}-B_{ij})^2 = \sum_i (s_i-B_{ii})^2 + \sum_{i\ne j}B_{ij}^2.$$ Esto se minimiza cuando todos los elementos no diagonales de $B$ son cero y todos $k$ Los términos diagonales anulan el $k$ mayores valores singulares $s_i$ [hueco aquí: esto no es obvio] es decir $B_\mathrm{optimal}=S_k$ y por lo tanto $A_\mathrm{optimal} = U_k S_k V_k^\top$ .