From the 1 of 8 linked papers with an AI index.
8 papers
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…
Almost Navigable Graphs
Pratyush Avi, Christopher Musco
The paper introduces γ‑almost navigability, a relaxed graph property for approximate nearest neighbor search that enables construction of sparse, space‑efficient search graphs in n…
The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm
Noah Amsel, David Persson, Christopher Musco +1
Computing the polar decomposition and the related matrix sign function has been a well-studied problem in numerical analysis for decades. Recently, it has emerged as an important s…
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…
An Exact Algorithm for the Unanimous Vote Problem
Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha +2
Consider independent, biased coins, each with a known probability of heads. Presented with an ordering of these coins, flip (i.e., toss) each coin once, in that order, until we…