17 citations · 23 across the 14 of their papers we have counts for
9 papers · 1 filter
Hutch#: Optimal non-adaptive Frobenius norm estimation
Tyler Chen, Diana Halikias, Christopher Musco +1
The Girard--Hutchinson estimator provides an extremely simple randomized estimate of the Frobenius norm of a matrix that can only be accessed implicitly via matrix-vector produ…
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…
A zero-one law for one-shot system identification
Nicolas Boullé, Diana Halikias, Samuel E. Otto +1
Can a model be identified from one experiment? We study analytic systems that are linearly parameterized by a combination of prescribed dictionary terms, such as partial differenti…
Transpose-free linear algebra
Diana Halikias, Michiel E. Hochstenbach, Alex Townsend
We study the limitations of matrix-free algorithms that access a matrix only through forward matrix-vector products (matvecs) , without access to the transpose $A…
Attention Mechanisms Through the Lens of Numerical Methods: Approximation Methods and Alternative Formulations
Michel Fabrice Serret, Alice Cortinovis, Yijun Dong +10
The attention mechanism is the computational core of modern Transformer architectures, but its quadratic complexity in the input sequence length is the bottleneck for large-scale i…
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…
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…
Operator learning without the adjoint
Nicolas Boullé, Diana Halikias, Samuel E. Otto +1
There is a mystery at the heart of operator learning: how can one recover a non-self-adjoint operator from data without probing the adjoint? Current practical approaches suggest th…
Structured matrix recovery from matrix-vector products
Diana Halikias, Alex Townsend
Can one recover a matrix efficiently from only matrix-vector products? If so, how many are needed? This paper describes algorithms to recover matrices with known structures, such a…