Approximate Matrix Multiplication through Joint Leverage Score Sampling

DOI10.48550/arXiv.2610.29466MaRDI QIDQ7401707arXivFDO

Authors Neophytos Charalambides, Mert Pilanci, Alfred O. III Hero, Alfred O. Hero

Publication date 21 October 2026

Published in arXiv

Tldr We propose a non-uniform sampling distribution constructed from the leverage scores of two matrices for approximate matrix multiplication and characterize its associated approximation error in terms of the spectral norm; we provide probability error bounds for the proposed algorithm and discuss connections to data-oblivious approximate matrix multiplication and graph sparsification algorithms.

Full work available at URL https://doi.org/10.48550/arXiv.2610.29466

arXiv classification

eess.SPmath.NA

Cites work

• A Note on Random Sampling for Matrix Multiplication
• A refined laser method and faster matrix multiplication
• A simpler approach to matrix completion
• A statistical perspective on algorithmic leveraging
• A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
• Algorithms, graph theory, and linear equations in Laplacian matrices
• Approximate Matrix Multiplication with Application to Linear Embeddings
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Approximate Weighted $CR$ Coded Matrix Multiplication
• Compressed matrix multiplication
• Compressed Regression
• CUR matrix decompositions for improved data analysis
• Dimensionality reduction for k-means clustering and low rank approximation
• Efficient block approximate matrix multiplication
• Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions
• Fast approximation of matrix coherence and statistical leverage
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Monte-Carlo algorithms for approximate matrix multiplication
• Faster least squares approximation
• Faster matrix multiplication via asymmetric hashing
• Gaussian elimination is not optimal
• Gradient Coding through Iterative Block Leverage Score Sampling
• Gradient coding with iterative block leverage score sampling
• Graph Clustering using Effective Resistance
• Graph Sparsification by Approximate Matrix Multiplication
• Graph Sparsification by Effective Resistances
• Improved approximation algorithms for large matrices via random projections
• Matrix multiplication via arithmetic progressions
• Matrix multiplication via matrix groups
• New bounds for matrix multiplication: from alpha to omega
• On sketching quadratic forms
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Optimal sampling algorithms for block matrix multiplication
• Orthonormal Sketches for Secure Coded Regression
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Perturbations of CUR Decompositions
• Powers of tensors and fast matrix multiplication
• Randomized algorithms for the low-rank approximation of matrices
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Relative-Error CUR Matrix Decompositions
• Sampling algorithms for l₂ regression and applications
• Sketching as a tool for numerical linear algebra
• Spectral sparsification of graphs
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Structural conditions for projection-cost preservation via randomized matrix multiplication
• Sums of random Hermitian matrices and an inequality by Rudelson
• Tensor-structured sketching for constrained least squares
• Uniform sampling for matrix approximation
• Weighted Gradient Coding with Leverage Score Sampling

This page was built for publication: Approximate Matrix Multiplication through Joint Leverage Score Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7401707)