Total: 1
The article concerns low-rank approximation of matrices generated by sampling a smooth function of two m-dimensional variables. We refute an argument made in the literature that, for a specific class of analytic functions, such matrices admit accurate entrywise approximation of rank that is independent of m. We provide a theoretical explanation of the numerical results presented in support of this argument, describing three narrower classes of functions for which n×n function-generated matrices can be approximated within an entrywise error of order ε with rank O(log(n)ε−2polylog(ε−1)) that is independent of the dimension m: (i) functions of the inner product of the two variables, (ii) functions of the squared Euclidean distance between the variables, and (iii) shift-invariant positive-definite kernels. We extend our argument to low-rank tensor-train approximation of tensors generated with functions of the multi-linear product of their m-dimensional variables. We discuss our results in the context of low-rank approximation of attention in transformer neural networks.