Quelle norme d'erreur de reconstruction est minimisée par la matrice d'approximation de bas rang obtenue avec l'ACP?

Réponse en un seul mot: les deux.

$X$ $2$

‖ X ‖_{2} = s u p \frac{‖ X v ‖_{2}}{‖ v ‖_{2}} = m a x (s_{i})

$\|X\|_2 = \mathrm{sup}\frac{\|Xv\|_2}{\|v\|_2} = \mathrm{max}(s_i)$

‖ X ‖_{F} = \sqrt{\sum_{i j} X_{i j}^{2}} = t r (X^{⊤} X) = \sqrt{\sum s_{i}^{2}},

$\|X\|_F = \sqrt {\sum_{ij} X_{ij}^2} = \mathrm{tr}(X^\top X) = \sqrt{\sum s_i^2},$

s_{i}

$s_i$

X

$X$

S

$S$

X = U S V^{⊤}

$X = USV^\top$

L'ACP est donnée par la même décomposition en valeurs singulières lorsque les données sont centrées. $US$ sont les composantes principales, $V$ sont les axes principaux, c'est-à-dire les vecteurs propres de la matrice de covariance, et la reconstruction de $X$ avec seulement les $k$ composantes principales correspondant aux $k$ plus grandes valeurs singulières est donnée par $X_k = U_k S_k V_k^\top$ .

Le théorème d'Eckart-Young dit que est la matrice minimisant la norme de l'erreur de reconstructionparmi toutes les matrices de rang . Cela est vrai à la fois pour la norme Frobenius et pour l'opérateur -norm. Comme souligné par @cardinal dans les commentaires, cela a été prouvé pour la première fois par Schmidt (de la renommée Gram-Schmidt) en 1907 pour l'affaire Frobenius. Il a ensuite été redécouvert par Eckart et Young en 1936 et est maintenant principalement associé à leurs noms. Mirsky a généralisé le théorème en 1958 à toutes les normes qui sont invariantes sous les transformations unitaires, et cela inclut l'opérateur 2-norme. $X_k$ $\|X-A\|$ $A$ $k$ $2$

Ce théorème est parfois appelé théorème d'Eckart-Young-Mirsky. Stewart (1993) l'appelle le théorème d'approximation de Schmidt. Je l'ai même vu appelé théorème de Schmidt-Eckart-Young-Mirsky.

Eckart et Young, 1936, l'approximation d'une matrice par une autre de rang inférieur
Mirsky, 1958, Fonctions de jauge symétrique et normes invariantes unitaires
Stewart, 1993, Sur les débuts de la décomposition en valeurs singulières

Preuve pour l'opérateur -norm $2$

Soit de rang complet . Comme est de rang , son espace nul a dimensions. L'espace couvert par les vecteurs singuliers droits de correspondant aux plus grandes valeurs singulières a dimensions. Ces deux espaces doivent donc se croiser. Soit un vecteur unitaire de l'intersection. On obtient alors: QED. $X$ $n$ $A$ $k$ $n-k$ $k+1$ $X$ $k+1$ $w$

‖ X - A ‖_{2}^{2} \geq ‖ (X - A) w ‖_{2}^{2} = ‖ X w ‖_{2}^{2} = \sum_{i = 1}^{k + 1} s_{i}^{2} (v_{i}^{⊤} w)^{2} \geq s_{k + 1}^{2} = ‖ X - X_{k} ‖_{2}^{2},

$\|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,$

Preuve de la norme Frobenius

Nous voulons trouver la matrice de rang qui minimise . Nous pouvons factoriser , où a colonnes orthonormées. Minimiser pour fixe est un problème de régression avec la solution . En le branchant, nous voyons que nous devons maintenant minimiser où est la matrice de covariance de , c'est-à-dire $A$ $k$ $\|X-A\|^2_F$ $A=BW^\top$ $W$ $k$ $\|X-BW^\top\|^2$ $W$ $B=XW$

‖ X - X W W^{⊤} ‖^{2} = ‖ X ‖^{2} - ‖ X W W^{⊤} ‖^{2} = c o n s t - t r (W W^{⊤} X^{⊤} X W W^{⊤}) = c o n s t - c o n s t \cdot t r (W^{⊤} Σ W),

$\|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),$

Σ

$\Sigma$

X

$X$

Σ = X^{⊤} X / (n - 1)

$\Sigma=X^\top X/(n-1)$ . Cela signifie que l'erreur de reconstruction est minimisée en prenant comme colonnes de quelques vecteurs orthonormés maximisant la variance totale de la projection.

W

$W$

k

$k$

Il est bien connu que ce sont les premiers vecteurs propres de la matrice de covariance. En effet, si , alors . En écrivant qui a aussi des colonnes orthonormées, on obtient avec un maximum atteint lorsque . Le théorème suit alors immédiatement. $k$ $X=USV^\top$ $\Sigma=VS^2V^\top/(n-1)=V\Lambda V^\top$ $R=V^\top W$

t r (W^{⊤} Σ W) = t r (R^{⊤} Λ R) = \sum_{i} λ_{i} \sum_{j} R_{i j}^{2} \leq \sum_{i = 1}^{k} λ_{k},

$\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,$

W = V_{k}

$W=V_k$

Voir les trois fils associés suivants:

Tentative antérieure de démonstration de la norme Frobenius

Cette preuve que j'ai trouvée quelque part en ligne mais elle est fausse (contient un écart), comme expliqué par @cardinal dans les commentaires.

La norme de Frobenius est invariante sous les transformations unitaires, car elles ne modifient pas les valeurs singulières. On obtient donc: où . Continue:Ceci est minimisé lorsque tous les éléments hors diagonale de sont nuls et que tous les termes diagonaux annulent les plus grandes valeurs singulières [écart ici: ce n'est pas évident] , c'est-à-dire et donc .

‖ X - A ‖_{F} = ‖ U S V^{⊤} - A ‖ = ‖ S - U^{⊤} A V ‖ = ‖ S - B ‖,

$\|X-A\|_F=\|USV^\top - A\| = \|S - U^\top A V\| = \|S-B\|,$

B = U^{⊤} A V

$B=U^\top A V$

‖ X - A ‖_{F} = \sum_{i j} (S_{i j} - B_{i j})^{2} = \sum_{i} (s_{i} - B_{i i})^{2} + \sum_{i \neq j} B_{i j}^{2} .

$\|X-A\|_F = \sum_{ij}(S_{ij}-B_{ij})^2 = \sum_i (s_i-B_{ii})^2 + \sum_{i\ne j}B_{ij}^2.$

B

$B$

k

$k$

k

$k$

s_{i}

$s_i$

B_{o p t i m a l} = S_{k}

$B_\mathrm{optimal}=S_k$

A_{o p t i m a l} = U_{k} S_{k} V_{k}^{⊤}

$A_\mathrm{optimal} = U_k S_k V_k^\top$

amibe dit réintégrer Monica
la source

La preuve dans le cas de la norme de Frobeniius n'est pas correcte (ou du moins complète) car l'argument ici n'exclut pas la possibilité qu'une matrice de même rang puisse annuler certains des autres termes diagonaux tout en ayant des "petits" off- diagonales. Pour voir l'écart plus clairement, notez que le fait de maintenir les diagonales constantes et de "mettre à zéro" les hors diagonales peut souvent augmenter le rang de la matrice en question!

cardinal

Notez également que la SVD était connue de Beltrami (au moins dans un cas assez général, bien que spécial) et de Jordan dès 1874.

Cardinal

B

$B$

S

$S$

k

$k$

\sum_{i} (s_{i} - B_{i i})^{2}

$\sum_{i}(s_i-B_{ii})^2$

\sum_{i \neq j} B_{i j}^{2}

$\sum_{i\ne j}B_{ij}^2$

amibe dit Réintégrer Monica

Je fais comme GW Stewart (1993), Au début de l' histoire de la décomposition de valeurs singulières, SIAM Review , vol. 35, non. 4, 551-566 et, compte tenu de votre intérêt démontré antérieur pour les questions historiques, je pense que vous aussi. Malheureusement, je pense que Stewart est involontairement trop dédaigneux de l'élégance de la preuve de Schmidt de 1907. Caché dedans, il y a une interprétation de régression que Stewart néglige et qui est vraiment assez jolie. Il existe une autre preuve qui suit l'approche de diagonalisation initiale que vous adoptez, mais qui nécessite un travail supplémentaire pour combler l'écart. (suite)

Cardinal

@cardinal: Oui, vous avez raison, maintenant je vois aussi l'écart. Merci beaucoup pour l'article de Stewart, c'était une lecture très intéressante. Je vois que Stewart présente les preuves de Schmidt et Weyl, mais les deux semblent plus compliquées que ce que je voudrais copier ici (et jusqu'à présent, je n'ai pas eu le temps de les étudier attentivement). Je suis surpris: je m'attendais à ce que ce soit un résultat très simple, mais il semble que ce soit moins trivial que je ne le pensais. En particulier, je ne m'attendais pas à ce que le cas de Frobenius soit tellement plus compliqué que celui de l'opérateur normal. Je vais modifier le message maintenant. Bonne année!

amibe dit Réintégrer Monica le

Quelle norme d'erreur de reconstruction est minimisée par la matrice d'approximation de bas rang obtenue avec l'ACP?

Réponses:

Réponse en un seul mot: les deux.

Preuve pour l'opérateur -norm222

Preuve de la norme Frobenius

Tentative antérieure de démonstration de la norme Frobenius

Preuve pour l'opérateur -norm $2$