A Short Proof for Gap Independence of Simultaneous Iteration
arXiv:1605.05610
Abstract
This note provides a very short proof of a spectral gap independent property of the simultaneous iterations algorithm for finding the top singular space of a matrix. See Rokhlin-Szlam-Tygert-2009, Halko-Martinsson-Tropp-2011 and Musco-Musco-2015. The proof is terse but completely self contained and should be accessible to the linear algebra savvy reader.