Jackknife Variability Estimation for Randomized Matrix Computations
Ethan Epperly, California Institute of Technology
In the era of big data, dimensionality reduction has been become an essential tool for learning from large data sets at scale. One essential tool for dimensionality reduction is low-rank matrix approximation by randomized sketching. To use these sketching algorithms safely in applications, they should be coupled with diagnostics to assess the quality of approximation. To meet this need, this project proposes a jackknife resampling method to estimate the variability of the output to a randomized matrix computation. The variability estimate can recognize that a computation re- quires additional data or that the computation is intrinsically unstable. As examples, this project studies jackknife estimates for two randomized low-rank matrix approximation algorithms. In each case, the operation count for the jackknife estimate is independent of the dimensions of the target matrix. In numerical experiments, the estimator accurately assesses variability and also provides an order-of-magnitude estimate of the mean-square error.
Abstract Author(s): Ethan N. Epperly, Joel A. Tropp