Riepilogo Tecnico: Flussi a Doppio Parentesi Discreti per la Decomposizione in Autovalori Invariante rispetto al Rumore Isotropo

1. Enunciato del Problema

Il documento affronta il problema della decomposizione in autovalori senza matrice completa (full-basis matrix-free) per un operatore simmetrico sotto osservazioni in streaming. Il modello di osservazione è dato da:
$$C_k = C_{\text{sig}} + \sigma_k^2 I + E_k$$
dove:

• $C_{\text{sig}} \in \mathbb{R}^{n \times n}$ è la covarianza del segnale con autovalori distinti.
• $\sigma_k^2 I$ rappresenta un fondo isotropo variabile nel tempo, potenzialmente illimitato (pavimento di rumore).
• $E_k$ è una perturbazione anisotropa.
• L'accesso è limitato ai prodotti matrice-vettore (MVP) $v \mapsto C_k v$, il che significa che la matrice completa $C_k$ non viene mai memorizzata o formata esplicitamente.

La Sfida Principale: In regimi ad alto fondo di rumore dove $\sigma_k^2 \gg \|C_{\text{sig}}\|_2$, gli algoritmi standard (ad esempio, iterazione del sottospazio, regola di Oja, discesa del gradiente euclidea con retrazione QR) soffrono di un grave degrado. La loro stabilità, le dimensioni del passo e i tassi di contrazione diventano accoppiati al pavimento di rumore $\sigma_k^2$. Ad esempio, il rapporto di contrazione nell'iterazione del sottospazio si avvicina all'unità quando $\sigma_k^2 \to \infty$, e la dimensione del passo effettiva in QR-Oja collassa a zero. Questo costringe il numero di iterazioni a scalare come $\Omega(\sigma_k^2 / \Delta)$, rendendoli impraticabili per ambienti ad alto rumore.

2. Metodologia

Gli autori propongono un Flusso a Doppio Parentesi Discreto che raggiunge un'invarianza algebrica rispetto agli spostamenti isotropi senza stimare o sottrarre esplicitamente il rumore.

2.1 Invarianza Algebrica tramite Parentesi di Lie

L'idea centrale è che la componente isotropa $\sigma_k^2 I$ risiede nel centro dell'algebra delle matrici. Di conseguenza, essa svanisce sotto l'operazione di parentesi di Lie (commutatore). Gli autori costruiscono un generatore dipendente dallo stato $\Omega(M)$ definito sull'algebra di Lie $\mathfrak{so}(n)$:
$$\Omega(M) = [A(M), D(M)] = A(M)D(M) - D(M)A(M)$$
dove:

• $A(M) = M^\top C_k M$
• $D(M) = \text{diag}(A(M))$

Poiché $[\alpha I, X] \equiv 0$ per qualsiasi scalare $\alpha$ e matrice $X$, il generatore soddisfa:
$$\Omega(M; C_{\text{sig}} + \sigma_k^2 I + E_k) = \Omega(M; C_{\text{sig}} + E_k)$$
Ciò garantisce che la direzione di aggiornamento sia puntualmente identica sia che l'osservazione includa il rumore isotropo sia che non lo includa. Il rumore non viene filtrato; viene strutturalmente annichilito dalla definizione del generatore.

2.2 Aggiornamento Discreto tramite Retrazione di Cayley

L'algoritmo aggiorna la matrice di rotazione $M_k \in SO(n)$ utilizzando la mappa di Cayley per mantenere l'ortogonalità senza costose decomposizioni SVD o QR:
$$M_{k+1} = M_k \cdot \text{Cay}(\eta_k \Omega_k)$$
dove $\text{Cay}(X) = (I - \frac{1}{2}X)^{-1}(I + \frac{1}{2}X)$.
In contesti senza matrice, l'inversa $(I - \frac{\eta}{2}\Omega)^{-1}$ è approssimata tramite una serie di Neumann troncata di ordine $K$ (tipicamente $K=3$ o $4$), richiedendo solo $O(n)$ MVP per iterazione.

2.3 Estensione al Tracciamento dei Top-$k$

Il framework è esteso alla varietà di Stiefel $\text{St}(k, n)$ per il tracciamento dei top-$k$ autovettori. Introducendo un obiettivo di Brockett pesato $J(M) = \text{tr}(M^\top C M N)$ con una matrice di pesi diagonale strettamente ordinata $N$, il metodo isola un autotelaio ordinato preservando la stessa proprietà di invarianza rispetto a $\sigma^2$.

3. Contributi Chiave e Risultati Teorici

3.1 Invarianza Algebrica e Stabilità

• Invarianza Puntuale: La traiettoria discreta $\{M_k\}$ e i valori di Lyapunov sono identici per le osservazioni $\{C_{\text{sig}} + \sigma_k^2 I + E_k\}$ e $\{C_{\text{sig}} + E_k\}$.
• Soglia di Stabilità: La dimensione del passo massima stabile $\eta_{\max} = 1/L_C$ dipende esclusivamente dall'energia del segnale a traccia nulla $\|C_e\|_2$ (dove $C_e = \text{tf}(C_{\text{sig}})$), non da $\sigma_k^2$. Nello specifico, $L_C = (4\sqrt{n} + 8)\|C_e\|_2^2$.

3.2 Stabilità Input-Stato (ISS)

Gli autori stabiliscono che l'algoritmo è Input-to-State Stable rispetto alla perturbazione a traccia nulla $E_e$.

• Sfera di Rumore: Il limite dell'errore allo stato stazionario (raggio della sfera di rumore) è governato esclusivamente da $\|E_e\|$, $\|C_e\|$ e dal gap spettrale $\delta$. È indipendente dal livello di rumore isotropo $\{\sigma_k^2\}$.
• Complessità del Campione: Sotto rumore stocastico, il tasso di convergenza è $O(1/k)$, e la complessità del campione per raggiungere una precisione $\epsilon$ è $O(\|C_e\|_2^2 \sigma_u^2 / (\delta^2 \epsilon))$, dove $\sigma_u^2$ dipende solo dai momenti del rumore anisotropo.

3.3 Convergenza Globale

• Geometria Strict-Saddle: La funzione obiettivo su $SO(n)$ non ha minimi locali spurii. Tutti i punti critici non ottimali sono selle strette.
• Convergenza Quasi-Certa di Haar: Per l'iterazione di Cayley esatta (senza rumore), l'inizializzazione casuale (misura di Haar) converge all'insieme del minimo globale con probabilità 1.
• Entrata in Tempo Finito: Sotto perturbazioni a traccia nulla limitate, l'orbita perturbata entra nel dominio separato spettralmente (dove vale l'analisi ISS locale) in tempo finito partendo da quasi qualsiasi inizializzazione.

3.4 Complessità Computazionale

• **Base Completa ($SO(n)$):**$O(n)$ MVP e aritmetica densa $O(n^3)$ per passo.
• Top-$k$ ($\text{St}(k, n)$): $O(k)$ MVP e aritmetica $O(nk^2 + k^3)$ per passo, consentendo la scalabilità fino a $n \sim 10^4$ per piccoli $k$.

4. Risultati Sperimentali

Il documento convalida le previsioni teoriche attraverso diagnosi numeriche piuttosto che ampi benchmark empirici:

1. Complessità delle Iterazioni vs Rumore: Il metodo di Cayley proposto richiede un numero costante di iterazioni ($\approx 1600$) su quattro ordini di grandezza di rumore isotropo ($\sigma^2 \in [0, 1000]$). Al contrario, "Raw Oja" fallisce completamente per $\sigma^2 \ge 10$, e le linee di base di rimozione della traccia (TF-Oja) comportano un sovraccarico significativo.
2. Correttezza Algebrica: L'implementazione del commutatore soddisfa identità algebriche (ad esempio, profili di fuga di Givens, limiti di ingresso) con precisione di macchina ($\sim 10^{-15}$).
3. Convergenza Globale: Da 100 inizializzazioni casuali di Haar su $SO(15)$, l'algoritmo converge al minimo globale nel 100% dei tentativi.
4. Invarianza di Stiefel: Le traiettorie su $\text{St}(5, 50)$ con $\sigma^2 = 10^4$ sono indistinguibili da quelle con $\sigma^2 = 0$ (differenza $< 2.3 \times 10^{-12}$).

5. Significato e Affermazioni

Il documento afferma di risolvere una limitazione fondamentale nella decomposizione in autovalori in streaming: l'accoppiamento della stabilità algoritmica al pavimento di rumore. Sfruttando l'identità della parentesi di Lie $[\alpha I, \cdot] \equiv 0$, il metodo rende il rumore isotropo "algebricamente invisibile".

• Strutturale vs Stima: A differenza degli approcci di stima della traccia o di denoising, questo metodo non tenta di stimare o sottrarre il parametro di disturbo. Invece, costruisce dinamiche in cui il rumore non può esistere.
• Robustezza: L'approccio fornisce garanzie di convergenza certificate anche quando lo sfondo isotropo è illimitato o impulsivo.
• Ambito: Gli autori limitano esplicitamente il loro ambito agli spostamenti isotropi. Le perturbazioni strutturate (non isotrope) sono al di fuori del framework attuale. La variante a base completa rimane $O(n^3)$, limitandola a $n \lesssim 10^3$, sebbene l'estensione di Stiefel offra scalabilità per il tracciamento a basso rango.

Il lavoro stabilisce un nuovo paradigma per la stima spettrale robusta in cui il modello di rumore è gestito attraverso la struttura geometrica piuttosto che la stima statistica.