A Bootstrap Method for Error Estimation in Randomized Matrix Multiplication
arXiv:1708.01945
Abstract
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.
References in corpus (6)
- A Statistical Perspective on Algorithmic Leveraging
- Fast matrix multiplication is stable
- Gaussian and bootstrap approximations for high-dimensional U-statistics and their applications
- Comparing large covariance matrices under weak conditions on the dependence structure and its application to gene clustering
- Sub-Sampled Newton Methods II: Local Convergence Rates
- A Practical Guide to Randomized Matrix Computations with MATLAB Implementations