mlsanityData to 14 Oct 2026

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

arXiv 2407.03250 ↗First posted 3 Jul 2024math.NA cs.LG cs.NAcited by 3

Not on the map. Why?

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.

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

18 of 50 references.

References · 18

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Rethinking Attention with Performerscited by 1,601
  3. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  4. 2023Representational Strengths and Limitations of Transformerscited by 133
  5. 2023Fast Attention Requires Bounded Entriescited by 102
  6. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  7. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  8. 2013Matrix Completion via Max-Norm Constrained Optimizationcited by 18
  9. 2014Factorization Norms and Hereditary Discrepancycited by 14
  10. 2017Near-optimal sample complexity for convex tensor completioncited by 9
  11. 2019Deterministic tensor completion with hypergraph expanderscited by 6
  12. 2017Low-Rank Matrix Approximation in the Infinity Normcited by 5
6 more
  1. 2021Kernel approximation on algebraic varietiescited by 4
  2. 2017Solving ℓp!-norm regularization with tensor kernelscited by 3
  3. 2023Hardness of Low Rank Approximation of Entrywise Transformed Matrix Productscited by 3
  4. 2023Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensorscited by 2
  5. 2022Sketching for low-rank nonnegative matrix approximation: Numerical studycited by 1
  6. 2022Low-rank nonnegative tensor approximation via alternating projections and sketchingcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Manifold-based Algorithms for the Hadamard Decompositioncited by 2
  2. 2026Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attentioncited by 1
  3. 2026Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structurecited by 0