Excluding Noise from Short Krylov Subspace Approximations to the Truncated Singular Value Decomposition (SVD)

Report No. ARL-TR-8161
Authors: Alex Breuer
Date/Pages: September 2017; 32 pages
Abstract: The truncated singular value decomposition (SVD) finds numerous applications, from dimension reduction to matrix regularization to data cleaning. The SVD truncated to rank n produces the rank-n approximation with smallest Frobenius norm error and also separates global structure from local deviations and noise. Fully accurate computation of the truncated SVD is often expensive. Krylov subspace approximations of the truncated SVD may be used to realize substantial computational savings. Approximation of the truncated SVD does not require finding an invariant subspace. The iteration may be terminated after only n iterations. Though these Krylov subspace approximations are close to the truncated SVD with respect to the Frobenius norm, they may not reproduce the important data cleaning qualities of the truncated SVD. We link the presence of noise in Krylov subspaces to the start vector and show necessary and sucient conditions on the start vector to produce a Krylov subspace that is free of noise up to an arbitrary threshold. These conditions may be used to design stopping criteria for implicitly or explicitly filtering a start vector to e ect a noise-free Krylov subspace.
Distribution: Approved for public release
  Download Report ( 1.021 MBytes )
If you are visually impaired or need a physical copy of this report, please visit and contact DTIC.
 

Last Update / Reviewed: September 1, 2017