# Optimal approximate matrix product in terms of stable rank

arXiv: https://arxiv.org/abs/1507.02268 · HTML: https://mlsanity.com/paper/1507.02268/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2015.

## Built on by (most cited first, 30 of 37)

- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [SubGen: Token Generation in Sublinear Time and Memory](https://mlsanity.com/paper/2402.06082/) (2024)
- [Zero-th Order Algorithm for Softmax Attention Optimization](https://mlsanity.com/paper/2307.08352/) (2023)
- [Lifelong Learning with Sketched Structural Regularization](https://mlsanity.com/paper/2104.08604/) (2021)
- [Tanimoto Random Features for Scalable Molecular Machine Learning](https://mlsanity.com/paper/2306.14809/) (2023)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation](https://mlsanity.com/paper/2103.04031/) (2021)
- [Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences](https://mlsanity.com/paper/2112.05359/) (2021)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity](https://mlsanity.com/paper/2411.08773/) (2024)
- [Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners](https://mlsanity.com/paper/2104.14101/) (2021)
- [DiffRed: Dimensionality Reduction guided by stable rank](https://mlsanity.com/paper/2403.05882/) (2024)
- [LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions](https://mlsanity.com/paper/2410.05462/) (2024)
- [Exploiting Explainable Metrics for Augmented SGD](https://mlsanity.com/paper/2203.16723/) (2022)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [Memory-Efficient Fine-Tuning via Low-Rank Activation Compression](https://mlsanity.com/paper/2509.23472/) (2025)
- [A Provably Accurate Randomized Sampling Algorithm for Logistic Regression](https://mlsanity.com/paper/2402.16326/) (2024)
- [TabConv: Low-Computation CNN Inference via Table Lookups](https://mlsanity.com/paper/2404.05872/) (2024)
- [Accurate Coresets for Latent Variable Models and Regularized Regression](https://mlsanity.com/paper/2412.20189/) (2024)
- [Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Method](https://mlsanity.com/paper/2506.17556/) (2025)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (2025)
- [A Unified Theory of Random Projection for Influence Functions](https://mlsanity.com/paper/2602.10449/) (2026)
- [Expand More, Shrink Less: Shaping Effective-Rank Dynamics for Dense Scaling in Recommendation](https://mlsanity.com/paper/2605.23191/) (2026)
- [Learning with Neural Tangent Kernels in Near Input Sparsity Time](https://mlsanity.com/paper/2104.00415/) (2021)
- [Non-PSD Matrix Sketching with Applications to Regression and Optimization](https://mlsanity.com/paper/2106.08544/) (2021)
- [Coresets for Multiple ℓp Regression](https://mlsanity.com/paper/2406.02432/) (2024)
- [Optimal Approximate Matrix Multiplication over Sliding Windows](https://mlsanity.com/paper/2502.18830/) (2025)

## Abstract (arXiv)

We prove, using the subspace embedding guarantee in a black box way, that one can achieve the spectral norm guarantee for approximate matrix multiplication with a dimensionality-reducing map having m = O(tilder/varepsilon2) rows. Here tilder is the maximum stable rank, i.e. squared ratio of Frobenius and operator norms, of the two matrices being multiplied. This is a quantitative improvement over previous work of [MZ11, KVZ14], and is also optimal for any oblivious dimensionality-reducing map. Furthermore, due to the black box reliance on the subspace embedding property in our proofs, our theorem can be applied to a much more general class of sketching matrices than what was known before, in addition to achieving better bounds. For example, one can apply our theorem to efficient subspace embeddings such as the Subsampled Randomized Hadamard Transform or sparse subspace embeddings, or even with subspace embedding constructions that may be developed in the future. Our main theorem, via connections with spectral error matrix multiplication shown in prior work, implies quantitative improvements for approximate least squares regression and low rank approximation. Our main result has also already been applied to improve dimensionality reduction guarantees for k-means clustering [CEMMP14], and implies new results for nonparametric regression [YPW15]. We also separately point out that the proof of the "BSS" deterministic row-sampling result of [BSS12] can be modified to show that for any matrices A, B of stable rank at most tilder, one can achieve the spectral norm guarantee for approximate matrix multiplication of AT B by deterministically sampling O(tilder/varepsilon2) rows that can be found in polynomial time. The original result of [BSS12] was for rank instead of stable rank. Our observation leads to a stronger version of a main theorem of [KMST10].