7
$\begingroup$

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?

enter image description here

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

enter image description here Notebook

$\endgroup$
8
  • 1
    $\begingroup$ See this: en.m.wikipedia.org/wiki/… $\endgroup$
    – lightxbulb
    Apr 20, 2023 at 8:05
  • 2
    $\begingroup$ You might also be interested in some references I gave (ten years ago) in answering this Math.SE Question about numerical eigenvalues of a diagonal-plus-rank-one matrix (a more general problem than the one you've asked about). Readers will benefit from learning more about the context in which your version arose. $\endgroup$
    – hardmath
    Apr 20, 2023 at 12:57
  • 1
    $\begingroup$ @hardmath added clarifications $\endgroup$ Apr 20, 2023 at 16:07
  • $\begingroup$ Thanks, it helps to have an idea about the importance of approximating eigenvalues vs. exact values. Also to think about how likely the components of $h$ are to be nearly equal. $\endgroup$
    – hardmath
    Apr 20, 2023 at 16:14
  • 1
    $\begingroup$ @hardmath more background on this problem is given here $\endgroup$ Apr 21, 2023 at 6:13

1 Answer 1

6
$\begingroup$

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.

Estimator performance comparison

$\endgroup$
2
  • 1
    $\begingroup$ Interesting! The 2h estimator essentially approximates eigenvalues by diagonal values, and the error can be bounded by Gershgorin circle theorem. Not sure why $h_i+h_{i+1}$ works better $\endgroup$ Apr 22, 2023 at 15:51
  • $\begingroup$ thanks for the update, this makes sense. Tried your average formula on random matrices. Seems a lot better than upper/lower bound, although biased $\endgroup$ May 3, 2023 at 22:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.