SVD et approximation de rang k

une image est une somme de couches de rang 1, rangées de la plus importante à la moins importante

1 · DÉCOMPOSITION ET THÉORÈME D'ECKART-YOUNG

$$A=U\Sigma V^\top=\sum_{i=1}^{r}\sigma_i\,u_iv_i^\top,\qquad \sigma_1\ge\sigma_2\ge\dots\ge\sigma_r>0,\qquad A_k=\sum_{i=1}^{k}\sigma_i\,u_iv_i^\top$$

$$\min_{\operatorname{rang}B\le k}\|A-B\|_F=\|A-A_k\|_F=\Big(\sum_{i>k}\sigma_i^2\Big)^{1/2}, \qquad \min_{\operatorname{rang}B\le k}\|A-B\|_2=\sigma_{k+1}$$

2 · À TOI : CHOISIS LE RANG k

image $A$ (96 × 96)

reconstruction $A_k$

couche $\sigma_k u_k v_k^\top$

spectre : valeurs singulières $\sigma_i$ (échelle log) — glisse pour choisir k

critère : erreur relative $\|A-A_k\|_F/\|A\|_F$ en fonction de k

rang $k$ bruit

Avec du bruit, la courbe orange mesure l'écart à l'image propre : elle passe par un minimum. Au-delà de ce k, on ajoute surtout du bruit. Le spectre montre alors un « plancher » de valeurs singulières dues au bruit.

3 · RAPPELS

Les $\sigma_i^2$ sont les valeurs propres de $A^\top A$ ; les $v_i$ ses vecteurs propres, les $u_i=Av_i/\sigma_i$. Sur des données centrées, c'est exactement l'ACP : les $v_i$ sont les axes principaux.
Eckart-Young (1936) : aucune matrice de rang $k$ n'approche mieux $A$, en norme de Frobenius comme en norme spectrale. L'erreur se lit sur le spectre, sans reconstruire.
Coût de stockage de $A_k$ : $k(m+n+1)$ nombres au lieu de $mn$. Ici $k(96+96+1)$ contre $9\,216$.
Une image formée de motifs alignés sur les axes (damier, bandes) a un rang très faible ; des bords obliques ou des courbes demandent beaucoup de couches.
Débruitage : avec $A=L+E$, $L$ de faible rang, tronquer la SVD garde le signal et jette la plus grande partie du bruit, à condition que les $\sigma_i$ du signal dépassent le niveau du bruit (≈ $\sigma_E(\sqrt m+\sqrt n)$).