Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces

Petros Drineas, Ilse C. F. Ipsen, Eugenia-Maria Kontopoulou, Malik Magdon-IsmailSIAM J. Matrix Anal. Appl 2018 · OpenReview

Abstract

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.
BibTeX
@article{drineas2018structural,
  author = {Petros Drineas and Ilse C. F. Ipsen and Eugenia-Maria Kontopoulou and Malik Magdon-Ismail},
  title = {{Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2018},
  url = {https://openreview.net/forum?id=mx7Tt_3qFD},
}

Loading related content...

Figure