Teorema di Eckart-Young — ingegnerismo.it

Il teorema di Eckart-Young afferma che la migliore approssimazione a basso rango di una matrice si ottiene troncando la decomposizione ai valori singolari più grandi. È uno dei risultati fondamentali dietro compressione dei dati, riduzione dimensionale, denoising, PCA e modelli a rango ridotto.

Enunciato

Sia $A\in\mathbb{R}^{m\times n}$ una matrice di rango $r$ con decomposizione ai valori singolari

A=\sum_{i=1}^{r}\sigma_i u_i v_i^T, \qquad \sigma_1\ge\cdots\ge\sigma_r>0,

dove $\sigma_i$ sono i valori singolari e $u_i$ , $v_i$ sono vettori singolari sinistri e destri.

Per $k<r$ , si definisce la SVD troncata

A_k=\sum_{i=1}^{k}\sigma_i u_i v_i^T.

Il teorema di Eckart-Young dice che $A_k$ è una migliore approssimazione di $A$ tra tutte le matrici di rango al più $k$ .

Norma spettrale

In norma spettrale vale

\|A-A_k\|_2=\sigma_{k+1}.

In altre parole, nessuna matrice di rango al più $k$ può approssimare $A$ con errore spettrale minore del primo valore singolare scartato.

Formalmente:

\min_{\operatorname{rank}(B)\le k} \|A-B\|_2 = \|A-A_k\|_2 = \sigma_{k+1}.

Norma di Frobenius

In norma di Frobenius vale

\|A-A_k\|_F= \sqrt{\sum_{i=k+1}^{r}\sigma_i^2}.

Quindi

\min_{\operatorname{rank}(B)\le k} \|A-B\|_F = \sqrt{\sum_{i=k+1}^{r}\sigma_i^2}.

La norma di Frobenius misura l’errore complessivo elemento per elemento, mentre la norma spettrale misura il massimo effetto dell’errore su un vettore unitario.

Interpretazione geometrica

La SVD scompone l’azione di $A$ in direzioni ortogonali ordinate per importanza. I valori singolari misurano quanto la matrice amplifica lungo ciascuna direzione. Troncare la SVD significa conservare le direzioni dominanti e scartare quelle meno energetiche.

Se i valori singolari decadono rapidamente, pochi termini bastano a rappresentare gran parte della struttura di $A$ . Se invece decadono lentamente, una bassa approssimazione di rango può perdere molta informazione.

Collegamento con PCA

Nell’analisi delle componenti principali, si cerca una rappresentazione dei dati in poche direzioni che conservi la massima varianza. La SVD della matrice dei dati centrati fornisce proprio queste direzioni. Il teorema di Eckart-Young giustifica matematicamente il fatto che una rappresentazione con le prime $k$ componenti principali sia ottima, in senso quadratico, tra le rappresentazioni lineari di rango $k$ .

Il collegamento passa anche dalla matrice di covarianza, dai suoi autovalori e autovettori.

Applicazioni

Il teorema è usato in:

compressione di immagini e matrici di dati;
riduzione del rumore;
modelli latenti;
sistemi di raccomandazione;
approssimazioni numeriche di operatori;
regressione e minimi quadrati a rango ridotto.

In una matrice immagine, per esempio, conservare solo i primi valori singolari può mantenere la struttura visiva principale riducendo drasticamente il numero di parametri.

Errori comuni

Un errore frequente è pensare che la SVD troncata sia sempre una buona approssimazione solo perché è ottima. Il teorema dice che è la migliore tra le matrici di rango $k$ , ma se $k$ è troppo piccolo o i valori singolari non decadono, l’errore può restare grande.

Un secondo errore è ignorare la norma rispetto alla quale si parla di ottimalità. Le formule classiche valgono per norma spettrale e norma di Frobenius; altre misure di errore possono portare a problemi diversi.

Infine, nella PCA bisogna centrare correttamente i dati. Applicare una SVD troncata a dati non centrati può mescolare media e variazione, alterando l’interpretazione delle componenti. Per esercizi, vedi la pagina sulla PCA e riduzione della dimensionalità.