# Approximating eigenvalues of DPR1 matrix with special properties

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

• 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 Commented Mar 12, 2023 at 0:01