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) @ None #None

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.

Author Information

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

More from the Same Authors