# Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition

arXiv: https://arxiv.org/abs/2602.13759 · HTML: https://mlsanity.com/paper/2602.13759/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 35 references that are in the map.
- First posted on arXiv 14 Feb 2026.

## Builds on (most cited first, 19 of 19)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Efficient Riemannian Optimization on the Stiefel Manifold via the Cayley Transform](https://mlsanity.com/paper/2002.01113/) (2020)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2303.16510/) (2023)
- [Convergence of Stochastic Gradient Descent for PCA](https://mlsanity.com/paper/1509.09002/) (2015)
- [AdaOja: Adaptive Learning Rates for Streaming PCA](https://mlsanity.com/paper/1905.12115/) (2019)
- [A Modern Analysis of Hutchinson's Trace Estimator](https://mlsanity.com/paper/2012.12895/) (2020)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024)
- [Riemannian stochastic optimization methods avoid strict saddle points](https://mlsanity.com/paper/2311.02374/) (2023)
- [Robust Streaming PCA](https://mlsanity.com/paper/1902.03223/) (2019)
- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)
- [Sparser, Better, Deeper, Stronger: Improving Sparse Training with Exact Orthogonal Initialization](https://mlsanity.com/paper/2406.01755/) (2024)
- [Streaming Heteroscedastic Probabilistic PCA with Missing Data](https://mlsanity.com/paper/2310.06277/) (2023)

## Abstract (arXiv)

We study eigendecomposition on SO(n) under streaming observations Ck = Csig + σk2 I + Ek, where the isotropic background σk2 I may be time-varying and arbitrarily large. Standard algorithms couple their stability to lVert Ck rVert2 ≈ σ2, forcing step sizes, contraction rates, and iteration counts to degrade with the noise floor. We observe that σ2 I lies in the center of the matrix algebra and therefore *should never enter* the eigenspace dynamics. We construct a discrete double-bracket flow whose skew-symmetric generator Omega = [A, operatornamediag(A)] operates in the tangent Lie algebra mathfrakso(n), where scalar multiples of the identity vanish by antisymmetry. The resulting trajectory, Lyapunov function, and maximal stable step size ηmax = 1/LC depend exclusively on the trace-free signal Ce -- achieving pointwise, pathwise σ2-invariance. We establish input-to-state stability with a noise ball governed solely by trace-free perturbations, prove global convergence via strict-saddle geometry and a discrete Lojasiewicz argument, and extend the framework to top-k eigentracking on the Stiefel manifold operatornameSt(k,n) at cost k matrix-vector products per step.