Eigengap Sparsity for Covariance Parsimony

Sintesi Tecnica: Eigengap Sparsity per la Parsimonia della Covarianza

Enunciato del Problema
La stima della covarianza è una sfida fondamentale in statistica, particolarmente in contesti ad alta dimensionalità dove il numero di campioni $n$ è insufficiente per stimare accuratamente i $p(p+1)/2$ parametri di una matrice di covarianza $p$-dimensionale. La matrice di covarianza campionaria (SCM), pur essendo la massima verosimiglianza (MLE), soffre di significativi errori di campionamento, in particolare del fenomeno di "dispersione degli autovalori" descritto dalla legge di Marčenko–Pastur, dove gli autovalori campionari si disperdono ampiamente attorno ai loro valori reali.

Per affrontare l'over-parametrizzazione, sono preferiti modelli parsimoniosi. Tuttavia, la selezione tradizionale del modello per le matrici di covarianza comporta scelte discrete (ad esempio, la selezione di specifici pattern di sparsità o vincoli di rango), che portano a problemi combinatori computazionalmente intrattabili. Nello specifico, gli autori si concentrano sulla parsimonia della covarianza indotta dalle molteplicità degli autovalori, dove il raggruppamento di autovalori uguali riduce la dimensionalità dello spazio dei parametri tramite il quoziente della invarianza rotazionale all'interno degli spazi eigenspaiziali. Sebbene questo approccio (Analisi del Sottospazio Principale) offra un quadro teorico, l'ottimizzazione esatta richiede la risoluzione di $2^{p-1}$ distinti problemi di ottimizzazione non penalizzati, rendendolo computazionalmente proibitivo anche per dimensioni moderate.

Metodologia
Il documento propone una rilassazione continua del problema discreto della parsimonia, denominata "eigengap sparsity" (sparsità del gap autovalore), per rendere l'ottimizzazione trattabile.

1. Stratificazione e Derivazione della Penalità:
   Lo spazio delle matrici simmetriche definite positive, $\text{Sym}_+(p)$, è stratificato in sottovarietà basate sulle molteplicità degli autovalori. Viene derivata la dimensione di una sottovarietà corrispondente a un particolare pattern di molteplicità $\gamma$. Gli autori dimostrano un teorema chiave (Teorema 1) affermando che questa dimensione può essere espressa come una norma $\ell_0$ dei gap spettrali:
   $$\dim(\text{Sym}_+(\gamma)) = 1 + \|\delta(\lambda_s, \lambda_{s+1})\|_0 + \|\delta(\lambda_s, \lambda_t)\|_0$$
   dove $\delta(a,b)=0$ se e solo se $a=b$. Questa formulazione rivela che la parsimonia è ottenuta non solo uguagliando gli autovalori adiacenti, ma anche uguagliando quelli non adiacenti, "attraggendo" efficacemente tutti gli autovalori verso l'un l'altro.

2. Rilassazione $\ell_1$:
   Per evitare la complessità combinatoria della norma $\ell_0$, gli autori sostituiscono questa con una norma $\ell_1$, creando una rilassazione convessa. Il problema di ottimizzazione risultante minimizza una verosimiglianza penalizzata:
   $$\min_{\lambda \in K_+(p)} \left( -2 \ln L(V \text{diag}(\lambda) V^\top) + \alpha \sum_{s=1}^{p-1} \left( \delta(\lambda_s, \lambda_{s+1}) + \sum_{t=s+1}^p \delta(\lambda_s, \lambda_t) \right) \right)$$
   dove $K_+(p)$ è il cono monotono degli autovalori ordinati.

3. Algoritmo di Ottimizzazione:
   Per il caso gaussiano, gli autori propongono un algoritmo di Gradiente Proiettato sul cono monotono.

   • Step di Gradiente: Aggiorna gli autovalori per massimizzare la verosimiglianza riducendo al contempo la penalità del gap autovalore.
   • Step di Proiezione: Proietta gli autovalori aggiornati nuovamente sul cono monotono $K_+(p)$. Questa proiezione equivale alla regressione isotonica, risolta efficientemente tramite l'algoritmo Pools Adjacent Violators (PAVA).
   • Meccanismo: L'algoritmo esegue iterativamente uno step di gradiente e poi "equalizza" gli autovalori che violano i vincoli di ordinamento. Gli autori notano che, mentre gli autovalori vicini sono spesso una maledizione numerica nella letteratura sul shrinkage, in questo framework sono una "benedizione" poiché lo step di proiezione li equalizza naturalmente, inducendo parsimonia.
   • Funzione Eigengap: Gli autori utilizzano una funzione di gap relativo $\delta(a, b) = (a-b)/a$ (per $a \ge b$), sostenendo che fornisca risultati migliori rispetto alla differenza assoluta.

Contributi Chiave

• Riformulazione Teorica: Il documento stabilisce un nuovo legame tra la parsimonia della covarianza e i gap degli autovalori, dimostrando che la dimensione intrinseca di una varietà di covarianza può essere scritta come una norma $\ell_0$ dei gap tra tutte le coppie di autovalori.
• Strategia di Rilassazione: Introduce la "eigengap sparsity" come una rilassazione $\ell_1$ di questa penalità di dimensione, trasformando un problema di selezione del modello discreto in un problema di ottimizzazione continua.
• Legame Algoritmico: Il metodo proposto traccia una connessione diretta tra la parsimonia della covarianza e i metodi di shrinkage. Dimostra che la regressione isotonica (storicamente usata come trucco di post-elaborazione per gestire l'instabilità numerica) emerge naturalmente come lo step di proiezione in un framework di verosimiglianza penalizzata, raggruppando automaticamente gli autovalori per ridurre la complessità del modello.
• Efficienza Computazionale: Il metodo evita la complessità esponenziale dell'esatta Analisi del Sottospazio Principale (PSA) risolvendo un singolo problema di ottimizzazione continua.

Risultati Sperimentali
Gli autori hanno valutato il metodo (ESCP) rispetto alla Matrice di Covarianza Campionaria (SCM), allo stimatore di shrinkage di Ledoit-Wolf (LW) e alla esatta Analisi del Sottospazio Principale (PSA) su dataset gaussiani sintetici con dimensioni ($p$) e dimensioni campionarie ($n$) variabili.

• Accuratezza vs. Parsimonia: ESCP ha ottenuto punteggi di verosimiglianza penalizzata ($L_p$) significativamente più bassi rispetto a SCM e LW in contesti ad alta dimensionalità, indicando un migliore compromesso tra adattamento e complessità.
• Errore di Stima: Sorprendentemente, ESCP ha superato lo stimatore LW in termini di errore di stima della norma di Frobenius ($L_F$), nonostante non sia stato esplicitamente progettato per minimizzare questa metrica.
• Recupero degli Autovalori: In esperimenti con strutture di covarianza isotrope e a blocchi diagonali, ESCP ha recuperato con successo le vere molteplicità degli autovalori (ad esempio, recuperando perfettamente $I_{100}$ e la struttura a blocchi di $\Xi_{80,80,40}$), mentre SCM mostrava un'alta dispersione e LW mostrava uno shrinkage parziale senza un raggruppamento completo.
• Velocità: ESCP è stato ordini di grandezza più veloce della PSA esatta, che diventava computazionalmente proibitiva per $p \gtrsim 20$.

Significatività e Rivendicazioni
Il documento afferma che la eigengap sparsity offre una prospettiva promettente sulla stima della covarianza, riformulandola attraverso la lente della parsimonia indotta dall'equalizzazione degli autovalori. Gli autori evidenziano tre ponti verso aree di ricerca attive:

1. Ottimizzazione Sparsa: Il metodo induce la sparsità tramite regressione isotonica piuttosto che attraverso il classico thresholding (come il LASSO).
2. Teoria dello Shrinkage: Affronta il fenomeno della dispersione degli autovalori raggruppandoli, estendendosi oltre i modelli a basso rango (come il PPCA) che raggruppano solo i piccoli autovalori come rumore.
3. Statistica Geometrica: Il framework integra sia gli autovalori che la "flag" degli eigenspaizi, offrendo una visione geometrica più completa rispetto ai metodi focalizzati esclusivamente sugli autovalori.

Gli autori concludono che, sebbene il metodo mostri promesse negli esperimenti sintetici e nella velocità, rimane in una fase iniziale di ricerca, con la necessità di futuri lavori per valutare le prestazioni su profili di autovalori diversificati, distribuzioni non gaussiane e per esplorare garanzie teoriche ed estensioni della metrica di Riemann.