Fall 2018

Error Estimation for Randomized Numerical Linear Algebra: Bootstrap Methods

Tuesday, Sep. 25, 2018 2:30 pm3:00 pm

Add to Calendar


Miles Lopes (UC Davis)

In recent years, many randomized algorithms have been proposed for computing approximate solutions to large-scale problems in numerical linear algebra. However, the user rarely knows the actual error of a randomized solution. For this reason, it is common to rely on theoretical worst-case error bounds as a source of guidance. As a more practical alternative, we propose bootstrap methods to obtain direct error estimates for randomized solutions. Specifically, in the contexts of matrix multiplication and least-squares, we show that bootstrap error estimates are theoretically justified, and incur modest computational cost.