I would like to discuss or hear an opinion about the following. Given is the (hermitian) $n\times n$ matrix
$A = D+M V M^{\dagger}$
with D diagonal. I would like to calculate the eigenvalues (and vectors) of $A$ as economically as possible. What I would normally apply here is a Lanczos type of algorithm which (as far as I know) does at least not scale as $\mathcal{O} (n^3)$.
First of all do you think a procedure as follows can outperform this?
- low rank approximation of $M V M^{\dagger}$
- use algorithm for diagonalization of a diagonal + low rank matrix
As far as 2. goes I know there exist algorithms which deal with diagonal + rank 1 matrices very efficiently (as discussed here). This for me is an incentive to believe that low rank could simplify the calculation of eigenvalues. However I don't know if this extends to any other but rank 1 matrices.
For 1. there is this paper I found that gives a low rank approximation without the need of SVD.
If V has rank k for small k, then the cheapest way to find spectrum of A is to apply rank 1 update procedure k times.
If k is not small, then the structure of A will not help to speed up direct eigensolvers (like divide-and-conquer or QR).
If only few eigenvalues are required, then the Lanczos algorithm will be the fastest. Low rank approximation of $MVM'$ will not help much. It may save some time in forming matrix-vector products $A x$ required by the Lanczos algorithm, but will disturb eigenvalues substantially.