Publications (34)
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…
Large-scale Outdoor Cell-free mMIMO Channel Measurement in an Urban Scenario at 3.5 GHz
Yuning Zhang, Thomas Choi, Zihang Cheng +14
The design of cell-free massive MIMO (CF-mMIMO) systems requires accurate, measurement-based channel models. This paper provides the first results from the by far most extensive ou…
Low-memory Krylov subspace methods for optimal rational matrix function approximation
Tyler Chen, Anne Greenbaum, Cameron Musco +1
We describe a Lanczos-based algorithm for approximating the product of a rational matrix function with a vector. This algorithm, which we call the Lanczos method for optimal ration…
Nearly Optimal Approximation of Matrix Functions by the Lanczos Method
Noah Amsel, Tyler Chen, Anne Greenbaum +2
Approximating the action of a matrix function on a vector is an increasingly important primitive in machine learning, data science, and statistics, wit…
Non-asymptotic moment bounds for random variables rounded to non-uniformly spaced sets
Tyler Chen
We study the effects of rounding on the moments of random variables. Specifically, given a random variable and its rounded counterpart , we study $|\mathb…
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…
Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method
Tyler Chen, Thomas Trogdon, Shashanka Ubaru
We analyze randomized matrix-free quadrature algorithms for spectrum and spectral sum approximation. The algorithms studied include the kernel polynomial method and stochastic Lanc…
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…
Error bounds for Lanczos-based matrix function approximation
Tyler Chen, Anne Greenbaum, Cameron Musco +1
We analyze the Lanczos method for matrix function approximation (Lanczos-FA), an iterative algorithm for computing when is a Hermitian matri…
Stability of the Lanczos algorithm on matrices with regular spectral distributions
Tyler Chen, Thomas Trogdon
We study the stability of the Lanczos algorithm run on problems whose eigenvector empirical spectral distribution is near to a reference measure with well-behaved orthogonal polyno…
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…
Near-optimal hierarchical matrix approximation from matrix-vector products
Tyler Chen, Feyza Duman Keles, Diana Halikias +3
We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an matrix , accessible only thou…
Krylov-aware stochastic trace estimation
Tyler Chen, Eric Hallman
We introduce an algorithm for estimating the trace of a matrix function using implicit products with a symmetric matrix . Existing methods for implicit…
On the Convergence Rate of Variants of the Conjugate Gradient Algorithm in Finite Precision Arithmetic
Anne Greenbaum, Hexuan Liu, Tyler Chen
We consider three mathematically equivalent variants of the conjugate gradient (CG) algorithm and how they perform in finite precision arithmetic. It was shown in [{\em Behavior of…
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…
Numerical computation of the equilibrium-reduced density matrix for strongly coupled open quantum systems
Tyler Chen, Yu-Chen Cheng
We describe a numerical algorithm for approximating the equilibrium-reduced density matrix and the effective (mean force) Hamiltonian for a set of system spins coupled strongly to…
A spectrum adaptive kernel polynomial method
Tyler Chen
The kernel polynomial method (KPM) is a powerful numerical method for approximating spectral densities. Typical implementations of the KPM require an a prior estimate for an interv…
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…
On the fast convergence of minibatch heavy ball momentum
Raghu Bollapragada, Tyler Chen, Rachel Ward
Simple stochastic momentum methods are widely used in machine learning optimization, but their good practical performance is at odds with an absence of theoretical guarantees of ac…
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…
GMRES, pseudospectra, and Crouzeix's conjecture for shifted and scaled Ginibre matrices
Tyler Chen, Anne Greenbaum, Thomas Trogdon
We study the GMRES algorithm applied to linear systems of equations involving a scaled and shifted matrix whose entries are independent complex Gaussians. When the righ…
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…
Fixed-sparsity matrix approximation from matrix-vector products
Noah Amsel, Tyler Chen, Feyza Duman Keles +3
We study the problem of approximating a matrix with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when is accessed only by ma…
Analysis of stochastic Lanczos quadrature for spectrum approximation
Tyler Chen, Thomas Trogdon, Shashanka Ubaru
The cumulative empirical spectral measure (CESM) of a symmetric matrix is defined as the fraction of eigenvalues of…
Optimal Polynomial Approximation to Rational Matrix Functions Using the Arnoldi Algorithm
Tyler Chen, Anne Greenbaum, Natalie Wellen
Given an by matrix and an -vector , along with a rational function , we show how to find the optimal approximation to from the K…
The Lanczos algorithm for matrix functions: a handbook for scientists
Tyler Chen
Lanczos-based methods have become standard tools for tasks involving matrix functions. Progress on these algorithms has been driven by several largely disjoint communities, resulti…
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…
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…
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…
A posteriori error bounds for the block-Lanczos method for matrix function approximation
Qichen Xu, Tyler Chen
We extend the error bounds from [SIMAX, Vol. 43, Iss. 2, pp. 787-811 (2022)] for the Lanczos method for matrix function approximation to the block algorithm. Numerical experiments…
Predict-and-recompute conjugate gradient variants
Tyler Chen, Erin C. Carson
The standard implementation of the conjugate gradient algorithm suffers from communication bottlenecks on parallel architectures, due primarily to the two global reductions require…
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…
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…
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…