5
$\begingroup$

In a large (possibly above $5000\times 5000$) matrix, the problem of finding all the eigenvalues and eigenvectors can be solved using iterative methods (Arnoldi, Lanczos etc.). However, there seems to be a convergence happening in these methods suggesting that one can quantify how many eigenvalues/eigenvectors are needed before we have sufficient information and can stop finding more (I apologize for not being able to make this more precise). This is also indirectly suggested in some posts here for example.

To take a concrete example, if I have a large antisymmetric matrix made up of only $\pm 1,0$ then there are several eigenvalues that are close to zero but not exactly zero. Their corresponding eigenvectors are almost parallel but not quite. In this example I would be interested to know how many of these are actually numerical residues.

Can someone suggest how this distinction between important and spurious eigenvalues can be made? Or even in terms of the spectrum (eigenvectors)? In other words given an $n\times n$ matrix (in my case it is also hermitian, but a general answer, if it exists will be nice) can one quantify how many eigenvalues are spurious?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ So if I understand correctly you want to know how many eigenvalues are exactly zero? This is a simpler problem than computing eigenvalues. For a normal matrix (which an antisymmetric matrix is), the number of zero eigenvalues is simply the rank. You can get the rank from the LU factorization of $A$ (which you were already computing anyway if you were using the shift-and-invert mode of Arnoldi / Lanczos). $\endgroup$
    – Federico Poloni
    Commented Oct 17, 2017 at 16:07
  • 1
    $\begingroup$ In statistics the answer would be to pick a percentage, typically 95 and after ordering the eigenvalues by size, only use the eigenvalues that account for 95% of the total variation. $\endgroup$
    – meh
    Commented Oct 17, 2017 at 16:18
  • 1
    $\begingroup$ @FedericoPoloni aginensky's comment is closer to what I'm asking, I'm sorry if that wasn't clear. I am aware that the rank gives the size of the null space. I wanted to know if we could throw away "spurious" eigenvalues and make the null space bigger in this sense, and do this quantitatively $\endgroup$
    – user116085
    Commented Oct 17, 2017 at 17:02
  • $\begingroup$ @aginensky how do you come to that number exactly? what's the criterion? can you give a reference? $\endgroup$
    – user116085
    Commented Oct 17, 2017 at 17:03
  • 1
    $\begingroup$ @FedericoPoloni What I mean is that if I set these eigenvalues to zero by hand and treat their corresponding eigenvectors as just part of the null space then this will still be a good approximation to my original matrix? If yes then in what sense? how would I check? $\endgroup$
    – user116085
    Commented Oct 17, 2017 at 17:43

1 Answer 1

Reset to default
5
$\begingroup$

Antisymmetric matrices are normal, hence they can be diagonalized with an orthogonal matrix. So $\|A\|_F^2=\sum |\lambda_i|^2$. If you keep only the $k$ largest eigenvalues (ordered in modulus: $|\lambda_1| \geq |\lambda_2| \geq \dots \geq |\lambda_k| \geq |\lambda_{k+1}| \geq \dots \geq |\lambda_n|)$ and replace the other ones with zeros, you get the best possible rank-$k$ approximation $A_k$ to $A$ in Frobenius norm (because of the Eckart-Young theorem: the eigendecomposition of a normal matrix is, up to signs and absolute values, an SVD).

Moreover, you can compute exactly the approximation error in Frobenius norm: $\|A-A_k\|_F^2 = \sum_{i=k+1}^n |\lambda_i|^2 = \|A\|_F^2 - \sum_{i=1}^k |\lambda_i|^2$. When this difference is sufficiently small, you can stop your computation (whatever this means).

Improve this answer
$\endgroup$

You must log in to answer this question.