In my application, I have a sum of diagonal $A$ and rank-1 $B$

$$T=\underbrace{\text{diag}(1-2\alpha h+2\alpha^2 h^2)}_A + \underbrace{\alpha^2 hh^T}_B$$

Where $h$ is a vector $\in \mathbb{R}^d$ with positive entries decaying faster than $1/i$, $\alpha>0$ and $\|T\|<1$. Can eigenvalues of $T$ be approximated faster than $O(d^2)$?

Earlier answer pointed to $O(d^2)$ algorithms for finding full eigendecomposition for general DPR1 matrix, but I'm wondering if the specific structure is useful here.

Motivation: this matrix describes evolution of errors of SGD with step-size $\alpha$ when used to solve Ordinary-Least Squares problem with Hessian $\text{diag}(h)$ and normally distributed observations. In contrast to standard gradient descent where error evolves as $\text{diag}(1-2\alpha h+\alpha^2 h^2)$

  • $\begingroup$ Largest eigenvalue can be obtained numerically using power method or algebraically using Tauberian theorem on the generating function of $\operatorname{Tr}(T^k)$ derived here $\endgroup$ Commented Mar 12, 2023 at 0:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.