Timezone: »

 
Poster
Error Estimation for Sketched SVD via the Bootstrap
Miles Lopes · N. Benjamin Erichson · Michael Mahoney

Tue Jul 14 10:00 AM -- 10:45 AM & Tue Jul 14 11:00 PM -- 11:45 PM (PDT) @
in Poster Session 4 »

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 may 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. Furthermore, the method is computationally inexpensive, because it operates only on sketched objects, and hence it requires no extra passes over the full matrix being factored.

Keywords: Monte Carlo Methods · Probabilistic Inference - Approximate, Monte Carlo, and Spectral Methods

Author Information

Miles Lopes (University of California, Davis)
N. Benjamin Erichson (University of California, Berkeley)
Michael Mahoney (UC Berkeley)

More from the Same Authors