# Efficient error and variance estimation for randomized matrix computations

arXiv: https://arxiv.org/abs/2207.06342 · HTML: https://mlsanity.com/paper/2207.06342/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 38 references that are in the map.
- First posted on arXiv 13 Jul 2022.

## Builds on (most cited first, 7 of 7)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [A Bootstrap Method for Error Estimation in Randomized Matrix Multiplication](https://mlsanity.com/paper/1708.01945/) (2017)
- [Error Estimation for Sketched SVD via the Bootstrap](https://mlsanity.com/paper/2003.04937/) (2020)
- [Bootstrapping the Operator Norm in High Dimensions: Error Estimation for Covariance Matrices and Sketching](https://mlsanity.com/paper/1909.06120/) (2019)

## Built on by (most cited first, 1 of 1)

- [Information Limits of Low-Rank Approximation Certification](https://mlsanity.com/paper/2610.03321/) (2026)

## Abstract (arXiv)

Randomized matrix algorithms have become workhorse tools in scientific computing and machine learning. To use these algorithms safely in applications, they should be coupled with posterior error estimates to assess the quality of the output. To meet this need, this paper proposes two diagnostics: a leave-one-out error estimator for randomized low-rank approximations and a jackknife resampling method to estimate the variance of the output of a randomized matrix computation. Both of these diagnostics are rapid to compute for randomized low-rank approximation algorithms such as the randomized SVD and randomized Nystr"om approximation, and they provide useful information that can be used to assess the quality of the computed output and guide algorithmic parameter choices.