Fast Estimation of Principal Eigenspace Using Lanczos Algorithm

This paper considers the problem of finding the principal eigenspace and/or eigenpairs of M × M Hermitian matrices that can be expressed or approximated by a low-rank matrix plus a shift, i.e., A = B + σ I, where B is a rank d Hermitian matrix and d M. Such matrices arise in signal processing, geophysics, dynamic structure analysis, and other fields. The proposed problem can be solved by a full O( M³ ) eigendecomposition, or by several more efficient alternatives, e.g., the power, subspace iteration, and Lanczos algorithms. This paper shows that the Lanczos algorithm can exploit the inherent structure and is generally more efficient than other alternatives. More specifically, if A = B + σ I, the Lanczos algorithm can be used to exactly determine the principal eigenspace span\ B \ and σ with a finite amount of computation. If A is close to B + σ I, the Lanczos algorithm can estimate the principal eigenvectors and eigenvalues in O( M² d ) flops. It is shown that the errors in the estimates of the kth principal eigenvalue λ ₖ and eigenvector eₖ decay at the rate of ε ²/( λ ₖ - σ )² and ε/( λ ₖ - σ ), respectively, where ε is a measure of the mismatch between A and B + σ I.