Efficient Error and Variance Estimation for Randomized Matrix Computations

DOI10.1137/23M1558537MaRDI QIDQ6154964zbMATH OpenOpenAlexFDO

Authors Ethan N. Epperly, Joel A. Tropp

Publication date 16 February 2024

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.06342

zbMATH Keywords

error estimationjackknife resamplinglow-rank approximationrandomized algorithms

Mathematics Subject Classification ID

Bootstrap, jackknife and other resampling methods (62F40) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Randomized algorithms (68W20)

Abstract: 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 Nystr"om, and they provide useful information that can be used to assess the quality of the computed output and guide algorithmic parameter choices.

Cites work

• A bootstrap method for error estimation in randomized matrix multiplication
• Algorithm 971
• An Efron-Stein inequality for nonsymmetric statistics
• Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching
• Efron-Stein inequalities for random matrices
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 3782216 (Why is no real title available?)
• scientific article; zbMATH DE number 708500 (Why is no real title available?)
• scientific article; zbMATH DE number 3053501 (Why is no real title available?)
• Numerical methods for large eigenvalue problems
• Randomized numerical linear algebra: Foundations and algorithms
• Sketching as a tool for numerical linear algebra
• Streaming low-rank matrix approximation with an application to scientific simulation
• The jackknife estimate of variance

Cited in

(5)

• Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
• Unified matrix analysis for strong consistency of estimators based on the singular value decomposition with orthogonal projections for noisy datasets
• Fixed-sparsity matrix approximation from matrix-vector products
• Möbius inversion and the iterated bootstrap
• librla: Randomized Linear Algebra Library

This page was built for publication: Efficient Error and Variance Estimation for Randomized Matrix Computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154964)