Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
Petros Drineas, Ilse C. F. Ipsen, Eugenia-Maria Kontopoulou, Malik Magdon‐Ismail · SIAM Journal on Matrix Analysis and Applications · 2018
This paper is concerned with approximating the dominant left singular vector space of a real matrix $A$ of arbitrary dimension, from block Krylov spaces generated by the matrix ${A}{A}^T$ and the block vector $A{X}$. Two classes of results are presented. First are bounds on the distance, in the two- and Frobenius norms, between the Krylov space and the target space. The distance is expressed in terms of principal angles. Second are bounds for the low-rank approximation computed from the Krylov space compared to the best low-rank approximation, in the two- and Frobenius norms. For starting guesses ${X}$ of full column-rank, the bounds depend on the tangent of the principal angles between ${X}$ and the dominant right singular vector space of ${A}$. The results presented here form the structural foundation for the analysis of randomized Krylov space methods. The innovative feature is a combination of traditional Lanczos convergence analysis with optimal approximations via least squares problems.