Excluding Noise from Short Krylov Subspace Approximations to the Truncated Singular Value Decomposition (SVD)
ARMY RESEARCH LAB ABERDEEN PROVING GROUND MD ABERDEEN PROVING GROUND United States
Pagination or Media Count:
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 sufficient 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 effect a noise-free Krylov subspace.
- Statistics and Probability
- Theoretical Mathematics