2 citations · 3 across the 11 of their papers we have counts for
14 papers
Optimal near-optimality bounds for the Lanczos method for matrix functions
Tyler Chen, David Persson
Let be Hermitian positive definite and let denote the Lanczos approximation to . We prove that if or is Stieltjes, then the -norm error of t…
A recursive butterfly factorization with optimality guarantees
David Persson, Paul G. Beckman, Tyler Chen +2
We formalize a recursive format for representing a butterfly matrix. This new format naturally leads to a simple recursive algorithm for computing a quasi-optimal butterfly approxi…
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…
A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
Tyler Chen, Junhyung Lyle Kim, Archan Ray +3
We describe and analyze a simple algorithm for sampling from the solution to a linear system . We assume…
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…
Query Efficient Structured Matrix Learning
Noah Amsel, Pratyush Avi, Tyler Chen +5
We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix given access to matrix-vector product (matvec) queries of the…
GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches
Tyler Chen, Pradeep Niroula, Archan Ray +3
A litany of theoretical and numerical results have established the sketch-and-precondition paradigm as a powerful approach to solving large linear regression problems in standard c…
A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
Tyler Chen, Akshay Seshadri, Mattia J. Villani +7
Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models. However, computing exact Shapley values is diffic…
Quasi-optimal hierarchically semi-separable matrix approximation
Noah Amsel, Tyler Chen, Feyza Duman Keles +4
We present a randomized algorithm for producing a quasi-optimal hierarchically semi-separable (HSS) approximation to an matrix using only matrix-vector products wit…
Provably faster randomized and quantum algorithms for -means clustering via uniform sampling
Tyler Chen, Archan Ray, Akshay Seshadri +6
The -means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the -means algorithm is that each iteration requires time…
Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
David Persson, Tyler Chen, Christopher Musco
The randomized SVD is a method to compute an inexpensive, yet accurate, low-rank approximation of a matrix. The algorithm assumes access to the matrix through matrix-vector product…
Preconditioning without a preconditioner: faster ridge-regression and Gaussian sampling with randomized block Krylov subspace methods
Tyler Chen, Caroline Huber, Ethan Lin +1
We describe a randomized variant of the block conjugate gradient method for solving a single positive-definite linear system of equations. Our method provably outperforms precondit…
Near-optimal convergence of the full orthogonalization method
Tyler Chen, Gérard Meurant
We establish a near-optimality guarantee for the full orthogonalization method (FOM), showing that the overall convergence of FOM is nearly as good as GMRES. In particular, we prov…
Faster randomized partial trace estimation
Tyler Chen, Robert Chen, Kevin Li +3
We develop randomized matrix-free algorithms for estimating partial traces, a generalization of the trace arising in quantum physics and chemistry. Our algorithm improves on the ty…