15 papers · 1 filter
A new analysis of the randomly pivoted Cholesky algorithm
Ethan N. W. Epperly
The randomly pivoted Cholesky algorithm is one of the leading methods for computing a low-rank approximation to a large positive-semidefinite matrix. However, while it consistently…
Linear algebra at exponential scale via tensor network dimension reduction
Chris Camaño, Ethan N. Epperly, Raphael A. Meyer +1
Many problems in modern scientific computing are challenging because of a \emph{curse of dimension}, where their mathematical formulation involves objects whose dimension is \emph{…
Sharp analysis of sketched least squares and randomized low-rank approximation
Ethan N. Epperly, Robert J. Webber
Two widely used randomized algorithms are the sketch-and-solve method for least-squares regression and the randomized SVD for low-rank approximation. These algorithms apply a rando…
Numerical Instabilities in the Kaczmarz Method and Stabilization by Iterative Refinement
MichaÅ DereziÅski, Ethan N. Epperly, Deanna Needell +1
The randomized Kaczmarz method and its accelerated variants are a powerful class of iterative methods for solving large-scale linear systems, offering guaranteed convergence with l…
Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
Noah Amsel, Yves Baumann, Paul Beckman +36
This document presents a series of open questions arising in matrix computations, i.e., the numerical solution of linear algebra problems. It is a result of working groups at the w…
Fast, High-Accuracy, Randomized Nullspace Computations for Tall Matrices
Ethan N. Epperly, Taejun Park, Yuji Nakatsukasa
In this paper, we develop RLOBPCG, an efficient method for computing a small number of singular triplets corresponding to the smallest singular values of large, tall matrices. The…