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$ Mar 12 at 0:01


Your Answer

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

Browse other questions tagged or ask your own question.