17 citations · 23 across the 14 of their papers we have counts for
16 papers
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…
Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure
Lawrence K. Saul, Ningyuan Huang, Dennis Bollweg +2
We investigate when a sparse nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements. The potential for such decomposi…
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…
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…
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…
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…
Elliptic PDE learning is provably data-efficient
Nicolas Boullé, Diana Halikias, Alex Townsend
PDE learning is an emerging field that combines physics and machine learning to recover unknown physical systems from experimental data. While deep learning models traditionally re…
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…
Arbitrary-Depth Universal Approximation Theorems for Operator Neural Networks
Annan Yu, Chloé Becquey, Diana Halikias +2
The standard Universal Approximation Theorem for operator neural networks (NNs) holds for arbitrary width and bounded depth. Here, we prove that operator NNs of bounded width and a…
Discrete variants of Brunn-Minkowski type inequalities
Diana Halikias, Bo'az Klartag, Boaz A. Slomka
We present an alternative, short proof of a recent discrete version of the Brunn-Minkowski inequality due to Lehec and the second named author. Our proof also yields the four funct…
A Cheeger inequality for graphs based on a reflection principle
Edward Gelernt, Diana Halikias, Charles Kenney +1
Given a graph with a designated set of boundary vertices, we define a new notion of a Neumann Laplace operator on a graph using a reflection principle. We show that the first eigen…