A Bootstrap Method for Error Estimation in Randomized Matrix
  Multiplication
  In recent years, randomized methods for numerical linear algebra have
received growing interest as a general approach to large-scale problems.
Typically, the essential ingredient of these methods is some form of randomized
dimension reduction, which accelerates computations, but also creates random
approximation error. In this way, the dimension reduction step encodes a
tradeoff between cost and accuracy. However, the exact numerical relationship
between cost and accuracy is typically unknown, and consequently, it may be
difficult for the user to precisely know (1) how accurate a given solution is,
or (2) how much computation is needed to achieve a given level of accuracy. In
the current paper, we study randomized matrix multiplication (sketching) as a
prototype setting for addressing these general problems. As a solution, we
develop a bootstrap method for \emph{directly estimating} the accuracy as a
function of the reduced dimension (as opposed to deriving worst-case bounds on
the accuracy in terms of the reduced dimension). From a computational
standpoint, the proposed method does not substantially increase the cost of
standard sketching methods, and this is made possible by an "extrapolation"
technique. In addition, we provide both theoretical and empirical results to
demonstrate the effectiveness of the proposed method.
