BLISS: Global Blind Identification of Linear Systems with Sparse Inputs

1. Il Problema: Identificazione Cieca di Sistemi Lineari

Il lavoro affronta il problema dell'identificazione cieca di sistemi lineari tempo-invarianti (LTI) in un contesto completamente osservato.
Data la dinamica del sistema vero e proprio:
$$x(k+1) = A^\natural x(k) + B^\natural u(k)$$
dove $x(k)$ sono gli stati e $u(k)$ sono gli input, l'obiettivo è stimare i parametri del sistema $(A^\natural, B^\natural)$ e la sequenza di input sconosciuta $(u(k))$, partendo solo dalle osservazioni degli stati $(x(0), \dots, x(T))$.

La sfida principale risiede nel fatto che gli input $u(k)$ sono sconosciuti ma si assume che siano sparsi (cioè, la maggior parte dei valori è zero o molto piccola). Questo rende il problema una fattorizzazione di matrice strutturata non convessa, dove sia la matrice del sistema che quella degli input devono essere recuperate simultaneamente. A differenza dell'identificazione classica (dove gli input sono noti) o del dictionary learning completo (dove la matrice di trasformazione è nota), qui entrambi i fattori sono incogniti.

2. Metodologia e Formulazione Matematica

Gli autori propongono un approccio basato sulla massimizzazione del volume (o minimizzazione del volume della matrice inversa), ispirato ai recenti risultati nel dictionary learning completo.

• Formulazione come Ottimizzazione: Il problema è formulato come un problema di minimizzazione vincolata non convessa:
  $$\min_{A, B, U} \text{vol}(B) \quad \text{s.t.} \quad X^+ = A X^\top + B U^\top, \quad \max_i \|U_i\|_1 \leq T\mu$$
  Dove $X^+$ e $X$ sono le matrici degli stati futuri e passati, e $U$ è la matrice degli input. La funzione obiettivo $\text{vol}(B) = \sqrt{\det(B^\top B)}$ agisce come regolarizzatore per favorire soluzioni uniche, sfruttando la connessione con la stima di massima verosimiglianza (MLE) assumendo che gli input seguano una distribuzione di Laplace.

• Condizione di Identificabilità Globale: Il contributo teorico centrale è l'introduzione della condizione di "Persistente Scattering" (Persistently Scattering).

  • Gli autori definiscono un zonotopo fondamentale $Z$ generizzato dalle colonne normalizzate degli stati e degli input.
  • La condizione richiede che esista una matrice diagonale non singolare $D$ tale che un'ellisse $DB_2$ sia contenuta in $Z$ e intersechi il bordo di $Z$ solo in punti specifici corrispondenti agli assi unitari degli input.
  • Questa condizione è una generalizzazione della "Sufficient Scattering" nota nel dictionary learning, adattata per gestire l'ambiguità introdotta dalla matrice $A$ sconosciuta.

• Teorema Principale: Sotto la condizione di "Persistente Scattering", ogni soluzione globale ottimale del problema di ottimizzazione recupera esattamente $A^\natural$ e recupera la coppia $(B^\natural, U^\natural)$ a meno di equivalenze di scala e permutazione (cioè, fino a una trasformazione diagonale e una permutazione delle colonne).

3. Algoritmo: BLISS

Per risolvere il problema di ottimizzazione non convesso, gli autori sviluppano BLISS (Blind Identification of Sparse Signals), una variante generalizzata del Metodo dei Moltiplicatori di Direzione Alternata (ADMM).

• Struttura: L'algoritmo utilizza un approccio primal-dual con un bilanciamento dinamico dei residui.
• Aggiornamenti Chiusi: Sfruttando la struttura del problema, gli aggiornamenti per $U$ e $\Phi$ (una variabile ausiliaria legata alla trasformazione di $B$) possono essere calcolati in forma chiusa:
  • L'aggiornamento di $U$ coinvolge una proiezione su una sfera $\ell_1$ scalata.
  • L'aggiornamento di $\Phi$ coinvolge un operatore prossimale per la funzione $-\log|\Phi|$, calcolabile efficientemente tramite la SVD (Singular Value Decomposition).
• Stabilità: Viene introdotto un schedule adattivo per il parametro di penalità $\rho(k)$ basato sul bilanciamento dei residui primali e duali, garantendo la convergenza e la stabilità numerica.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su sistemi con dimensione dello stato $n=100$ e dimensione dell'input $m=25$, variando la lunghezza della traiettoria $T$ e il livello di sparsità degli input.

• Transizione di Fase: I risultati mostrano una chiara transizione di fase tra il recupero perfetto e il fallimento. Il successo del recupero è strettamente correlato alla sparsità degli input e alla lunghezza della traiettoria osservata.
• Confronto:
  • Il metodo BLISS (identificazione cieca) performa significativamente meglio quando gli input sono molto sparsi e la traiettoria è lunga.
  • Confrontando con il caso in cui $A^\natural$ è noto (che riduce il problema al dictionary learning standard), si osserva che l'identificazione cieca richiede più dati o maggiore sparsità per avere successo, ma è comunque in grado di recuperare il sistema globale.
  • Gli input distribuiti secondo una Laplaceiana mostrano prestazioni leggermente migliori rispetto a quelli Gaussiani in termini di tolleranza alla densità, coerentemente con l'assunzione MLE.
• Convergenza: L'algoritmo converge rapidamente quando il parametro iniziale $\rho(0)$ è scelto in modo intelligente (basato sulla norma spettrale della matrice pseudoinversa), superando le inizializzazioni casuali.

5. Contributi Chiave e Significato

I principali contributi del lavoro sono:

1. Unificazione Teorica: Colma il divario tra la teoria dell'identificazione dei sistemi e il dictionary learning, mostrando che l'identificazione cieca con input sparsi è una generalizzazione del dictionary learning completo.
2. Garanzie di Identificabilità Globale: Fornisce le prime garanzie di identificabilità globale per sistemi lineari generali e non strutturati con input sparsi sconosciuti, basandosi sulla nuova condizione geometrica di "Persistente Scattering".
3. Algoritmo Scalabile: Propone BLISS, un algoritmo ADMM efficiente con aggiornamenti in forma chiusa, capace di recuperare il sistema vero da una singola traiettoria.
4. Validazione Empirica: Dimostra sperimentalmente che il metodo funziona in pratica, identificando chiaramente le regioni di successo e fallimento in funzione della sparsità e della quantità di dati.

Significato: Questo lavoro è fondamentale per applicazioni in cui gli input non sono misurabili ma sono intrinsecamente sparsi, come nei processi di diffusione, nelle reti neurali biologiche (sparsità di attivazione), nel rilevamento di guasti e nel pruning delle reti neurali. Offre un framework teorico solido e uno strumento pratico per risolvere problemi di identificazione che erano precedentemente considerati mal posti o privi di garanzie globali.