0
$\begingroup$

I have a matrix $X=CC^T$ that I want to diagonalize. Here $C$ is a known $n\times n$ matrix, which I could also factor as $LM$ if it helps, $L$ being a lower triangular matrix and $M$ another matrix. Is there a shortcut to compute the eigenvectors and eigenvalues of $X$, in particular knowing $C$? The matrix $X$ is symmetrical and definite positive.

$\endgroup$
3
  • 2
    $\begingroup$ The complexity is provably $\mathcal{O}(n^3)$ if you want all the eigenvalues (see Golub's book). Some iterative solvers/pre-conditioners can jump start the solve, for example see LOBPCG. $\endgroup$
    – user20857
    Jul 13, 2022 at 22:46
  • 2
    $\begingroup$ This is a very common operation in statistics: given a data matrix X', find eigenvalues of the covariance matrix XX'. Eigenvectors of XX' are the left singular vectors of X, so you have a choice between SVD on X or spectral decomposition on XX' $\endgroup$ Jul 13, 2022 at 22:46
  • $\begingroup$ @SpencerBryngelson The complexity is provably not $O(n^3)$, see e.g. arxiv.org/abs/math/0612264 . $\endgroup$ Jul 18, 2022 at 12:44

1 Answer 1

2
$\begingroup$

The first classical improvement is computing a SVD $C=USV^*$; then $CC^* = U S^2 U^*$ is an eigendecomposition, with the eigenvalues being the squares of the singular values of $C$. This is very advantageous in terms of stability, compared to forming the product and then computing the eigenvalues, because the smallest eigenvalues will be computed with an error that grows with $\kappa(C)$ rather than $\kappa(C)^2$. In terms of CPU time, unfortunately you will not gain much, at least without working directly with LAPACK calls.

If you want something more radical in this direction, there are algorithms for the so-called product eigenvalue problem that let you compute the eigenvalues of a product by making orthogonal transformations directly on its factors, in your case $L$ and $M$; see e.g. https://doi.org/10.1137/S0036144504443110 or https://doi.org/10.1137/0907079 specifically for the SVD. This algorithm is more complex, and implementations are less widely available, but it has the advantage of being backward stable in terms of the original factors: you can prove that it computes the exact eigenvalues of a matrix $\hat{X}$ that would be obtained by starting from $L+\delta_L$, $M+\delta_M$, with perturbations $\|\delta_L\| / \|L\|, \|\delta_M\| / \|M\|$ of the order of machine precision.

In terms of CPU time, using these algorithms can bring a big advantage if the factors have dimensions that are very different one from the other; but when all the factors are square they are slower than their classical counterparts.

$\endgroup$
2
  • $\begingroup$ I am more concerned with the stability of the solution so definitely the SVD approach is attractive. Also, in my current use case, the matrix $C$ is square so it's probably the simplest approach at this time. Thank you for the detailed explanation. $\endgroup$
    – PC1
    Jul 18, 2022 at 15:44
  • $\begingroup$ Happy to help! If stability is your concern then switching to the SVD is a no-brainer, since the algorithms are easily available. The product eigenvalue problem ones are more technical, and I would suggest the investment only if both $L$ and $M$ are severely ill-conditioned and you have reason to suspect some small eigenvalues are mis-computed because of cancellation in forming the product. $\endgroup$ Jul 18, 2022 at 16:12

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.