Approximation de rang faible

Garder la partie d'une matrice qui compte

La SVD écrit une matrice comme une somme de couches de rang un, $A=\sum_i\sigma_i\mathbf u_i\mathbf v_i^{T}$, de la plus grande à la plus petite. Ne garder que les $k$ premières couches donne $A_k=U_k\Sigma_kV_k^{T}$, une matrice de rang $k$. Le théorème d'Eckart-Young dit que cette troncature est la meilleure approximation de rang $k$ possible, que l'erreur soit mesurée par la norme de Frobenius ou par la norme spectrale. Aucun choix astucieux de $k$ directions ne peut battre les $k$ premières directions singulières.

L'erreur est exactement formée des valeurs singulières écartées ; la part de la taille au carré conservée est donc $\sum_{i\le k}\sigma_i^2\big/\sum_i\sigma_i^2$, souvent appelée variance expliquée quand $A$ est une matrice de données centrées. Une approximation de rang $k$ d'une matrice $m\times n$ ne demande que $k(m+n+1)$ nombres au lieu de $mn$, ce qui fait du rang faible aussi une compression. En finance, les couches de petit $\sigma_i$ sont surtout du bruit d'échantillonnage ; les tronquer est un débruitage, et l'on choisit $k$ par un seuil sur la part conservée ou par un saut dans les valeurs singulières.

• Eckart-Young : tronquer la SVD à $k$ termes est la meilleure approximation de rang $k$ pour les deux normes.
• Erreur : Frobenius $\sqrt{\sum_{i>k}\sigma_i^2}$, spectrale $\sigma_{k+1}$.
• Stockage : $k(m+n+1)$ nombres au lieu de $mn$.

Lab : ce qui est noté

• L'erreur de Frobenius15 pts
• La part conservée15 pts
• Une approximation de rang un15 pts
• Stockage d'une matrice de rang faible10 pts
• Le théorème d'Eckart-Young15 pts
• Compresser une matrice15 pts
• Pourquoi la troncature débruite15 pts