Error Estimation for Sketched SVD via the Bootstrap
  In order to compute fast approximations to the singular value decompositions
(SVD) of very large matrices, randomized sketching algorithms have become a
leading approach. However, a key practical difficulty of sketching an SVD is
that the user does not know how far the sketched singular vectors/values are
from the exact ones. Indeed, the user may be forced to rely on analytical
worst-case error bounds, which do not account for the unique structure of a
given problem. As a result, the lack of tools for error estimation often leads
to much more computation than is really necessary. To overcome these
challenges, this paper develops a fully data-driven bootstrap method that
numerically estimates the actual error of sketched singular vectors/values. In
particular, this allows the user to inspect the quality of a rough initial
sketched SVD, and then adaptively predict how much extra work is needed to
reach a given error tolerance. Furthermore, the method is computationally
inexpensive, because it operates only on sketched objects, and it requires no
passes over the full matrix being factored. Lastly, the method is supported by
theoretical guarantees and a very encouraging set of experimental results.
