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)$
