Admissible subspaces and low-rank approximations from the Subspace Iteration method

PEDRO MASSEY

CABA

Workshop; Workshop in Harmonic Analysis, Sampling Theory, Machine Learning, and Data Science; 2022

Departamento de Matemática - FCEN - UBA.

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, theanalysis of convergence of these low rank approximations has been obtained by first estimatingthe (angular) distance between the subspaces produced by the SIM and the dominant subspacesof A. We consider numerical examples which show that in some cases the previous approachinduce upper bounds for the approximation error by low rank matrices that overestimate sucherrors. In order to overcome this difficulty we introduce a substitute of dominant subspaces,that we call admissible subspaces. We develop a convergence analysis of subspaces produced bythe SIM to admissible subspaces; in turn, this analysis allow us to obtain novel estimates for theapproximation error by low rank matrices obtained by the implementation of the deterministicSIM. We further apply these results to obtain a convergence analysis for the randomized SIM.The ideal context for our results (low rank approximations) is when h-th and (h+1)-th singularvalues of A coincide, which does not seem to be covered by previous works in the deterministicsetting. Our results also apply in the more general context in which the h-th singular value ofA belongs to a cluster of singular values