Admissible subspaces and the subspace iteration method

Abstract

In this work we revisit the convergence analysis of the Subspace Iteration Method (SIM) for the computation of approximations of a matrix A by matrices of rank h. Typically, the analysis of convergence of these low-rank approximations has been obtained by first estimating the (angular) distance between the subspaces produced by the SIM and the dominant subspaces of A. It has been noticed that this approach leads to upper bounds that overestimate the approximation error in case the hth singular value of A lies in a cluster of singular values. To overcome this difficulty we introduce a substitute for dominant subspaces, which we call admissible subspaces. We develop a proximity analysis of subspaces produced by the SIM to admissible subspaces; in turn, this analysis allows us to obtain novel estimates for the approximation error by low-rank matrices obtained by the implementation of the deterministic SIM. Our results apply in the case when the h-th singular value of A belongs to a cluster of singular values. Indeed, our approach allows us to consider the case when the hth and the st singular values of A coincide, which does not seem to be covered by previous works in the deterministic setting.