Matrice di Gram — ingegnerismo.it

La matrice di Gram raccoglie tutti i prodotti scalari tra una famiglia finita di vettori. Se $v_1,\ldots,v_n$ appartengono a uno spazio con prodotto scalare, la matrice di Gram è

G_{ij}=\langle v_i,v_j\rangle.

Nel caso reale euclideo, se i vettori sono le colonne di una matrice $A$ , allora

G=A^T A.

Nel caso complesso si usa la trasposta coniugata:

G=A^*A.

Forme principali

Contesto	Formula	Interpretazione
Vettori euclidei	$\displaystyle G_{ij}=v_i^T v_j$	Prodotti scalari tra vettori reali.
Spazio complesso	$\displaystyle G_{ij}=\langle v_i,v_j\rangle$	Matrice hermitiana dei prodotti scalari.
Kernel positivo-definito	$\displaystyle G_{ij}=K(x_i,x_j)$	Similarità implicite tra punti.
Dati centrati per righe	$\displaystyle G=X_cX_c^T$	Prodotti scalari tra osservazioni centrate.
Dati centrati per colonne	$\displaystyle S=\dfrac{1}{n-1}X_c^T X_c$	Covarianza campionaria come Gram normalizzata delle variabili.

La stessa idea compare quindi in algebra lineare, statistica multivariata e metodi kernel: cambia solo che cosa viene messo a prodotto scalare.

Positiva semidefinitezza

Ogni matrice di Gram è semidefinita positiva. Infatti, per coefficienti $c_1,\ldots,c_n$ ,

c^*Gc = \sum_{i=1}^n\sum_{j=1}^n \overline{c_i}c_j\langle v_i,v_j\rangle = \left\lVert\sum_{j=1}^n c_jv_j\right\rVert^2 \ge0.

Questa identità spiega perché le funzioni positive-definite sono definite chiedendo che ogni matrice costruita come $G_{ij}=K(x_i,x_j)$ sia semidefinita positiva.

Proprietà	Formula	Conseguenza
Simmetria reale	$\displaystyle G=G^T$	I prodotti scalari reali sono simmetrici.
Simmetria hermitiana	$\displaystyle G=G^*$	Nel caso complesso gli autovalori sono reali.
Semidefinitezza positiva	$\displaystyle c^*Gc\ge0$	Tutti gli autovalori sono non negativi.
Rango	$\displaystyle \operatorname{rank}(G)=\dim\operatorname{span}\{v_1,\ldots,v_n\}$	Misura quante direzioni indipendenti sono presenti.
Determinante di Gram	$\displaystyle \det G\ge0$	È il quadrato del volume generato dai vettori.

Se i vettori sono linearmente indipendenti, $G$ è definita positiva. Se sono dipendenti, $G$ è singolare e $\det G=0$ .

Matrice kernel

Nei metodi kernel si parte da punti $x_1,\ldots,x_n$ e da un kernel $K$ . La matrice

G_{ij}=K(x_i,x_j)

è ancora una matrice di Gram, perché per un kernel positivo-definito esiste una mappa di feature $\Phi$ tale che

K(x_i,x_j)=\langle \Phi(x_i),\Phi(x_j)\rangle_{\mathcal F}.

Questa è la base del kernel trick: si usa $G$ senza costruire esplicitamente lo spazio $\mathcal F$ . Quando $G$ è troppo grande, le Random Fourier features costruiscono una matrice di feature esplicite $Z$ tale che $ZZ^T$ approssimi la Gram kernel, mentre il metodo di Nyström approssima direttamente $G$ tramite landmark.

Oggetto	Formula	Uso
Mappa di feature	$\displaystyle \Phi(x_i)$	Rappresentazione implicita del punto.
Kernel	$\displaystyle K(x_i,x_j)$	Prodotto scalare nello spazio feature.
Matrice kernel	$\displaystyle G_{ij}=K(x_i,x_j)$	Dati trasformati riassunti in una matrice.
Gram approssimata	$\displaystyle \widehat G=ZZ^T$	Approssimazione esplicita tramite feature finite.
Nyström	$\displaystyle \widehat G=CW^\dagger C^T$	Approssimazione tramite landmark.
Gram centrata	$\displaystyle \widetilde G=HGH$	Versione centrata usata in Kernel PCA.

Centratura

Per applicazioni come la Kernel PCA, la matrice di Gram deve rappresentare dati centrati nello spazio feature. Si usa

H=I_n-\dfrac{1}{n}\mathbf 1\mathbf 1^T, \qquad \widetilde G=HGH.

La centratura equivale a sottrarre la media delle feature anche quando le feature non sono note esplicitamente.

Schema operativo

Passo	Azione	Controllo
1	Scegliere vettori $\displaystyle v_1,\ldots,v_n$ o punti $\displaystyle x_1,\ldots,x_n$	Serve una famiglia finita.
2	Calcolare prodotti scalari o kernel	Si ottiene $\displaystyle G_{ij}=\langle v_i,v_j\rangle$ oppure $\displaystyle G_{ij}=K(x_i,x_j)$ .
3	Verificare simmetria o hermitianità	Deve valere $\displaystyle G=G^T$ o $\displaystyle G=G^*$ .
4	Controllare semidefinitezza positiva	Gli autovalori devono essere $\displaystyle \lambda_i\ge0$ .
5	Usare rango, autovalori o determinante	Si deducono dipendenza lineare, volumi e geometria.

Errori comuni

Confondere matrice di Gram e matrice di covarianza: la covarianza è una Gram normalizzata di dati centrati in una convenzione precisa, ma non ogni Gram è una covarianza.
Dimenticare la convenzione righe/colonne: con vettori colonna si ottiene $A^T A$ , mentre con osservazioni per riga compare spesso $XX^T$ .
Pensare che ogni matrice semidefinita positiva sia automaticamente una Gram osservata: può esserlo astrattamente, ma l’interpretazione dipende dai vettori o dal kernel scelto.
Saltare la centratura: in PCA e Kernel PCA la matrice non centrata cambia il problema geometrico.
Confondere Gram-Schmidt e matrice di Gram: condividono il prodotto scalare come struttura di base, ma il primo è un algoritmo di ortogonalizzazione.

Vedi anche: mappa di feature, Random Fourier features, metodo di Nyström, funzione positiva-definita, kernel trick, Kernel PCA, procedimento di Gram-Schmidt, matrice di covarianza, forma quadratica.