Eigenvalues of a $d\times d$ diagonal+rank1 matrix in $O(d)$ time?

Question

Suppose $h$ is a vector of $d$ positive numbers adding up to 1. I'm looking for a $O(d)$ algorithm to estimate eigenvalues of the following diagonal + rank1 matrix:

$$A=2\operatorname{diag}(h)-hh^T$$

Empirically it appears that $2h$ gives a good starting point for eigenvalues of $A$. How could I improve this estimate in $O(d)$ time?

Background: $f(t)=\operatorname{Tr} \exp(-t A)$ gives an estimate of mean error of SGD after $t/2$ steps of solving linear least squares for normally distributed data with covariance eigenvalues $h$ and a random starting distribution of error. Values of $h$ are expected to decay at least as fast as power-law with constant >1

This follows from Equation 5 of Bordelon paper after discarding small terms, using approximation$(I-A)^t\approx e^{-t A} $ and this trace result.

Equivalently, $f(t)$ gives expected value of $\|e\|^2$ after $t/2$ iterations of the form $e\leftarrow e-x\langle e, x\rangle$ for $x\sim \text{Normal}(0,\operatorname{diag}h)$ and isotropic starting $e_0$ with $\|e_0\|^2=1$.

Notebook

Answer 1

I get a substantially better estimate if sort $h$ (descending) and estimate the eigenvalues as:

$$ \tilde\lambda_i = h_i + h_{i+1} $$

---

This works because a symmetric DPR1 matrix (with positive rank-one modification, no duplicate eigenvalues) has the strict interlacing property, which means that

$$ \lambda_1 > d_1 > \lambda_2 > d_2 > ... > \lambda_n > d_n $$

where $d_i$ are the entries of the diagonal matrix without the rank one modification. Details in this paper, introduction up to equation 5. In your matrix structure, the rank one modification is negative, meaning

$$ A = D + \rho h h^T,\quad\rho < 0 $$

and thus the strict interlacing property applies to the negated matrix where the symmetric rank one modification is positive, like

$$ A = -D + \rho h h^T,\quad\rho > 0 $$

For your original matrix, that means

$$ d_i > \lambda_i > d_{i+1} $$

My estimator simply takes the average of the upper and lower bound. The image below shows the result for a random 15 element vector. Your estimator is equivalent to the upper bound shown here.