FAST ESTIMATION OF PRINCIPAL EIGENSPACE USING LANCZOS-ALGORITHM

作     者：XU, GH KAILATH, T 

作者机构：STANFORD UNIVINFORMAT SYST LABSTANFORDCA 94305 

出 版 物：《SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS》 (工业与应用数学会矩阵分析和应用杂志)

年 卷 期：1994年第15卷第3期

页      面：974-994页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：FAST EIGENDECOMPOSITION KRYLOV SUBSPACE LANCZOS ALGORITHM EIGENVALUE MULTIPLICITY 

摘      要：This paper considers the problem of finding the principal eigenspace and/or eigenpairs of M x M Hermitian matrices that can be expressed or approximated by a low-rank matrix plus a shift., i.e., A = B + sigmaI 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(M3) 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 + sigmaI, the Lanczos algorithm can be used to exactly determine the principal eigenspace span{B} and sigma with a finite amount of computation. If A is close to B + sigmaI, the Lanczos algorithm can estimate the principal eigenvectors and eigenvalues in O(M2d) flops. It is shown that the errors in the estimates of the kth principal eigenvalue lambda(k) and eigenvector e(k) decay at the rate of epsilon2/(lambda(k) - sigma)2 and epsilon/(lambda(k) - sigma), respectively, where epsilon is a measure of the mismatch between A and B + sigmaI.