Technische Samenvatting: Discrete Double-Bracket Flows voor Isotroop-Geruis Invariante Eigendecompositie

1. Probleemstelling

Het artikel behandelt het probleem van de full-basis matrixvrije eigendecompositie voor een symmetrische operator onder streaming-observaties. Het observatiemodel wordt gegeven door:
$$C_k = C_{\text{sig}} + \sigma_k^2 I + E_k$$
waarbij:

• $C_{\text{sig}} \in \mathbb{R}^{n \times n}$ de signaalcovariantie is met verschillende eigenwaarden.
• $\sigma_k^2 I$ een tijdsvariërende, potentieel onbegrensde isotrope achtergrond (ruisvloer) vertegenwoordigt.
• $E_k$ een anisotrope perturbatie is.
• Toegang beperkt is tot matrix-vectorproducten (MVPs) $v \mapsto C_k v$, wat betekent dat de volledige matrix $C_k$ nooit expliciet wordt opgeslagen of gevormd.

De Kernuitdaging: In regimes met een hoge achtergrond waar $\sigma_k^2 \gg \|C_{\text{sig}}\|_2, lijden standaardalgoritmen (zoals subspace iteratie, Oja's regel, Euclidische gradiëntafdaal met QR-retractie) aan ernstige degradatie. Hun stabiliteit, stapgroottes en contractiesnelheden worden gekoppeld aan de ruisvloer$\sigma_k^2$. Bijvoorbeeld, de contractieverhouding in subspace iteratie nadert eenheid naarmate $\sigma_k^2 \to \infty$, en de effectieve stapgrootte in QR-Oja stort in tot nul. Dit dwingt het aantal iteraties om te schalen als $\Omega(\sigma_k^2 / \Delta)$, waardoor ze onpraktisch worden voor omgevingen met hoge ruis.

2. Methodologie

De auteurs stellen een Discrete Double-Bracket Flow voor die algebraïsche invariantie tegenover isotrope verschuivingen bereikt zonder expliciet de ruis te schatten of af te trekken.

2.1 Algebraïsche Invariantie via Lie-haken

Het centrale inzicht is dat het isotrope component $\sigma_k^2 I$ ligt in het centrum van de matrixalgebra. Bijgevolg verdwijnt het onder de Lie-haakbewerking (commutator). De auteurs construeren een toestandsafhankelijke generator $\Omega(M)$ gedefinieerd op de Lie-algebra $\mathfrak{so}(n)$:
$$\Omega(M) = [A(M), D(M)] = A(M)D(M) - D(M)A(M)$$
waarbij:

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

Omdat $[\alpha I, X] \equiv 0$ voor elke scalair $\alpha$ en matrix $X$, voldoet de generator aan:
$$\Omega(M; C_{\text{sig}} + \sigma_k^2 I + E_k) = \Omega(M; C_{\text{sig}} + E_k)$$
Dit zorgt ervoor dat de updaterichting puntsgewijs identiek is, ongeacht of de observatie de isotrope ruis bevat of niet. De ruis wordt niet gefilterd; ze wordt structureel geannihileerd door de definitie van de generator.

2.2 Discrete Update via Cayley-retractie

Het algoritme update de rotatiematrix $M_k \in SO(n)$ met behulp van de Cayley-afbeelding om orthogonaliteit te behouden zonder dure SVD- of QR-decomposities:
$$M_{k+1} = M_k \cdot \text{Cay}(\eta_k \Omega_k)$$
waarbij $\text{Cay}(X) = (I - \frac{1}{2}X)^{-1}(I + \frac{1}{2}X)$.
In matrixvrije omgevingen wordt de inverse $(I - \frac{\eta}{2}\Omega)^{-1}$ benaderd via een afgeknotte Neumann-reeks van orde $K$ (typisch $K=3$ of $4$), wat slechts $O(n)$ MVPs per iteratie vereist.

2.3 Uitbreiding naar Top-$k$ Tracking

Het kader wordt uitgebreid tot de Stiefel-manie $\text{St}(k, n)$ voor het volgen van de top-$k$ eigenvectoren. Door een gewogen Brockett-doelfunctie $J(M) = \text{tr}(M^\top C M N)$ in te voeren met een strikt geordende diagonale gewichtsmatrix $N, isoleert de methode een geordende eigenframe terwijl dezelfde $\sigma^2$-invariantie-eigenschap behouden blijft.

3. Belangrijkste Bijdragen en Theoretische Resultaten

3.1 Algebraïsche Invariantie en Stabiliteit

• Puntsgewijze Invariantie: De discrete traject $\{M_k\}$ en Lyapunov-waarden zijn identiek voor observaties $\{C_{\text{sig}} + \sigma_k^2 I + E_k\}$ en $\{C_{\text{sig}} + E_k\}$.
• Stabiliteitsdrempel: De maximale stabiele stapgrootte $\eta_{\max} = 1/L_C$ hangt uitsluitend af van de spoorloze signaalenergie $\|C_e\|_2$ (waarbij $C_e = \text{tf}(C_{\text{sig}})$), niet van $\sigma_k^2$. Specifiek geldt $L_C = (4\sqrt{n} + 8)\|C_e\|_2^2$.

3.2 Input-to-State Stabiliteit (ISS)

De auteurs stellen vast dat het algoritme Input-to-State Stabiel is met betrekking tot de spoorloze perturbatie $E_e$.

• Ruisbol: De steady-state foutgrens (straal van de ruisbol) wordt uitsluitend bepaald door $\|E_e\|$, $\|C_e\|$ en de spectrale kloof $\delta$. Het is onafhankelijk van het isotrope ruisniveau $\{\sigma_k^2\}$.
• Steekproefcomplexiteit: Onder stochastische ruis is de convergentiesnelheid $O(1/k)$, en is de steekproefcomplexiteit om precisie $\epsilon$ te bereiken $O(\|C_e\|_2^2 \sigma_u^2 / (\delta^2 \epsilon))$, waarbij $\sigma_u^2$ uitsluitend afhangt van anisotrope ruismomenten.

3.3 Globale Convergentie

• Strict-Saddle Geometrie: De doelfunctie op $SO(n)$ heeft geen spurious lokale minima. Alle niet-optimale kritieke punten zijn strikte zadelpunten.
• Haar-Bijna-Zekere Convergentie: Voor de exacte (ruisvrije) Cayley-iteratie convergeert willekeurige initialisatie (Haar-maat) met waarschijnlijkheid 1 naar de verzameling van het globale minimum.
• Finiet-Tijd Betreden: Onder begrenste spoorloze perturbaties betreedt de verstoorde baan het spectraal gescheiden domein (waar lokale ISS-analyse geldt) in eindige tijd vanuit bijna elke initialisatie.

3.4 Computatiecomplexiteit

• **Full Basis ($SO(n)$):**$O(n)$ MVPs en $O(n^3)$ dichte rekenwerk per stap.
• Top-$k$ ($\text{St}(k, n)$): $O(k)$ MVPs en $O(nk^2 + k^3)$ rekenwerk per stap, wat schaalbaarheid mogelijk maakt tot $n \sim 10^4$ voor kleine $k$.

4. Experimentele Resultaten

Het artikel valideert theoretische voorspellingen via numerieke diagnostiek in plaats van brede empirische benchmarks:

1. Iteratiecomplexiteit vs. Ruis: De voorgestelde Cayley-methode vereist een constant aantal iteraties ($\approx 1600$) over vier ordes van grootte van isotrope ruis ($\sigma^2 \in [0, 1000]$). Daarentegen faalt "Raw Oja" volledig voor $\sigma^2 \ge 10$, en brengen baselines met spoorverwijdering (TF-Oja) aanzienlijke overhead met zich mee.
2. Algebraïsche Correctheid: De commutator-implementatie voldoet aan algebraïsche identiteiten (bijv. Givens-ontsnappingsprofielen, inputgrenzen) tot machineprecisie ($\sim 10^{-15}$).
3. Globale Convergentie: Uit 100 Haar-willekeurige initialisaties op $SO(15)$ convergeert het algoritme in 100% van de trials naar het globale minimum.
4. Stiefel Invariantie: Trajecten op $\text{St}(5, 50)$ met $\sigma^2 = 10^4$ zijn niet te onderscheiden van die met $\sigma^2 = 0$ (verschil $< 2.3 \times 10^{-12}$).

5. Betekenis en Claims

Het artikel claimt een fundamentele beperking in streaming eigendecompositie op te lossen: de koppeling van algoritmische stabiliteit aan de ruisvloer. Door gebruik te maken van de Lie-haak-identiteit $[\alpha I, \cdot] \equiv 0, maakt de methode isotrope ruis "algebraïsch onzichtbaar".

• Structureel vs. Schatting: In tegenstelling tot schatting van het spoor of denoising-benaderingen, probeert deze methode de nuisance-parameter niet te schatten of af te trekken. In plaats daarvan construeert ze dynamica waarin de ruis niet kan bestaan.
• Robuustheid: De aanpak biedt gecertificeerde convergentiegaranties, zelfs wanneer de isotrope achtergrond onbegrensd of impulsief is.
• Scope: De auteurs beperken hun scope expliciet tot isotrope verschuivingen. Gestructureerde (niet-isotrope) perturbaties vallen buiten het huidige kader. De full-basis variant blijft $O(n^3)$, wat deze beperkt tot $n \lesssim 10^3$, hoewel de Stiefel-extensie schaalbaarheid biedt voor low-rank tracking.

Het werk vestigt een nieuw paradigma voor robuuste spectrale schatting waarbij het ruismodel wordt behandeld via geometrische structuur in plaats van statistische schatting.