67 citations · 107 across the 27 of their papers we have counts for
28 papers
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…
Fast Length-Squared Sampling for Positive-Semidefinite Matrices
Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco +1
We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an positive-semidefinite (psd) matrix: that is, to sample a column with p…
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…
The matrix-vector complexity of
Michał Dereziński, Ethan N. Epperly, Raphael A. Meyer
Matrix--vector algorithms, particularly Krylov subspace methods, are widely viewed as the most effective algorithms for solving large systems of linear equations. This paper establ…
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…
Adaptive randomized pivoting and volume sampling
Ethan N. Epperly
Adaptive randomized pivoting (ARP) is a recently proposed and highly effective algorithm for column subset selection. This paper reinterprets the ARP algorithm by drawing connectio…
Faster Linear Algebra Algorithms with Structured Random Matrices
Chris Camaño, Ethan N. Epperly, Raphael A. Meyer +1
To achieve the greatest possible speed, practitioners regularly implement randomized algorithms for low-rank approximation and least-squares regression with structured dimension re…
Does block size matter in randomized block Krylov low-rank approximation?
Tyler Chen, Ethan N. Epperly, Raphael A. Meyer +2
We study the problem of computing a rank- approximation of a matrix using randomized block Krylov iteration. Prior work has shown that, for block size or , a $(1…
Successive randomized compression: A randomized algorithm for the compressed MPO-MPS product
Chris Camaño, Ethan N. Epperly, Joel A. Tropp
Tensor networks like matrix product states (MPSs) and matrix product operators (MPOs) are powerful tools for representing exponentially large states and operators, with application…
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…
The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution
Zhiyan Ding, Ethan N. Epperly, Lin Lin +1
Subspace-based signal processing techniques, such as the Estimation of Signal Parameters via Rotational Invariant Techniques (ESPRIT) algorithm, are popular methods for spectral es…
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…