Minimal Krylov Subspaces for Dimension Reduction

摘要

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 of floating-point operations and applied to numerous problems.