67 citations · 107 across the 27 of their papers we have counts for
19 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{…
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…
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…
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…
Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
Noah Amsel, Yves Baumann, Paul Beckman +33
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…
Make the most of what you have: Resource-efficient randomized algorithms for matrix computations
Ethan N. Epperly
In recent years, randomized algorithms have established themselves as fundamental tools in computational linear algebra, with applications in scientific computing, machine learning…
Stable algorithms for general linear systems by preconditioning the normal equations
Ethan N. Epperly, Anne Greenbaum, Yuji Nakatsukasa
This paper studies the solution of nonsymmetric linear systems by preconditioned Krylov methods based on the normal equations, LSQR in particular. On some examples, preconditioned…
Randomized Kaczmarz with tail averaging
Ethan N. Epperly, Gil Goldshlager, Robert J. Webber
The randomized Kaczmarz (RK) method is a well-known approach for solving linear least-squares problems with a large number of rows. RK accesses and processes just one row at a time…
Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky
Ethan N. Epperly, Joel A. Tropp, Robert J. Webber
Randomly pivoted Cholesky (RPCholesky) is an algorithm for constructing a low-rank approximation of a positive-semidefinite matrix using a small number of columns. This paper devel…
Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
Ethan N. Epperly, Maike Meier, Yuji Nakatsukasa
One of the greatest success stories of randomized algorithms for linear algebra has been the development of fast, randomized algorithms for highly overdetermined linear least-squar…
Superfast direct inversion of the nonuniform discrete Fourier transform via hierarchically semi-separable least squares
Heather Wilber, Ethan N. Epperly, Alex H. Barnett
A direct solver is introduced for solving overdetermined linear systems involving nonuniform discrete Fourier transform matrices. Such matrices can be transformed into a Cauchy-lik…
Fast and forward stable randomized algorithms for linear least-squares problems
Ethan N. Epperly
Iterative sketching and sketch-and-precondition are randomized algorithms used for solving overdetermined linear least-squares problems. When implemented in exact arithmetic, these…
Kernel quadrature with randomly pivoted Cholesky
Ethan N. Epperly, Elvira Moreno
This paper presents new quadrature rules for functions in a reproducing kernel Hilbert space using nodes drawn by a sampling algorithm known as randomly pivoted Cholesky. The resul…
Robust, randomized preconditioning for kernel ridge regression
Mateo Díaz, Ethan N. Epperly, Zachary Frangella +2
We investigate preconditioned conjugate gradient methods for kernel ridge regression (KRR) problems with a moderate to large number of data points (). We dev…
XTrace: Making the most of every sample in stochastic trace estimation
Ethan N. Epperly, Joel A. Tropp, Robert J. Webber
The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized al…
Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
Yifan Chen, Ethan N. Epperly, Joel A. Tropp +1
The randomly pivoted partial Cholesky algorithm (RPCholesky) computes a factorized rank-k approximation of an N x N positive-semidefinite (psd) matrix. RPCholesky requires only (k…
Efficient error and variance estimation for randomized matrix computations
Ethan N. Epperly, Joel A. Tropp
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 p…
Graph-Induced Rank Structures and their Representations
Shivkumar Chandrasekaran, Ethan N. Epperly, Nithin Govindarajan
A new framework is proposed to study rank-structured matrices arising from discretizations of 2D and 3D elliptic operators. In particular, we introduce the notion of a graph-induce…