Sintesi Tecnica: Completamento di Matrici Distribuzionali a Basso Rango

Definizione del Problema

Questo articolo affronta il problema del completamento di matrici distribuzionali, una generalizzazione del classico compito di completamento di matrici a basso rango. In questo contesto, la matrice target $\rho^* \in \mathcal{P}(\mathcal{X})^{m_1 \times m_2}$ consiste in voci che sono distribuzioni di probabilità su un dominio $\mathcal{X}$, piuttosto che valori scalari.

Il modello di osservazione è caratterizzato da due livelli di incompletezza:

1. Osservazione Parziale: Solo un sottoinsieme di voci della matrice è osservato, indicato da una maschera binaria $T(i,j)$.
2. Osservazione Indiretta: Anche per le voci osservate, la distribuzione sottostante $\rho^*(i,j)$ non è direttamente accessibile. Invece, si osserva un insieme finito di campioni i.i.d. \{X^{(ij)}_1, \dots, X^{(ij)}_{N_{ij}}\ estratti da $\rho^*(i,j)$, dove la dimensione del campione $N_{ij}$ può variare tra le diverse voci.

L'obiettivo è recuperare la matrice completa a valori distribuzionali $\rho^*$ (o la sua rappresentazione) partendo da queste osservazioni parziali e indirette. Questo problema sorge in applicazioni come la modellazione della variabilità del flusso di traffico tra località o l'analisi della distribuzione delle previsioni di guadagno tra diversi trimestri fiscali e istituzioni.

Metodologia

Kernel Mean Embeddings (KME)

Per gestire la natura a dimensione infinita delle distribuzioni di probabilità ed evitare i vincoli di varietà associati alle funzioni di densità, gli autori rappresentano ogni distribuzione $\rho^*(i,j)$ tramite il suo Kernel Mean Embedding (KME) in uno Spazio di Hilbert Riproduttivo (RKHS) $\mathcal{H}$:
$$\mu^*(i, j, \cdot) = \mathbb{E}_{X \sim \rho^*(i,j)} [K(X, \cdot)] \in \mathcal{H}$$
Il recupero di $\rho^*$ è equivalente al recupero della matrice KME $\mu^* \in \mathcal{H}^{m_1 \times m_2}$. La distanza tra le distribuzioni è misurata tramite la Maximum Mean Discrepancy (MMD).

Modellazione a Basso Rango tramite Svolgimento Funzionale

Gli autori propongono una struttura di rango Tucker per la matrice distribuzionale. Essi vedono $\mu^*$ come un tensore a tre vie nello spazio $\mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H}$. Poiché $\mathcal{H}$ è spesso a dimensione infinita, le definizioni standard di rango tensoriale non si applicano direttamente.

Per affrontare ciò, il documento introduce operatori di svolgimento funzionale ($U_1, U_2, U_3$) che mappano il tensore in prodotti di due spazi (ad es., $U_1: \mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H} \to \mathbb{R}^{m_1} \otimes (\mathbb{R}^{m_2} \otimes \mathcal{H})$). Questi operatori inducono operatori lineari il cui rango definisce il rango multilineare $(r_1, r_2, r_3)$.

• Implicazione Strutturale: Un basso rango multilineare implica che le componenti funzionali dei KME giacciono in un sottospazio a bassa dimensione, e le matrici di funzione di aspettativa associate (ad es., matrici di media) sono a basso rango.

Framework di Stima

Gli autori propongono un M-stimatore regolarizzato $\hat{\mu}$ definito dalla minimizzazione di una funzione di perdita più un termine di penalità della norma nucleare:
$$\hat{\mu} = \arg\min_{\mu} \left[ \frac{1}{m_1 m_2} \sum_{(i,j): T(i,j)=1} \left\| \mu(i, j, \cdot) - \hat{\mu}_{emp}(i, j, \cdot) \right\|_{\mathcal{H}}^2 + \lambda \Psi(\mu) \right]$$

• Termine di Perdita: Il quadrato della MMD tra il KME stimato e il KME empirico derivato dai campioni osservati.
• Regolarizzazione: $\Psi(\mu) = \sum_{j=1}^3 \beta_j \|U_j \mu\|_*$, dove $\|\cdot\|_*$ denota la norma nucleare dell'operatore lineare indotto. Ciò promuove il basso rango attraverso tutte e tre le modalità.

Soluzione Computazionale

Nonostante la natura a dimensione infinita di $\mathcal{H}$, il Teorema del Rappresentante garantisce che la soluzione $\hat{\mu}$ giaccia nello span a dimensione finita delle funzioni kernel osservate.

1. Il problema viene ri-parametrizzato in un problema di ottimizzazione tensoriale a dimensione finita su un tensore di coefficienti $B \in \mathbb{R}^{m_1 \times m_2 \times \tilde{N}}$.
2. Per gestire grandi dimensioni di campionamento, gli autori suggeriscono di approssimare la matrice di Gram utilizzando tecniche di approssimazione del kernel (ad es., metodo Nyström o Random Fourier Features).
3. L'ottimizzazione viene risolta utilizzando un metodo ADMM (Alternating Direction Method of Multipliers) accelerato.

Contributi Chiave

1. Nuova Formulazione del Problema: Il documento formalizza il completamento di matrici con voci a valori distribuzionali, affrontando la sfida di recuperare distribuzioni da dati campionari parziali e rumorosi.
2. Framework Teorico: Introduce una definizione di rango Tucker per tensori a valori distribuzionali tramite operatori di svolgimento funzionale, colmando il divario tra dati funzionali a dimensione infinita e analisi tensoriale a dimensione finita.
3. Innovazione Algoritmica: Lo stimatore proposto utilizza la regolarizzazione della norma nucleare su operatori lineari indotti. Fondamentalmente, gli autori dimostrano che la soluzione ammette una rappresentazione a dimensione finita, rendendo il problema computazionalmente trattabile tramite ottimizzazione convessa.
4. Garanzie Statistiche: Il documento stabilisce limiti di errore non asintotici per la MMD quadratica aggregata.
   • Il tasso di convergenza corrisponde a quello del classico completamento di matrici regolarizzato con norma nucleare per matrici scalari.
   • A differenza degli approcci esistenti basati sui vicini più prossimi (ad es., Feitelberg et al., 2024), la coerenza del metodo proposto non richiede che il numero di campioni per voce ($N_{ij}$) diverga. Invece, la coerenza è ottenuta man mano che le dimensioni della matrice ($m_1, m_2$) crescono, sfruttando la struttura globale a basso rango per la condivisione delle informazioni.

Risultati Sperimentali

Dati Sintetici

• Setup: Matrici simulate con distribuzioni di miscela gaussiana. I confronti sono stati effettuati contro un metodo di vicini più prossimi (NN) (Feitelberg et al., 2024) e un completamento di matrici classico (SOFTIMPUTE) applicato a medie e varianze campionarie.
• Risultati:
  • Il metodo proposto (LRKME) ha superato costantemente il metodo NN sia nelle voci osservate che in quelle non osservate, in particolare nella stima della varianza e delle statistiche di ordine superiore.
  • LRKME ha inoltre superato SOFTIMPUTE, dimostrando il vantaggio di utilizzare l'intera informazione distribuzionale anziché solo riassunti scalari.
  • In contesti 2D, il metodo NN è stato escluso a causa dell'intrattabilità computazionale delle distanze di Wasserstein multivariate, mentre LRKME è rimasto efficace.

Applicazione nel Mondo Reale

• Dataset: Dati sui viaggi dei taxi di NYC, modellando la distribuzione del numero giornaliero di viaggi tra 265 località di origine e destinazione.
• Sfida: Alto tasso di dati mancanti (>39%) e dimensioni dei campioni altamente variabili per ogni voce (da 1 a 3672).
• Risultati: LRKME ha ottenuto un errore relativo empirico significativamente più basso (0.0015) rispetto al metodo NN (0.0212) sul set di test. L'ispezione visiva di casi specifici ha mostrato che LRKME cattura meglio le distribuzioni a coda pesante e i pattern di concentrazione rispetto all'estimatore NN.

Significato e Rivendicazioni

Il documento sostiene di fornire il primo metodo per il completamento di matrici distribuzionali che:

1. Accoglie schemi di osservazione generali con dimensioni di campione variabili.
2. Si estende naturalmente a distribuzioni multidimensionali senza i colli di bottiglia computazionali dei metodi basati su Wasserstein.
3. Offre garanzie di coerenza globale che non dipendono dalla crescita asintotica dei campioni per voce, basandosi invece sulla struttura a basso rango della matrice.
4. Fornisce una soluzione computazionalmente efficiente tramite rappresentazione a dimensione finita e ottimizzazione convessa.

Gli autori posizionano il loro lavoro come un passo significativo rispetto agli approcci esistenti basati sui vicini più prossimi, offrendo un framework più robusto, teoricamente fondato e scalabile per l'imputazione di dati distribuzionali mancanti.