# Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 3 Nov 2023.

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel](https://mlsanity.com/paper/1908.11775/) (2019)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [Distributed Low Rank Approximation of Implicit Functions of a Matrix](https://mlsanity.com/paper/1601.07721/) (2016)
- [Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix](https://mlsanity.com/paper/1905.11616/) (2019)
- [Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation](https://mlsanity.com/paper/1912.04177/) (2019)
- [An Equivalence Class for Orthogonal Vectors](https://mlsanity.com/paper/1811.12017/) (2018)
- [A Generative Word Embedding Model and its Low Rank Positive Semidefinite Solution](https://mlsanity.com/paper/1508.03826/) (2015)
- [Sketching Transformed Matrices with Applications to Natural Language Processing](https://mlsanity.com/paper/2002.09812/) (2020)
- [Single Pass Entrywise-Transformed Low Rank Approximation](https://mlsanity.com/paper/2107.07889/) (2021)

## Built on by (most cited first, 3 of 3)

- [SubGen: Token Generation in Sublinear Time and Memory](https://mlsanity.com/paper/2402.06082/) (2024)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions](https://mlsanity.com/paper/2410.05462/) (2024)

## Abstract (arXiv)

Inspired by fast algorithms in natural language processing, we study low rank approximation in the entrywise transformed setting where we want to find a good rank k approximation to f(U · V), where U, V^top ∈ ℝn × r are given, r = O(log(n)), and f(x) is a general scalar function. Previous work in sublinear low rank approximation has shown that if both (1) U = V^top and (2) f(x) is a PSD kernel function, then there is an O(nkω-1) time constant relative error approximation algorithm, where ω ≈ 2.376 is the exponent of matrix multiplication. We give the first conditional time hardness results for this problem, demonstrating that both conditions (1) and (2) are in fact necessary for getting better than n2-o(1) time for a relative error low rank approximation for a wide class of functions. We give novel reductions from the Strong Exponential Time Hypothesis (SETH) that rely on lower bounding the leverage scores of flat sparse vectors and hold even when the rank of the transformed matrix f(UV) and the target rank are no(1), and when U = V^top. Furthermore, even when f(x) = xp is a simple polynomial, we give runtime lower bounds in the case when U neq V^top of the form Omega(min(n2-o(1), Omega(2p))). Lastly, we demonstrate that our lower bounds are tight by giving an O(n · poly(k, 2p, 1/ε)) time relative error approximation algorithm and a fast O(n · poly(k, p, 1/ε)) additive error approximation using fast tensor-based sketching. Additionally, since our low rank algorithms rely on matrix-vector product subroutines, our lower bounds extend to show that computing f(UV)W, for even a small matrix W, requires Omega(n2-o(1)) time.