Abstract
We study matrix-free eigendecomposition under a matrix-vector product (MVP) oracle, where each step observes a covariance operator $C_k = C_{sig} + \sigma_k^2 I + E_k$. Standard stochastic approximation methods either use fixed steps that couple stability to $\|C_k\|_2$, or adapt steps in ways that slow down due to vanishing updates. We introduce a discrete double-bracket flow whose generator is invariant to isotropic shifts, yielding pathwise invariance to $\sigma_k^2 I$ at the discrete-time level. The resulting trajectory and a maximal stable step size $\eta_{max} \propto 1/\|C_e\|_2^2$ depend only on the trace-free covariance $C_e$. We establish global convergence via strict-saddle geometry for the diagonalization objective and an input-to-state stability analysis, with sample complexity scaling as $O(\|C_e\|_2^2 / (\Delta^2 \epsilon))$ under trace-free perturbations. An explicit characterization of degenerate blocks yields an accelerated $O(\log(1/\zeta))$ saddle-escape rate and a high-probability finite-time convergence guarantee.