6
$\begingroup$

Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix.

For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and eigenvectors of the following new matrices:

$$A+\mathbf{\mathit{v}}\mathbf{\mathit{v}}^T\textrm{ and }A-\mathbf{\mathit{v}}\mathbf{\mathit{v}}^T$$

Some relevant questions on the website:

$\endgroup$
3
  • $\begingroup$ What is your question? $\endgroup$
    – Richard
    Sep 3 '20 at 17:17
  • 1
    $\begingroup$ @Richard I want to calculate $A+vv^T$ and $A-vv^T$ efficiently at least with complexity lower than $\mathcal{O}(n^3)$ by using knowledge of the eigen-decomposition from $A$ $\endgroup$ Sep 3 '20 at 18:25
  • $\begingroup$ You could try using inverse iteration starting with the eigenvalues of $A$, but the work to solve the different linear systems for each eigenvalue would probably be so large that it would be faster to just find the eigenvalues of $A+vv^{T}$ from scratch without using the previous eigenvalues. $\endgroup$ Sep 3 '20 at 22:54
9
$\begingroup$

Unfortunately, I don't think there is a good algorithm to do this efficiently.

Given the eigendecomposition $\mathbf A = \mathbf X \mathbf D \mathbf X^T$, one is tempted to project $\mathbf v$ onto the eigenvectors by introducing the vector $\mathbf u = \mathbf X^T \mathbf v$, forming $\mathbf A + \mathbf v \mathbf v^T = \mathbf X \left(\mathbf D + \mathbf u \mathbf u^T \right) \mathbf X^T$, and then attack the inner system (a diagonal matrix with a rank-one update) with something clever. Golub outlines an algorithm for computing such an eigendecomposition here, which requires only $\mathcal O(n^2)$ flops. The catch is that, even once you possess the decomposition $\mathbf D + \mathbf u \mathbf u^T = \mathbf Y\mathbf D_2\mathbf Y^T$, you are still faced with issue of composing the "final" decomposition, $\mathbf A + \mathbf v \mathbf v^T = \left(\mathbf X \mathbf Y \right) \mathbf D_2 \left(\mathbf X \mathbf Y \right)^T$, and to explicitly tabulate the "final" eigenvectors $\mathbf X \mathbf Y$ will require $\mathcal O(n^3)$ flops. This spoils the complexity of doing something clever, it's asymptotically no better than just accumulating $\mathbf A + \mathbf v \mathbf v^T$ and using the common/usual algorithm.

It's worth pointing out that if you're lucky, and $\mathbf v$ is known to be an eigenvector of $\mathbf A$, the eigendecomposition of $\mathbf A + \mathbf v \mathbf v^T$ is easy to puzzle out (all the eigenvectors are the same, and only the eigenvalue associated with $\mathbf v$ will change). With some effort this idea can be extended to the case where $\mathbf v$ is a linear combination of just a handful / $\mathcal O(1)$ of the original eigenvectors. Unfortunately, an arbitrary $\mathbf v$ is probably a combination of all the eigenvectors of $\mathbf A$, which spoils this line of attack for the general case, too.

So, I am pessimistic on this question (but would be happy to be proven wrong).

$\endgroup$
14
  • $\begingroup$ I think the way you point out is very clever. I agree that the algorithm might be very difficult to optimize. However, I think your proposal can reduce computation time as long as the computation of $XY$ is faster than computing the eigen-decomposition of $A$ directly (even if they're all on the magnitude of $\mathcal{O}(n^3)$ $\endgroup$ Sep 3 '20 at 18:31
  • $\begingroup$ Potentially related: math.stackexchange.com/q/3052997 $\endgroup$ Sep 3 '20 at 18:35
  • 1
    $\begingroup$ Incidentally, your answer shows that one can compute the eigenvalues alone (not the eigenvectors) in $O(n^2)$, which is already non-obvious. $\endgroup$ Sep 3 '20 at 18:46
  • $\begingroup$ It's a joy every time to read a good answer: this one doesn't just answer the what, but also the why! $\endgroup$ Sep 3 '20 at 19:10
  • 1
    $\begingroup$ I might have a follow-up, though: The question originally likely starts from wanting to create an "online" algorithm, for example if one is interested in addressing how the covariance matrix (or its eigenvalues) changes with every incoming new sample being measured. In these cases, the changes to the eigenvalues are likely quite small if one already has a lot of samples. This opens up the possibility of thinking of inexact, iterative algorithms to update the eigenvalues: with expected small changes, one might think that one would only need to do 1 or 2 iterations with every new sample. Ideas? $\endgroup$ Sep 3 '20 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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