Metodo di Nyström — ingegnerismo.it

Il metodo di Nyström è una tecnica di approssimazione a rango basso usata per matrici kernel grandi. Invece di calcolare e memorizzare tutta la matrice di Gram

G_{ij}=K(x_i,x_j), \qquad G\in\mathbb R^{n\times n},

si scelgono $m$ punti rappresentativi, detti landmark, con $m\ll n$ , e si ricostruisce un’approssimazione della matrice completa.

La formula centrale è

\widehat G=CW^\dagger C^T,

dove $C$ contiene i kernel tra tutti i punti e i landmark, mentre $W$ contiene i kernel tra landmark.

Schema matriciale

Oggetto	Formula	Ruolo
Dataset	$\displaystyle x_1,\ldots,x_n$	Punti su cui sarebbe costruita la matrice kernel completa.
Landmark	$\displaystyle s_1,\ldots,s_m$	Sottoinsieme rappresentativo, con $\displaystyle m\ll n$ .
Blocco colonne	$\displaystyle C_{i\ell}=K(x_i,s_\ell)$	Similarità tra tutti i punti e i landmark.
Blocco interno	$\displaystyle W_{\ell r}=K(s_\ell,s_r)$	Matrice kernel ristretta ai landmark.
Approssimazione	$\displaystyle \widehat G=CW^\dagger C^T$	Ricostruzione a rango al più $\displaystyle m$ .

Se $W$ è invertibile, il simbolo $W^\dagger$ può essere sostituito da $W^{-1}$ . La pseudoinversa è però più robusta quando i landmark sono ridondanti o il blocco $W$ è quasi singolare.

Costruzione per blocchi

Dopo aver riordinato i punti in modo che i primi $m$ siano landmark, una matrice kernel ideale può essere letta per blocchi:

G= \begin{pmatrix} W & B^T\\ B & D \end{pmatrix}.

Il metodo di Nyström conserva il blocco $W$ e le colonne che collegano tutti i punti ai landmark:

C= \begin{pmatrix} W\\ B \end{pmatrix}.

Poi approssima il blocco non osservato $D$ tramite

D\approx BW^\dagger B^T.

La matrice completa diventa quindi

\widehat G= C W^\dagger C^T.

Feature esplicite indotte

Quando $W$ è semidefinita positiva, il metodo può essere interpretato anche come costruzione di feature esplicite. Se

W=U\Lambda U^T

è una decomposizione spettrale sui soli autovalori positivi, si definisce

Z=C\,U\Lambda^{-1/2}.

Allora

ZZ^T = C\,U\Lambda^{-1}U^T C^T = CW^\dagger C^T = \widehat G.

In questa forma, Nyström trasforma un problema kernel in un modello lineare sulle righe di $Z$ , in modo simile nello scopo alle Random Fourier features, ma con una costruzione basata sui punti landmark anziché su frequenze casuali.

Confronto con Random Fourier features

Metodo	Che cosa approssima	Formula	Dipendenza dal kernel
Kernel trick esatto	Matrice kernel completa	$\displaystyle G_{ij}=K(x_i,x_j)$	Richiede tutte le coppie di punti.
Metodo di Nyström	Matrice di Gram	$\displaystyle \widehat G=CW^\dagger C^T$	Usa landmark scelti tra i dati o punti rappresentativi.
Random Fourier features	Funzione kernel stazionaria	$\displaystyle K(x,y)\approx z(x)^Tz(y)$	Usa la misura spettrale del kernel.
Feature lineari	Prodotto scalare osservato	$\displaystyle K(x,y)=x^Ty$	Non introduce approssimazione kernel non lineare.

La differenza è sostanziale: Nyström approssima una matrice finita già legata al dataset, mentre le Random Fourier features approssimano la funzione kernel e poi generano feature per qualunque punto.

Scelta dei landmark

La qualità dell’approssimazione dipende molto da come vengono scelti i landmark.

Criterio	Idea	Rischio
Campionamento uniforme	Scegliere $\displaystyle m$ punti a caso	Può ignorare regioni rare ma importanti.
K-means o centroidi	Usare punti rappresentativi dei cluster	Aggiunge costo preliminare e dipende dalla metrica.
Leverage score	Favorire punti con alta influenza spettrale	Richiede stime più sofisticate.
Campionamento stratificato	Coprire classi o regioni note	Serve informazione di struttura sul dataset.

In pratica, la scelta uniforme può bastare come baseline, ma dataset sbilanciati o con varietà geometriche sottili richiedono landmark più curati.

Schema operativo

Passo	Azione	Controllo
1	Scegliere il kernel $\displaystyle K$	Deve generare una Gram semidefinita positiva.
2	Selezionare $\displaystyle m$ landmark	Devono coprire la geometria dei dati.
3	Calcolare $\displaystyle C_{i\ell}=K(x_i,s_\ell)$	Costo dell’ordine di $\displaystyle nm$ .
4	Calcolare $\displaystyle W_{\ell r}=K(s_\ell,s_r)$	Costo dell’ordine di $\displaystyle m^2$ .
5	Costruire $\displaystyle \widehat G=CW^\dagger C^T$ oppure feature $\displaystyle Z$	Si ottiene una rappresentazione a rango basso.
6	Addestrare o diagonalizzare usando l’approssimazione	Verificare errore, stabilità e sensibilità ai landmark.

Il vantaggio computazionale appare quando $m$ è molto più piccolo di $n$ : il costo di memoria passa da una matrice $n\times n$ a blocchi o feature di dimensione circa $n\times m$ .

Uso in Kernel PCA

Nella Kernel PCA, diagonalizzare la matrice di Gram centrata può diventare proibitivo per dataset grandi. Nyström riduce il problema sostituendo $G$ con una matrice a rango basso:

\widetilde G = HGH \approx H C W^\dagger C^T H.

Se si lavora con le feature $Z$ , la centratura può essere eseguita direttamente nello spazio approssimato:

Z_c=HZ, \qquad \widehat G_c=Z_cZ_c^T.

Questo consente una decomposizione spettrale più economica, pur mantenendo una geometria kernel approssimata.

Errori comuni

Confondere Nyström con Random Fourier features: Nyström campiona landmark nel dominio dei dati; le Random Fourier features campionano frequenze nello spettro del kernel.
Scegliere landmark senza controllare la copertura: punti poco rappresentativi producono una Gram approssimata povera anche se $m$ è grande.
Invertire $W$ senza regolarizzazione: se $W$ è mal condizionata, usare $W^{-1}$ può amplificare rumore numerico.
Dimenticare la centratura in Kernel PCA: l’approssimazione non elimina la necessità di centrare coerentemente la matrice o le feature.
Trattare $\widehat G$ come esatta: downstream, autovalori e distanze dipendono dall’errore di approssimazione.

Vedi anche: matrice di Gram, kernel trick, Random Fourier features, leverage score, Kernel PCA, mappa di feature, funzione positiva-definita.