A Short Proof for Gap Independence of Simultaneous Iteration
For researchers in numerical linear algebra, this offers a simplified proof of a known result, but it is incremental as it does not introduce new algorithms or findings.
The paper provides a short, self-contained proof that the simultaneous iteration algorithm for finding the top singular space of a matrix converges independently of spectral gaps, a property previously established in randomized numerical linear algebra.
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.