Perhaps I’ve missed it, but is there a way to obtain the “economy” eigendecomposition of a matrix whose rank is less than the dimension? That is, if A is size n and rank r < n, I would like to store just r eigenvalues and r eigenvectors. But eigen seems to always return all n eigenvalues and eigenvectors.
In practice, because of floating-point roundoff errors, it’s pretty much impossible to distinguish eigenvalues that are zero from eigenvalues that are just very small. (For the same reason, numerical libraries don’t generally compute the “compact” SVD.)
Of course, you can compute all of the eigenvectors and eigenvalues and then discard those for which |\lambda| / \max |\lambda| falls below some tolerance. In principle, I could imagine an algorithm that does this automatically, but I’m not aware of an existing library routine for this.
Yes, some thresholding would be needed. The rank function already does this, so presumably the same strategy could be used in eigen. I think it would be a nice option to have when working with matrices whose dimension is much greater than their rank.
My deeper interest here is knowing whether the LinearAlgebra package (and perhaps even broader ecosystem) is set up to work with rank-deficient eigendecompositions, since I am developing my own methods to obtain such a representation as part of a larger algorithm. I found that the Eigen type can be constructed with r < n eigenvalues/vectors, but I do not know whether existing methods assume a full representation. I suppose it wouldn’t be too hard to just try.
If the matrix is extremely low rank, you are in a somewhat different regime than the dense linear algebra of LAPACK that is in the LinearAlgebra stdlib — you are may be more in the regime of randomized sketching and similar (ala LowRankApprox.jl).
Indeed, LowRankApprox.jl implements a partial Hermitian eigendecomposition. (If your matrix is not Hermitian, you should be cautious about using eigenvectors at all.)
1 Like
Thanks.
I see that LowRankApprox uses its own datatype for storing the thin factorizations rather than using the Eigen type from LinearAlgebra. I initially thought it would be nice to coopt Eigen for this, but upon further investigation tjhat doesn’t seem quite so useful. In Base there are only 9 methods that take an Eigen and they are all trivial, so it’s not as if there’s a large codebase to take advantage of. And some of these methods (e.g .inv) are only useful if the rank is maximal anyway.