# When big data actually are low-rank, or entrywise approximation of certain function-generated matrices

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 50 references that are in the map.
- First posted on arXiv 3 Jul 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Matrix Completion via Max-Norm Constrained Optimization](https://mlsanity.com/paper/1303.0341/) (2013)
- [Factorization Norms and Hereditary Discrepancy](https://mlsanity.com/paper/1408.1376/) (2014)
- [Near-optimal sample complexity for convex tensor completion](https://mlsanity.com/paper/1711.04965/) (2017)
- [Deterministic tensor completion with hypergraph expanders](https://mlsanity.com/paper/1910.10692/) (2019)
- [Low-Rank Matrix Approximation in the Infinity Norm](https://mlsanity.com/paper/1706.00078/) (2017)
- [Kernel approximation on algebraic varieties](https://mlsanity.com/paper/2106.02755/) (2021)
- [Solving ℓp!-norm regularization with tensor kernels](https://mlsanity.com/paper/1707.05609/) (2017)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)
- [Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensors](https://mlsanity.com/paper/2308.16097/) (2023)
- [Sketching for low-rank nonnegative matrix approximation: Numerical study](https://mlsanity.com/paper/2201.11154/) (2022)
- [Low-rank nonnegative tensor approximation via alternating projections and sketching](https://mlsanity.com/paper/2209.02060/) (2022)

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

- [Manifold-based Algorithms for the Hadamard Decomposition](https://mlsanity.com/paper/2605.28980/) (2026)
- [Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention](https://mlsanity.com/paper/2608.28150/) (2026)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)

## Abstract (arXiv)

The article concerns low-rank approximation of matrices generated by sampling a smooth function of two m-dimensional variables. We identify several misconceptions surrounding a claim that, for a specific class of analytic functions, such n × n matrices admit accurate entrywise approximation of rank that is independent of m and grows as log(n) -- colloquially known as ''big-data matrices are approximately low-rank''. We provide a theoretical explanation of the numerical results presented in support of this claim, describing three narrower classes of functions for which function-generated matrices can be approximated within an entrywise error of order varepsilon with rank O(log(n) varepsilon-2 log(varepsilon-1)) that is independent of the dimension m: (i) functions of the inner product of the two variables, (ii) functions of the Euclidean distance between the variables, and (iii) shift-invariant positive-definite kernels. We extend our argument to tensor-train approximation of tensors generated with functions of the ''higher-order inner product'' of their multiple variables. We discuss our results in the context of low-rank approximation of (a) growing datasets and (b) attention in transformer neural networks.