10 papers
Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition
Israa Fakih, Laura Grigori, Karl Pierce
We present a novel leverage score-based sampling strategy for the randomized alternating least squares optimization (ALS) of the canonical polyadic decomposition (CPD-ALS). Unlike…
Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices
Hussam Al Daas, Grey Ballard, Laura Grigori +4
Sketching is widely used in randomized linear algebra for low-rank matrix approximation, column subset selection, and many other problems, and it has gained significant traction in…
Sketch low-rank dynamics: orthogonal vs. oblique projections
Benjamin Carrel, Laura Grigori
We study how sketching techniques from randomized numerical linear algebra can be incorporated into the dynamical low-rank approximation (DLRA) of large-scale matrix differential e…
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…
Restoring similarity in randomized Krylov methods with applications to eigenvalue problems and matrix functions
Laura Grigori, Daniel Kressner, Nian Shao +1
The randomized Arnoldi process has been used in large-scale scientific computing because it produces a well-conditioned basis for the Krylov subspace more quickly than the standard…
Randomized orthogonalization and Krylov subspace methods: principles and algorithms
Jean-Guillaume de Damas, Laura Grigori, Igor Simunec +1
We present an overview of randomized orthogonalization techniques that construct a well-conditioned basis whose sketch is orthonormal. Randomized orthogonalization has recently eme…