Papers › When big data actually are low-rank, or entrywise approximation of certain...
When big data actually are low-rank, or entrywise approximation of certain function-generated matrices
Stanislav Budzinskiy
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 ε with rank 𝒪(log(n) ε⁻² log(ε⁻¹)) 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections