Minimal Krylov Subspaces for Dimension Reduction

Report No. ARL-RP-0480
Authors: Alexander M. Breuer
Date/Pages: May 2014; 200 pages
Abstract: Krylov subspaces may be used as an alternative to singular vector spaces or eigenvector spaces for projective dimension reduction for low-rank matrix approximation. Though the truncated spectral or singular value decomposition is optimal for minimizing Frobenius norm error of a low-rank approximation, substituting a Krylov subspace projection may result in marked compute time savings. Previous efforts to apply Krylov subspaces to low-rank approximation problems are extended to block Krylov subspaces. Closely related random projection methods are compared to block Krylov subspaces, and new hybrid approaches are developed. Hybrid random projection Krylov subspace methods offer faster compute times than random projection methods and lower approximation errors when sufficient conditions are met. A novel adaptively blocked Krylov subspace algorithm is developed that offers superior compute times to random projection methods. Stationary inner iteration is considered for accelerating convergence of Krylov subspaces and applied to the low-rank approximation problem; a generalization of eigenvalue approximation bounds is presented for Krylov subspaces augmented with inner iteration. All aforementioned methods are evaluated in terms offloating-point operations and applied to numerous problems.
Distribution: Approved for public release
  Download Report ( 4.732 MBytes )
If you are visually impaired or need a physical copy of this report, please visit and contact DTIC.

Last Update / Reviewed: May 1, 2014