7
$\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:

Improve this question
$\endgroup$
3
  • $\begingroup$ What is your question? $\endgroup$
    – Richard
    Commented Sep 3, 2020 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$
    – Max Wong
    Commented Sep 3, 2020 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$
    – Brian Borchers
    Commented Sep 3, 2020 at 22:54

1 Answer 1

Reset to default
11
$\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).

Improve this answer
$\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$
    – Max Wong
    Commented Sep 3, 2020 at 18:31
  • $\begingroup$ Potentially related: math.stackexchange.com/q/3052997 $\endgroup$
    – Abdullah Ali Sivas
    Commented Sep 3, 2020 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$
    – Federico Poloni
    Commented Sep 3, 2020 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$
    – Wolfgang Bangerth
    Commented Sep 3, 2020 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$
    – Wolfgang Bangerth
    Commented Sep 3, 2020 at 19:14

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.