6 papers
Computing the density of the Kesten-Stigum limit in supercritical Galton-Watson processes
Alice Cortinovis, Sophie Hautphenne, Stefano Massei
This paper proposes a novel numerical method for computing the density of the limit random variable associated with a supercritical Galton-Watson process. This random variable capt…
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…
Detecting when one probe vector is enough for preconditioned log-determinant approximation
Alice Cortinovis, Daniele Toni
We present randomized algorithms for estimating the log-determinant of regularized symmetric positive semi-definite matrices. The algorithms access the matrix only through matrix v…
Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation
Alice Cortinovis, Daniel Kressner
We derive a new adaptive leverage score sampling strategy for solving the Column Subset Selection Problem (CSSP). The resulting algorithm, called Adaptive Randomized Pivoting, can…
Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices
Ya-Chi Chu, Alice Cortinovis
In this work, we analyze the variance of a stochastic estimator for computing Schatten norms of matrices. The estimator extracts information from a single sketch of the matrix, tha…
A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
Alice Cortinovis, Lexing Ying
In this work, we analyze a sublinear-time algorithm for selecting a few rows and columns of a matrix for low-rank approximation purposes. The algorithm is based on an initial unifo…