Metric Transforms and Low Rank Representations of Kernels for Fast Attention
Authors: Timothy Zer-An Chu
Josh Alman
Gary Miller
Shyam Narayanan
Mark Sellke
Zhao Song
Venue: NeurIPS 2024 spotlight (2024)
Keywords: hardness
impossibility
low rank transform
kernel method
LLM
attention
Primary area: learning_theory
TL;DR: This paper studies the possibility and impossibility for kernel methods and metric transform

Abstract: We introduce a new linear-algebraic tool based on group representation theory, and use it to address three key problems in machine learning.

1. Past researchers have proposed fast attention algorithms for LLMs by approximating or replace softmax attention with other functions, such as low-degree polynomials. The key property of these functions is that, when applied entry-wise to the matrix $QK^{\top}$, the result is a low rank matrix when $Q$ and $K$ are $n \times d$ matrices and $n \gg d$. This suggests a natural question: what are all functions $f$ with this property? If other $f$ exist and are quickly computable, they can be used in place of softmax for fast subquadratic attention algorithms. It was previously known that low-degree polynomials have this property. We prove that low-degree polynomials are the only piecewise continuous functions with this property. This suggests that the low-rank fast attention only works for functions approximable by polynomials. Our work gives a converse to the polynomial method in algorithm design.

2. We prove the first full classification of all positive definite kernels that are functions of Manhattan or $\ell_1$ distance. Our work generalizes an existing theorem at the heart of all kernel methods in machine learning: the classification of all positive definite kernels that are functions of Euclidean distance. 

3. The key problem in metric transforms, a mathematical theory used in geometry and machine learning, asks what functions transform pairwise distances in semi-metric space $M$ to semi-metric space $N$ for specified $M$ and $N$. We provide the first full classification of functions that transform Manhattan distances to Manhattan distances. Our work generalizes the foundational work of Schoenberg, which fully classifies functions that transform Euclidean to Euclidean distances.
 
We additionally prove results about stable-rank preserving functions that are potentially useful in algorithmic design, and more. Our core new tool is called the representation theory of the hyperrectangle.

Metric Transforms and Low Rank Representations of Kernels for Fast Attention
Timothy Chu Independent Researcher cimotuyzchu@@gail.co
Josh Alman Columbia University
Gary Miller
Carnegic Mellon University glmillerècs, cmu, edu
j joshOcs. col columbia. edu
Shyam Narayanan
Mark Sellke
Citadel Securities
Harvard University
shyam. 8, marayaann@gmail.coom
msellkeffas harvard.
Zhao Song
Simons Institute for the Theory of Computing, UC Berkeley magic. linxkde@gmail.ccom
Abstract
We introduce a new linear-algebraic tool based on group representation theory, and use it to address three key problems in machine learning.
1. Past researchers have proposed fast attention algorithms for LLMs by approx- imating replace softmax attention with other functions, such low-degree polynomials. The key property of these functions that, when applied entry- wise the matrix QK the result is low rank matrix when Q and K are n x d matrices and n >> d.
This suggests a natural question: what are all functions f with this property? If other exist and are quickly computable, they can be used in place of softmax for fast subquadratic attention algorithms. It was previously known that low-degree polynomials have this property. We prove that low-degree polynomials are the only piecewise continuous functions with this property. This suggests that the low-rank fast atlention only works for functions approx- imable by polynomials. Our work gives converse to the polynomial method in algorithm design.
We prove the first full classification of all positive definite kernels that are functions of Manhattan or é, distance. Our work generalizes, and also gives new proof for, an existing theorem at the heart of kernel methods in machine learning: the classification of all positive definite kernels that are functions of Euclidean distance.
3. The key problem in metric transforms, mathematical theory used in geome- try and machine learning, asks what functions transform pairwise distances in metric space M to metric space N for specified M and N. We prove the first full classification of functions that transform Manhattan distances Manhattan distances. Our work generalizes the foundational work of Schoen- berg, which fully classifies functions that transform Euclidean to Euclidean distances.
We additionally prove results about stable-rank preserving functions that are poten- tially useful in algorithmic design, and more. Our core tool for all our results is a new technique called the representation theory of the hyperrectangle.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
Kernel methods in linear algebra have numerous applications throughout computer science and machine learning, Consider the following basic questions in this area.
(A) Given any set of low-dimensional points 21, .2, Fn. y1, U2. .. Un E Rdd and function f R + TR, is there a small k < n. and a function F IR - R such that [( Uy)) = FFu)),((u;) for all and j? Equivalently, when I is applied entry-wise to a low-rank (kernel) matrix, is the result always low-rank? What about approximately low-rank?
(B) Given any set of points æ1, F2, ... ... Fu and a (kernel) function f - R. is there some function F such that f f[ - xyy11) (F(x;). F(zy)) for all i and j? Equivalently, is f a positive definite Manhattan kernel?
(C) Given any of points " In, from semi-metric spaces X' and V for which functions does there exist a function F such that fdist (1;,, z3)) = (Fttt)(((x))) F(z))) for all i and j? Equivalently, which functions give a metric transform [DL09] between X' and y?
Question (A) relates to the study and effectiveness of polynomial kernels in machine learning. These kernels have many applications [Sou10], for instance in speeding up attention in LLMs [AS23, KMZ23, TBY 19, KVPF20, AS24b, AS24c, SSWZ23a], in NLP for improving the quality of learning algorithms [KM03, GE08, CHC+ 10] and basic computations [VSP+ 17] during training. Oftentimes, if f is not a polynomial, one may even approximate it by a polynomial (for instance by truncating its Taylor expansion) or use sketching [HAS200, SWYZ21, S7724, SYZ24] in order to achieve some of the benefits of polynomial kernels in exchange for worse accuracy guarantees. This has been particularly effective for the neural tangent kernel [JGH18]. Gaussian kernel [NJW02, RR08, AKK 20, HSW 22], generalized T-Student kernel [BTF04], Cauchy kernel [RR08], and power kernel [FS03].
One can verify that if f' is polynomial, then one can achieve A S dde(()) in question (A). Beyond just kernel methods, this fact has been used to design efficient algorithms throughout computer science using technique called 'the polynomial method in algorithm design' (see e.g.. [AWY14, CW 16, ACW16, Wil18, Alm19, ACSS20, AS23, AS24c, AS24b], and Section 2 below for more examples). Determining which other functions/ have this key property can help to extend these phenomena to more settings.
Kernel methods, and linear-algebraic computations related to the kernel matrix such as those involved in Question (B), are very popular modern machine learning. some applications. such as spectral clustering [vL07, NJW02], semi- cupisvuper learning [Zhu05a, Zhu05b, LSZ* 19, SSLL23, SSL24), Laplacian system solving in geometric graphs [ACSS20] and kernel support vector machines [GSZ23], one needs to explicitly compute the kernel matrix and corresponding function F. On the other hand, for many other applications such as regression or classification algorithms, it suffices to implicitly maintain the kernel matrix, or simply prove that the func- tion F' exists [Smo96, SSB SSB+97]; several prominent recent examples are neural tangent kernel regression [BPSW21, SYZ21, MOSW22, ALS 23, GLS+ 24. LLSS24], tensor kernel regression [Zha22, RSZ22, SZZ24), polynomial kernels [SWYZ21, HAS20, A SYZ24], and signal interpolation [CKPS16, SSWZ23b). This motivates question (B), where we ask whether F exists, but not how efficient it is.
The metric transforms referenced in Question (C) arise naturally in many settings where one wants to transform a set points from a metric space while maintaining some of the metric structure between them. The field was pioneered by Schoenberg [Sch38, Sch42, Sch35] and Von Neumann [NS41]. Very broadly. this allows one to take advantage of algorithmic tools in both metric spaces simultane- ously [DL09]. This approach has proven useful in many areas including visualizing the geometry of BERT [RYW- 19]. computer vision [FLH15, KZR16, 16, KCC17, WZFO5], clustering (MMR19], sketching and embedding norms [AKR 15, IMS terminal embedding [MMMR 18, NN19, CN21], low dimensional embeddings via JL transform [AC06, DKS10), mean estimation [LNRW19 19] nearest neighbor search [AIR18], generative models [XZZ18], fata-sensitive distances in clustering [CMS20), neural networks [Or16]]. harmonic analysis [Aro50, LLLH18, KW71], kernel methods [SSB 97], distance oracle [DSW722], and PDE theory [FS98, CFW12].
Many researchers consider metric transforms when the input and output space are Fuclidean, since more is known about metric transforms in this setting. However, metric transforms between other

---

metrics could have equally rich algorithmic applications, and question (C) generalizes this beyond just Euclidean metrics. We could think of distance metrics two semi-metric spaces X' and V, and the function pair (ʃ, F) can be viewed as a transform from X' to y
In all these settings, there is gap in our current understanding of what kernel functions can be used. For instance, there are number of functions where it is not known whether they are positive definite Manhattan kernels which could be used in classification, semi-supervised learning, and other similar tasks. We will see that a common suite of mathematical tools can be used to address all these different gaps. Most of our results prove that our understanding is complete, and that, for instance, the functions we know to be positive definite Manhattan kernels are, in fact, the only ones. This finally completes our understanding of these important classes of functions. That said, in the setting of preserving the stable rank of matrices, we will find that there are functions that are not polynomials, but that surprisingly do preserve the stable ranks of important matrices. Before we get into our technique in more detail, we first describe our main results in context.
Roadmap. In Section 2, we prove that the only functions which always yield low-rank matrix when applied entry-wise to a low-rank matrix are low-degree polynomials, and explain the application to transformers. In Section 3, we give a classification of positive definite kernels with Manhattan distance input. In Section 4, we categorize all functions which transform Manhattan distances to Manhattan distances or squared Fuclidean distances. In Section 5, we briefly introduce the core tool of this work. In Section 6, we give a conclusion of our work. In Section 7, we discuss the limitations of our work. In Section we discuss the societal impacts of our work.
2 Fast Attention and the Polynomial Method
Fast attention computations in transformers and LLMs [AS23, AS24c, AS24h, AS24a, LSS+ HWL* 24, LSSZ24a, LSSZ24b, KVPF20, TBY+ 19] use the polynomial method as a key ingredient. This is a powerful technique for designing algorithms and constructing combinatorial objects. It states that applying a low-degree polynomial entry-wise to a low rank matrix yields another low-rank matrix. Examples of these low rank matrices include QK /Va for n x matrices Q and K with >> d, which is a key matrix for attention computations in transformers and LLMs.
Fast attention computations rely on a polynomial approximation to the exponential function [AS23] combined with the polynomial method. Past researchers [KMZ23, SSWZ23a, TBY+ 19, KVPF20) suggested replacing the exponential function in softmax attention with a general kernel function f. When f is a low-degree polynomial, researchers leveraged the polynomial method to create fast algorithms for polynomial attention in LLM computations [KMZ23, T 19, KVPF20J. The work of [KMZ23] showed experimentally that polynomial attention has faster training and inference times, with little loss quality on large language models.
Fact 2.1 (The polynomial method, folklore; see e.g. [CLP17]). Suppose f : RR - R is polynomial of degree d. Then, for any matrix M E mR of rank r, letting
[d/2] [d/2)
1)
k: 2
the matrix M E RR given by M/, = f(Mis) has r) S k.
For instance, if = log, n and d < o(log2 n), then
ran < n.
The definition of the polynomial method inspires the following definition:
Definition 2.2 (Preserve low-rank matrices). For a function f R + and positive integer n, we say I preserves low-rank n x n matrices if. for every matrix M E Raxx with rank(M) S [[og2[n)] + +1, the entry-wise application M E Rax= given by M/ := fM, has
rank(M < n.
follows from the polynomial method that low-degree polynomials preserve low rank. Fast attention computations [AS23] rely this low rank preservation property. For any function f that preserves
3

---

low rank, if the low rank decomposition of M can be efficiently computed, one can create replacement for attention that runs in almost linear time the sequence length n. This is a significant improvement over the quadratic time algorithms necessary for (unbounded) softmax attention in L.MM models (implicit in [KM723, AS23, TBY+19, SSW723a)).
This motivates the question:
Question 2.3. Is it possible to generalize the polynomial method (Fact 2.1) to functions I other than polynomials?
In other words, are there functions f which are not polynomials, but such that one starts with any low-rank matrix M, and applies it entry-wise yielding the matrix M then M f also has low rank? If such a function existed, it could allow for faster transformers with a wider variety of attention functions, along with many other algorithmic applications.
We prove that low-degree polynomials are the only piecewise continuous functions f that preserve low rank. This suggests that the low-rank approach to fast attention calculations [AS23, AS24b, AS24c] and fast polynomial attention algorithms [KM723] can only work for functions that are approximations of polynomials.
The polynomial method can also be used in algorithm design design the fastest known algo- rithms for a variety of different, important problems, including: batch Hamming Nearest Neighbor Search [ACW16], the Orthogonal Vectors problem from fine-grained complexity [AWY14, 14, CW 16), All-Pairs Shortest Paths [Wil18, CW16), the lightbulb problem in which one wants to find a planted pair of correlated vectors among a collection of random vectors [Val12, KKK18, Alm com- putational problems related to kernel methods in spectral clustering and semi-supervised learn- ing [ACSS20]. and some stable matching problems [MPS16]. In all these works, one starts with matrix M describing the input data which has low rank, and one transforms it into matrix like M which 'amplifies" the key properties of the data while still having low rank. A similar approach has also been used in the theory of polynomial kernels, such as in algorithms for transformers in NLP [VSP+17. 17, DCLTI8, RNS 18, RWC+19, BMR+20, 20, CND+22 22, ZRG 22, AS23, AS24c, KMZ23, HJK+23, HSK HLSL24, HWL and to bound the ranks of matrices which arise in other settings, such as in the recent resolution of the Cap Set Conjecture from extremal combina- torics [CLP17, EG17], and in recent proofs that Hadamard and Fourier transforms have low 'matrix rigidity' [AW17, DE19, DL19].
For function f to be effective in the polynomial method as described above, it is necessary (but usually not sufficient) that f preserves low-rank n matrices the sense of Definition 2.2. Indeed, in all the aforementioned applications of the polynomial method, such as the algorithm of [ACW 16] and the application transformers that we described above, the original matrix M describing the data can have rank greater than log, The details of how low the rank of Mf must be can vary in the different applications, but is always necessary that M has less than full rank (i.e., rank(M < n).
2.1 Converse for the Polynomial Method
Our starting point is the recent work in mathematics by Guillot, Khare, and Rajaratnam [GKRI7], which partially answers Question 2.3 negatively. This shows that Fact 2.1 cannot be generalized in many settings.
Theorem 2.4 ([GKR17, Theorem B], Informal), Recall that in Fact 2.1, l: is the target rank of the matrix M Fact 2.1 is tight, i.e. its converse is true, when either f is (n 1)-times differentiable and k < n - 1, or if M is required to be positive semi- ceni-iefiitte and ls < n 3.
This past work has gaps where might still result in matrices without full rank, especially since the requirement that of is (n - 1)-times differentiable is quite restrictive. Common functions in machine learning like ELU [CUH15, KVPF20, CLD+ SELU [KUMH17, ZLZ24], and ReLU [HSM* + 00. LSS 20, ZZP* 21, ZLZ24] are not becondddiiffeeent to them. One might imagine getting around this differentiability restriction by using the second part of Theorem 2.4, but unfortunately the matrices M/ involved not required be positive semi-definite. So this second part of the theorem does not apply fast attention, which is core application of functions that preserve low rank.
everywhere, so Theorem 2.4 doesn't 't apply
in fast attention computations are

---

Our first result plugs these gaps, showing that Fact 2.1 cannot be generalized in the settings left open by [GKR17], (See Section C.8 below where we state [GKRI7, Theorem B] more formally and compare it with our Theorem 2.5 in more detail.)
Theorem 2.5 (Informal statement of Theorem C.11), Suppose the the function J - IK does not have any essential discontinuities of the first kind'. If preserves low-rank n. X matrices, then f is polynomial of degree at most [logg(n)]
This shows that functions without essential discontinuities of the first kind, which are also not polynomials, do not preserve low-rank n X matrices, and only polynomials of degree less than [n)] can preserve low-rank n X n matrices. The class of functions without these essential discontinuities of the first kind is very rich, and includes all piecewise continuous functions; it is hard to imagine a reasonable kernel function which is not piecewise continuous. Hence, one cannot hope to improve on the polynomial method by extending it to other functions without essential discontinuities of the first kind.
We conjecture that Theorem 2.5 holds for all functions s R + IR (i.e., that if / has an essential discontinuity of the first kind, then it also does not preserve low-rank matrices). Functions with an essential discontinuity of the first kind are not interesting in our setting since they cannot be efficiently evaluated.
We note that there is a small constant fonttrnt-factor gap between the degree which Fact 2.1 tells us is sufficient for polynomial to preserve low-rank matrices, and the degree which Theorem 2.5 says is necessary: for instance, Fact 2.1 says that polynomials of degree at most Iog2(n) suffice, since
4 1ogz 1 (ng
n,
whereas Theorem 2.5 says that degree less than (ng)(n) is necessary. We leave open the question of closing this gap. although we note that the constant factor in front of the polynomial degree does not play a major role in most of the aforementioned applications Fact 2.1.?
2.2 Weaker Polynomial Methods
Fact 2.1 being essentially tight rules out one way to try to generalize the polynomial method. It is natural to ask whether we can get around this by weakening our constraint on the function f. There are many properties of matrices which can be taken advantage of in the design of fast algorithms, and if we can show that M has any of these properties, it could still lead to improvements in the aforementioned applications.
Approximate Low Rank We first study functions f which, when applied entry-wise to a low- rank matrix M, always result in approximately low-rank matrix M As we mentioned earlier, approximating a non-polynomin kernel function i by a polynomial a common technique for taking advantage of the properties of polynomial kemnls;; when f can be well-approximated by polynomial, then M has approximately low rank for this reason. This raises the question: can functions ff which cannot be well-appro by polynomial also result in approximately low-rank matrices?
Our next result answers this question the negative: the only functions which approximately preserve low rank are approximate polynomials. In other words, if f is not approximately a polynomial, then such an algorithmic approach cannot succeed, as f applied entry- wise to a matrix not close to low rank.
We say matrix M is approximately low-rank if the ratio of its smallest and largest eigenvalues is small; if M were not full rank, then this ratio would be O. If M is approximately low-rank in this sense, then fast algorithms for manipulating follow by using low-rank approximation or approximate
'Recall that f : IR - has an essential discontinuity of the first kind a point e E R neither of the limits lim, f (xr) nor lim [x), converges. By contrast, if exactly one of the two limits converges, it is called an essential discontinuity of the second kind. If both limits converge, but they don't 't both converge to f(c). then it may be removable discontinuity a jump discontinuity.
'For instance, our running example algorithm of [ACW16] only uses an asymptotic bound on how the degree grows with the dimension of the input points, and the constant factor in front of the polynomial degree is ultimately subsumed by 'O' in the running time.
5

---

subspace finding algorithms to find low-rank approximations for the matrix. Analogously, we say is approximately a polynomial if its finite differences are small'; recall that the d-th order finite differences are O for any polynomial of degree < d 1.
Theorem 2.6 (Main result, informal statement of Theorem D.3). Let o= = [log, n', and let & E (0. 1) be sufficiently small. Suppose -R- + R is real analytic function which 5-approximately preserves low-rank matrices, i.e., minielel ell (A-(M))
muxxel4] (MF3] S 6/n for all rank d + 1 matrices M.
Then, the t order finite difference of f. evaluated at a E R. for sufficiently small gaps, is bounded above by 8- Ka- Here, Ka > is scaling factor with the property that if f is rescaled by a factor of e > 0 then Ka is also rescaled by c.
dependence on a scaling factor Ka is necessary since. if f is rescaled by c, this rescales the finite differences of f by but does not change the ratio of any two eigenvalues of any matrix Mr. In Theorem D.3 we also prove similar result if is Lipschitz (and not necessarily real analytic).
Stable Rank Our first two results, Theorem 2.5 and Theorem 2.6, both ruled out approaches to generalizing the polynomial method. Finally, we find one important property of matrices for which we can strictly generalize the polynomial method: stable rank.
Definition 2.7. For a matrix M E Bax", its stable rank is defined as srank(M) ==
IM Marl where
|| p denotes the Frobenius norm of matrix M and |||[] denotes the spectral norm of matrix M.
It is known that srank(M) < rank(M M), but there are example matrices where srank (M) < rank(M/) Moreover, matrices with low stable rank can be manipulated quickly in many applications: for instance, low stable rank matrices are a useful tool in data mining and the study of Banach spaces [MSS17], and very efficient sketching methods are known for matrices with small stable rank [CNW15].
Theorem 2.8 (Informal statement of Theorem J.2). Let M E Raxa be a matrix, and suppose f R50 - IR has the property that for any entry of M, I. VL" S f(2) S vL for some
L E Rso. Then, srank(M)) S srankk(MMM)).
Consider, for instance, the matrices which arise in polynomial method applications [ACW16]; these are matrices M E R=xn where each entry is in the interval [1, Olog n.)l. For these matrices, functions like f(x) x², for any constant > O, which are not polynomial when e is not an integer, still preserve stable rank (they satisfy the condition of Theorem 2.8 with = poly log(n)). By contrast, such bounds on the entries of M do not impact our earlier results, and so such functions do not preserve rank or approximately preserve rank for these matrices.
Unfortunately, it is not clear how to apply this to speed up the polynomial method applications we discussed earlier. Most known applications of stable rank require one to have access to the entire matrix M (in order to, for instance, apply sketching), whereas we are aiming for algorithms whose running time is sublinear in the number of entries of MM. Nonetheless, this is an exciting avenue where one can strictly generalize the polynomial method, and we believe it will have interesting algorithmic applications, and further motivates algorithmic applications of stable rank.
Theorem 2.8 tells us that functions which do not grow too quickly preserve stable rank, although the desired rate of growth depends on the matrix entries. We also prove complementary result about functions which do grow very quickly: In Theorem J.5 we prove that any super- popyr-polynomial function which grows like loog (a) for any e > 0 does not preserve low stable rank, and applying it entry-wise an matrix of rank Olog n)) can result in a matrix of stable rank 1. Hence, there is limit to how much one could improve our Theorem 2.8.
3 Kernel Methods
Our second main application of our techniques is to the study of kernel methods in machine learning. Much of the prior work on kernels methods focuses in the Euclidean distance setting. Our new result
'The d-th order finite difference is the discrete analog of the d-th order derivative. For formal definition of finite differences, see the paragraph on finite differences in Section A.2.

---

shows how to classify kernels in the Manhattan distance setting, We start with defining positive definite kernel.
Definition 3.1 (Positive definite Manhattan/ kernel). A function J is a positive definite bp R.d for any and d, the matrix M E RRux with
kernel if. for any -1,--.
M., =(11 10]1;-233) =zglpp)
is positive semi-definite.
For p we also say is a positive definite Manhattan kernel, and for p we call it a positive definite Euclidean kernel.
Equivalently, f a positive definite Ep kernel if and only if there exists a function F R - such that: (F(z), = f(|x= yylp) for all z. y E F for all Note that H. represents Hilbert space. The proof of the equivalence can be found in [Sch42]. Positive definite kernels are used in machine learning to separate data embedded in TRd using linear separator techniques, when the initial data not linearly separable [Smo96, SSB 97, SOW01, SSO1 In other words, a positive definite kernel can map points in IRd which are not linearly separable, to points in potentially higher dimensions which are linearly separable. Finding such embedding is not easy task in general, but kernel methods solve this problem.
Many regression algorithms require the kernel to be positive definite [Cut09, HTF09). The key idea to pick a function f based on the application so that function like the one in Definition 3.1 can be found which maps the data points to vectors of possible higher dimensions, after which linear separation can be performed efficiently on these higher dimensional points.
Interestingly, linear separator algorithms such as the widely used Support Vector Machines (SVMs) [CV95] can separate the data efficiently long (F(x:, F(y)) is easily computed for any y E Rd, even if F itself cannot be easily computed. By definition of the positive-definite kernel f. we know that
(F(x), F(y)) f(Il= sllp),
which allows us compute (F(x), F(y)) quickly by instead computing wllp). . In other words, in order to apply linear separator algorithms, it suffices to know that an F exists, and not necessarily know what is or how to compute it.
The main known result behind kernel methods is a full classification of all positive-defintte Euclidean kernels in terms of completely monotone functions, which are defined follows:
Definition 3.2 (Completely monotone functions [Ber29]). A function f Rzo + R2o is completely monotone if
(+)))((((x)))
(x) 20
for all k 2 0, > O, and f(0)= 2 lim f(x)
An example of completely monotone function is f(x) == Priior work [Mer09, Sch42, Sch38, SSB $98, SSM98, SOW0I] shows that function f RR - R is positive-definite Euclidean kernel (Definition 3.1) if and only if f(Vx) is completely monotone function (Definition 3.2). natural question to ask is Question 3.3. Is there a result that classifies all positive definite Manhattan kernels?
In our paper, we classify all positive-definite Manhattan kemnels. These kernels are widely used in machine learning for physical and chemical applications [FLLA15, Lil18, LRRK15]. A notable example of such a kernel is the Laplace kernel fo (x) = -o which commonly used in classification tasks [BMM18] 8. However, a full description of all positive-definite Manhattan kernels was not known before our work. In this work, we answer Question 3.3 positively:
Theorem 3.4 (Main result, informal statement of Theorem G.2). f is positive definite Manhattan kernel (Defiittion 3.1) if only if fzz) is completely monotone (Definition 3.2).
Theorem 3.4 classifies all dositive-defintt kernels when the input distance is Manhattan. was previously known that completely monotone functions positive definite Manhattan kernels [Sch38,
7

---

Ass80, DL09], but it was not known these were the only such functions. Interestingly. our new classification similar to the classification result for Euclidean kernels, but without a square root applied to the input. Prior to our result, one could have imagined that there are other positive definite Manhattan kernels to use in SVMs than were previously known. However, our result shows that there are no other such kernels.
We note that our proof techniques also give a new proof of the known result classifying all positive definite Euclidean kernels. This known result is a core insight at the heart of kernel methods in machine learning [SSB+99 + SSM98), but traditional proofs tend use methods related to infinite dimensional harmonic analysis [BCR84].
Metric Transforms
Our final application of our techniques is to metric transforms, a mathematical notion introduced by Von Neumann and Schoenberg [NS41].
Definition 4.1 (Metric transform). Suppose X and are X' to y if. for any finite set S C X. there is function F XX + such that f'dx (2)) dy (x1), F (xx2)), all 1n 322 E S.
spacest. .. Function f transforms
As we discussed earlier, metric transforms arise naturally in many settings where one wants to transform set of points from metric space while maintaining some of the metric structure between them, and they have proven useful for algorithm design many areas.
Typically we have particular metric spaces X and Y' of interest, and would like to determine which functions transform X y. This leads to the key question in metric transforms:
Question 4.2. For a given semi-metric space X and given semi-metric space Y, what is the full classification of functions f that transform X to y/
Metric transforms in the special case where X' and y are both Euclidean distances or close variants are well-studied. Related to Schoenberg and Von Neumann's 's work [NS41], Schoenberg [Sch38] classified all functions that transform Fuclidean distances to Euclidean distances. One natural question arises: what the theory of metric transforms for non-Euclidese metrics?
In the case when X' is Manhattan (or & distance, and Y is Euclidean distance, Schoenberg [Sch38] provided a partial categorization of functions that transform Manhattan distance Euclidean distance. This was followed by Assouad's work in 1980, which provided a partial categorization of functions that transform Manhattan distances to Manhattan distances [Ass80]. This setting is particularly well-motivatee in physical applications. For instance, recent work [GSDV17] studied the problem of inferring a force vector given collection of example configurations via kernel ridge regression; in order to encode certain desired symmetries ('axis reflections") in the problem, Manhattan pre- serving functions must be used to define the kernel. Our work on metric transforms completes the partial categorizations of Schoenberg and Assouad, and proves their partial categorization is full categorization.
Our main result about metric transforms is complete classification of functions that transform Manhattan distances to Manhattan distances. First, need define Bernstein functions:
Definition 4.3 (Bernstein functions [Ber29]). A function f R:20 - R20 Bernstein if f()) = and its derivative I' is completely monotone (see Definition 3.2) when restricted to B., Equivalently, a function f is Bernstein if:
1. (-1)+a''r d' f(m) da
5. for all 2 1, 0:
2. f(x) 2 0 for all x 2 and
'A semi- metric satisfies all the axioms for metric except possibly the triangle inequality; the square of the Euclidean distance gives rise semi-metric. 'When we refer to Euclidean or Manhattan distance in the remainder of this section, we always refer to distances in infinite dimensional Euclidean metric space and infinite dimensional Manhattan metric spaces, respectively.
8

---

3. f0) - 0.
Now we are ready to state our main result:
Theorem 4.4 (Main result, classifying all Manhattan metric transforms, informal version and combi- nation of Theorem E.2 and F.3). For function f R220 + R2o. the following are equivalent:
1. f is Bernstein.
2. f transforms Manhattan distances Manhattan distances.
3. f transforms Manhattan distances to squared Euclidean distances.
was previously known that Bernstein functions transform Manhattan distances to Manhattan dis- tances [Ass80], and that they transform Manhattan distances squared Euclidean distances [Sch38], but in both cases, it was not previously known that these were the only such functions. It was previously conceivable that, in situations where one needs metric transform involving Manhattan spaces, but Bernstein functions do not suffice, one could find other suitable metric transforms; our Theorem 4.4 rules out such a possibility. This also has a number of simple consequences, for instance: given any n points T1, In in the metric space (IR.. &1) for any d, one can use our construction in Theorem 4.4 to explicitly calculate finite dimensional embedding F Rd I such that [(x)) - 1 f([2=; - æz]l1)
5
Core Tool: Representation Theory of the Real Hyperrectangle
Our core mathematical tool tackle all three problems is a new technique call the representation theory of the hyperrectangle. Given a dimensional hyperrectangle (which is just a high dimensional rectangle), consider the matrix D where the ijth entry of the matrix is the Manhattan distance between the ith and jth vertex of the hyperrectangle. We prove this matrix has three key properties:
1. It is 2d x 2d matrix whose rank is + 1, and thus it is a low rank matrix.
2. This matrix is filled with Manhattan distances between points.
3. Applying f entry-wise to this matrix does not change the eigenvectors of this matrix, which are always the columns of the so-called Hadamard matrices [HW78].
We note that the last property is particularly useful for us: it allows us to provide closed formula for the eigenvectors and eigenvalues of D1, This is particularly useful because all of our key questions (on low rank preservation, kernels, and metric transforms) can be viewed as questions about the eigenvalues of certain matrices after function applied entrywise.
The last property can be verified by linear algebra computation, but it can also seen as a conse- quenee of group representation theory. Thus, we call our approach the representation theory of the hyperrectangle. For proofs of all three properties, refer to Appendix B.1 and I.
Conclusion
We demonstrate that low-degree polynomials are the only functions that consistently result in low-rank matrix when applied entry-wise to an existing low-rank matrix, and discuss applications to transformers and LLMs. Additionally, we classify all positive definite kernels that utilize Manhattan distance as their input, enhancing the theoretical framework for applications in various machine learn- ing tasks. Furthermore, we provide complete categorization of functions capable of transforming Manhattan distances into either Manhattan distances or Euclidean distances. We do all three tasks using a new linear algebraic tool called the representation theory of the hyperrectangle. Our findings not only advance the theoretical understanding of attention and kernel methods, but also open up new possibilities for their application in fields such as computational biology and algorithm design. This work completes the theoretical landscape of Manhattan to Manhattan metric transforms, and utilizes a sophisticated blend of mathematical techniques from several domains.
"We remark that the special attention on f(0) in the definitions above is a bit non standadd but are convenient for purposes.

---

7 Limitations
In this paper, we identify a few areas that require further exploration. Firstly, there remains a small constant-factor gap between Fact 2.1 and Theorem 2.5 that has not been fully explored; details can be found in the last paragraph of Section 2.1. Additionally, the application of the stable rank results presents ongoing challenge, as discussed in the second-last paragraph of Section 2.2. Finally, our analysis primarily focuses on LLMs, kernel methods, and metric transforms, potentially limiting its applicability to other methodologies.
Societal Impacts
This paper contributes positively by providing deeper and more comprehensive study of kernel functions and completes the theory of Manhattan to Manhattan metric transforms, a problem that has persisted since 1980 due Assouad's work. It opens up numerous algorithmic applications, potentially including large language models (LLMs), and offers a new direction for designing faster algorithms using stable rank results. However, the practical application of these results remains an open area, requiring additional time and effort to fully realize their potential.
9
Acknowledgments
The authors would like to thank Amol Aggarwal, Ainesh Bakshi, Robi Bhattacharree, Jerry Yao- Chich Hu, Rajesh Jayaram, Monique Laurent, Roie Levin. Yingyu Liang, Han Liu, Ryan O'Donnell, Zhenmei Shi, Kevin Tian, Alex Wang, Yu Wang, Yufa Zhou, Lichen Zhang, Di Zhu, and Goran Zuzic for support and helpful comments. The authors would like to thank Yufa Zhou for writing the conclusion and checklist of the paper. This work was mostly done when Timothy Chu was at Carnegie Mellon University, and later at Google, and when Shyam Narayanan was a student at MIT. Josh Alman is supported in part by NSF Grant CCF-2238221 and Google Research Scholar Award. Gary Miller is supported in part by NSF Grant CCF-1637525 Shyam Narayanan is supported by an NSF Graduate Fellowship and Google Fellowship. For more information related to the paper and adjacent topics, see https // //ww///www//////////////// /t//://wouuutt youtube. com/ /0zhaosong2031 and https:
//space. bilibili. com/ /554558776650066111
References
[AC06] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson- lindenstrauss transform. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC), pages 557-563, 2006.
[ACSS20] Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. Algorithms and hardness for linear algebra on geometric graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 541-552. IEEE, 2020.
[ACW16] Josh Alman, Timothy M Chan, and Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In 2016 IÉEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 467 467-476. IEEE, 2016.
[AIR18] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. In Proceedings of the International Congress of Mathemati- Rio de Janeiro 2018, pages 3287-3318. World Scientifie, 2018.
cians:
[AKK 20] Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Vel- ingker, David P Woodruff, and Amir Zandieh. Oblivious sketching high-degree polynomial kernels. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 141-160. SIAM, 2020.
[AKR15] Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn. Sketching and em- bedding are equivalent for norms. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing (STOC), pages 2015.
10

---

[Alm19] Josh Alman. An illuminating algorithm for the light bulb problem. In SOSA. arXiv preprint 1EXi::8810006740, 2019.
[3]S+23] Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, and Danyang Zhuo Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing. In NeurIPS, 2023.
[Aro50] Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3):337-404, 1950.
[AS23] Josh Alman and Zhao Song. Fast attention requires bounded entries. In NeurlPS, 2023.
[AS24a] Josh Alman and Zhao Song. Fast rope attention: Combining the polynomial method and fast fourier transform. In manuscript, 2024.
[AS24b] Josh Alman and Zhao Song. The fine-grained complexity gradient computation for training large language models. In NeurlPS, arXiv preprint arXiv:2402.04497 2024.
[AS24c] Josh Alman and Zhao Song. How to capture higher-order correlations? generalizing matrix softmax attention to kronecker computation. In ICLR, 2024.
[Ass80] Patrice Assouad. Plongements isométriques dans 11: aspect analytique. Number, 14:1979-1980, 1980.
[AW17] Josh Alman and Ryan Williams. Probabilistic rank and matrix rigidity. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 641-652. 2017.
[AWY14] Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the twenty-sixh annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 218-230. SIAM, 2014.
[Bai99] René Baire. Sur les fonctions de variables réelles. Annali di Matematica Pura ed Applicata (1898-1922), 3(1):1-123, 1899.
[BCR84] Christian Berg, Jens Peter Reus Christensen, and Paul Ressel. Harmonic analysis on semigroups: theory of positive definite and related functions, volume 100. Springer, 1984.
[Ber29] Serge Bernstein. Sur les fonctions absolument monotones. Acta Mathematiaa, 52(1)11 66, 1929.
[BMM18] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kemnel learning. In International Conference on Machine Learning. pages 541-549. PMLR, 2018
[BMR+20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances neural information processing systems (NeurIPS), 33:1877-1901, 2020.
[BPSW21] Jan van den Brand, Binghui Peng. Zhao Song, and Omri Weinstein. Training (over- parametrized) neural networks in near-linear time. In 12th Innovations in Theoretical Computer Science Conference (ITCS), 2021.
[BTF04] Sabri Boughorbel, Jean-Philippe Tarel, and Francois Fleuret. Non-mercer kernels for object recognition. In BMVC, pages 1-10, 2004.
[CDW+21] Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré, Scatter- brain: Unifying sparse and low-rank attention approximation. In NeurIPS, 2021.
[CFW12] Ching-Shyang Chen, Chia-Ming Fan, and PH Wen. The method of approximate particular solutions for solving certain partial differential equations. Numerical Methods for Partial Differential Equations, 28(2)506-522, 2012.

---

[CHC*t 10] Yin- Wen Chang, Cho-Jui Hsich, Kai-Wei Chang, Michael Ringgaard, and Chih-Jen Lin. Training and testing low-degree polynomial data mappings via linear svm. Journal of Machine Learning Research, (4)) 2010.
[CKPS16] Xue Chen, Daniel M Kane, Eric Price, and Zhao Song. Fourier-sparse interpolation without a frequency gap. In 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 741-750. IEEE, 2016.
[CLD+20] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. In International Conference on Learning Representations (ICLR), 2020.
[CLP17] Ernie Croot, Vsevolod F Lev, and Péter Pál Pach. Progression ffree sets in are exponen- tially small. Annals of Mathematics, pages 331-337, 2017.
[CMS20] Timothy Chu, Gary L. Miller, and Donald Sheehy. Exact computation of a manifold metric, via lipschitz embeddings and shortest paths on graph. In SODA, 2020.
[CN21] Yeshwanth Cherapanamjeri and Jelani Nelson. Terminal embeddings in sublinear time. FOCS, 2021.
[CND*22] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebas- tian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022.
[CNW15] Michael Cohen, Jelani Nelson, and David P Woodruff. Optimal approximate matrix product in terms of stable rank. arXiv preprint 1507.0260, 2015.
[Cop82] Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM Journal on Computing, 1 1163):467-471, 1982.
[Cri88] Frank Critchley. On certain linear mappings between inner-product and squared- distance matrices. Linear Algebra and its Applications, 105:91-107, 1988.
[CUH15] Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint 151.0725 2015.
[Cut09] Marco Cuturi. Positive definite kernels machine learning. wwXh::0111.337,20000 2009.
arXiv preprint
[CV95] Corinna Cortes and Vladimir Vapnik. Support- networks. Machine learning, 20(3):273-297, 1995.
[CW16] Timothy M Chan and Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing ruzborov-smolensk In Proceedings of the wenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 1255. SIAM, 2016.
[DCLTI8] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- training of deep bidirectional transformers for language understanding. arXiv preprint 1110000080, 2018.
[DE19] Zeev Dvir and Benjamin L Edelman. Matrix rigidity and the croot-lev-pach lemma. Theory of Computing, 15:1-7,2019.
[De173] Philippe Delsarte, An algebraic approach to the association schemes of coding theory. PhD thesis, Philips Research Laboratories, 1973.
[DKS10] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. A sparse johnson: Lindenstrauss transform. Proceedings of the forty- ACM symposium on Theory of computing, pages 341-350, 2010.
12

---

[DL09] Michel Marie Deza and Monique Laurent. Geometry of Cuts and Metrics. Springer Publishing Company, Incorporated, 1st edition, 2009.
[DL19] Zeev Dvir and Allen Liu. Fourier and circulant matrices are not rigid. In Computational Complexity Conference (CCC), volume 137, pages 17:1-17:23, 2019.
[DSWZ22] Yichuan Deng, Zhao Song, Omri Weinstein, and Ruizhe Zhang. Fast distance oracles for any symmetric norm. arXiv preprint arXiv: 14816, 2022.
[EG17] Jordan S Ellenberg and Dion Gijswijt. On large subsets of with no three-term arithmetic progression. Annals of Mathematics, pages 339-30-0 9399-33,,40 2017.
[EGH+ 11] Pavel I Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex Schwendner, Dmitry Vaintrob, and Elena Yudovina. Introduction to representation theory, volume 59, American Mathematical Soc., 2011.
[FLH15] Aasa Feragen, Francois Lauze, and Soren Hauberg. Geodesic exponential kernels: When curvature and linearity conflict. In Proceedings of the IEEE conference computer vision and pattern recognition (CVPR), pages 5032-3042. 2015.
[FLLA15] Felix Faber, Alexander Lindmaa, O Anatole von Lilienfeld, and Rickard Armiento. Crystal structure representations for machine learning models of formation energies. International Journal of Quantum Chemistry, 115(16): 1094-1101, 2015.
[Fro12] Georg Frobenius. Über matrizen aus nicht negativen elementen. 1912.
[FS98] Carsten Franke and Robert Schaback. Solving partial differential equations by colloca- tion using radial basis functions. Applied Mathematics and Computation, 93(1):73-82 822,
1998.
[FS03] François Fleuret and Hichem Sahbi. Scale-invariance of support vector machines based on the triangular kernel. 3rd International Workshop on Statistical and Computational Theories of Vision, pages 1-13, 2003.
[F7S21] William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2 2021.
[GE08] Yoav Goldberg and Michael Elhadad. splitsvm: fast, space-efficient, non-heuristic, polynomial kernel computation for nlp applications. In Proceedings of ACL-08: HLT, Short Papers, pages 237-240, 2008.
[GKR17] Dominique Guillot, Apoorva Khare, and Bala Rajaratnam. Preserving positivity for rank-constrained matrices. Transactions of the American Mathematical Society, 369(9):6105-61) 6145, 2017.
[G] Jiuxiang Gu, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. Differential pri- vacy mechanisms in neural tangent kernel regression. arXiv preprint 2rXIv:2407.13621. 2024.
[GSDV17] Aldo Glielmo, Peter Sollich, and Alessandro De Vita. Accurate interatomic force fields via machine learning with covariant kernels. Physical Review B, 95(21))214302, 2017.
[GS723] Yuzhou Gu, Zhao Song, and Lichen Zhang. Faster algorithms for structured linear and kernel support vector machines. arXiv preprint arXiv:2307.07735 2023.
[HAS20] Insu Han, Haim Avron, and Jinwoo Shin. Polynomial tensor sketch for element-wise function of low-rank matrix. In International Conference Machine Learning, pages 3984-3993. PMLR, 2020.
[HJK+23] Insu Han, Rajesh Jarayam, Amin Karbasi, Vahab Mirrokni, David P Woodruff, and Amir Zandieh. Hyperattention: Long-context attention near-linear time. arXiv preprint 200.0233, 2023.
13

---

[HLSL24] Jerry Yao- Hu, Thomas Lin, Zhao Song, and Han Liu. On computational lim- its of modern hopfield models: fine-grained complexity analysis. In Forty-first International Conference on Machine Learning (ICML., 2024.
[HSK*24) lerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computational limits of low-rank adaptation (Iora) for transformer-hased models. arXiv preprint arXiv:2406.0m 03136, 2024.
[HSM+00] Richard HR Hahnloser, Rahul Sarpeshkar, Misha A Mahowald, Rodney J Douglas, and H Sebastian Seung. Digital selection and analogue amplification coexist cortex-inspired silicon circuit. Nature, 40546777) 2000.
[2S Baihe Huang, Zhao Song, Omri Weinstein, Hengjie Zhang, and Ruizhe Zhang. A dynamic fast gaussian transform. arXiv preprint arXiv:2202.123299 2022.
[HTF09] T Hastic, R Tibshirani, and Friedman. Data mining, inference, and prediction. the elements of statistical learning. .. 2009.
[HW78] A Hedayat and Walter Dennis Wallis. Hadamard matrices and their applications. The Annals of Statistics, 6(6): ((6):1184-220) 1238, 1978.
[4] Jerry Yao-Chich Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, and Han Liu. On statistical rates and provably efficient criteria of latent diffusion transformers (dits). In eightt Conference on Neural Information Processing Systems (NeurIPS), 2024.
[MMS17] Piotr Indyk, Jifí Matoušck, and Anastasios Sidiropoulos. low-distortion embeddings finite metric spaces. In Handbook of discrete and computational geometry, pages 211-231. Chapman and Hall/CRC, 2017.
[JGH18] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Con- vergence and generalization in neural networks. In Advances in neural information processing systems (NeurIPS), pages 8571-8580 2018.
[KCC17] Irene Kaltenmark, Benjamin Charlier, and Nicolas Charon. A general framework for curve and surface comparison and registration with oriented varifolds. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pages 3346-3355, 2017.
[KKK18] Matti Karppa, Petteri Kaski, and Jukka Kohonen. A faster subquadratic algorithm for finding outlier correlations. ACM Transactions on Algorithms (TALG), 14(3):1-26, 2018.
[KKL19] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient trans- former. In International Conference on Learning Representations (ICLR). 2019.
[KМ03] Taku Kudo and Yuji Matsumoto. Fast methods for kernel- text analysis. In Pro- ceedings of the 41st Annual Meeting of the Association for Computational Linguistics, pages 24-31, 2003.
[MΣ22]] Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: Fast trans- formers via sketches for polynomial kernels. arXiv preprint arXiv:2310.01655 2023.
[KUMH17] Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self- normalizing neural networks. Advances in neural information processing systems, 30, 2017.
[KVPF20] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Trans- formers are rnns: Fast autoregressive transformers with linear attention. In International conference machine learning, pages 5156-5165. PMLR, 2020.
[KW71] George Kimeldorf and Grace Wahba. Some results on tchebycheffian spline functions. Journal of mathematical analysis and applications, 33(1):82-95, 1971.
14

---

[KZR16] Soheil Kolouri, Yang Zou, and Gustavo K. Rohde. Sliced wasserstein kernels for probability distributions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5258-558885 5267, 2016.
[Lax02] Peter Lax. Functional Analysis. Wiley, 1st edition, 2002.
[Lil18] O Anatole Von Lilienfeld. Quantum machine learning in chemical compound space. Angewandte Chemie International Edition, 57(16): 4169, 2018.
[LLLH18] Shaogao Lv, Huazhen Lin, Heng Lian, and Jian Huang. Oracle inequalities for sparse additive quantile regression reproducing kernel hilbert space. The Annals of Statistics, 46(2):781-98) 1-813, 2018.
[LLSS24] Chenyang Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. Exploring the frontiers of softmax: Provable optimization, applications in diffusion model, and beyond. arXiv preprint arXiv:2405.0325/,, 2024.
[LNRW19] Jerry Li, Aleksandar Nikolov, llya Razenshteyn, and Erik Waingarten. On mean estimation for general norms with statistical queries. In Conference Learning Theory, pages 2158-211 2172. PMLR, 2019.
[LRRK15] O Anatole Von Lilienfeld, Raghunathan Ramakrishnan, Matthias Rupp, and Aaron Knoll. Fourier series of atomic radial distribution functions: molecular fingerprint for machine learning models of quantum chemical properties. International Journal of Quantum Chemistry, 115(16):0844-093 2015.
[LSS+20] Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu. Generalized leverage score sampling for neural networks. In NeurIPS, 2020.
[LSS+24) Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, and Yufa Zhou. Multi-layer transformers gradient can be approximated in almost linear time. arXiv preprint arXiv:2408.1322. 2024.
[LSS7244] Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Differential privacy of cross-attention with provable guarantee. arXiv preprint 1771:22407.17777.1 2024.
[LSSZ24b] Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Tensor attention training: Prov- ably efficient learning of higher-order transformers. arXiv preprint arXiv:2405.1666 16411, 2024.
19] Xuanqing Liu, Si Si, Xiaojin Zhu, Yang Li, and Cho-Jui Hsieh. A unified framework for data poisoning attack graph-based supe-supe learning. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[LWD+23] Zichang Liu, Jue Wang, Tri Dao, Tianyi Zhou, Binhang Yuan, Zhao Song, Anshumali Shrivastava, Ce Zhang, Yuandong Tian, Christopher Re, et al. Deja vu: Contextual sparsity for efficient 1lms at inference time. In International Conference Machine Learning, pages 22137-22176. PMLR, 2023.
[Mer09] James Mercer. Functions of positive and negative type, and their connection the theory of integral equations. Philosophical transactions of the royal society of London. Series A, containing papers of mathematical or physical character, 45944444488::45444444 446, 1909.
[MMMR18 18] Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Nonlinear dimension reduction via outer bi-lipschitz extensions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1088- 1008-1101, 2018
[MMR19] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of Sohnson-lindenstrann transform for k-means and k-medians clustering. In Proceedings of the 5 51 Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1037-1038, 2019.
15

---

[MOSW22] Alexander Munteanu, Simon Omlor. Zhao Song. and David P. Woodruff. Bounding the width of neural networks via coupled initialization A worst case analysis. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 16083-16122. PMLR, 2022.
[MPS16] Daniel Moeller, Rumamohan Paturi, and Stefan Schneider. Subquadratic algorithms for succinet stable matching. In International Computer Science Symposium Russia, pages 294-308. Springer, 2016.
[MSS17] Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. Interlacing families ii:: Sharper restricted invertibility estimates. arXiv preprint arXiv: VIXiv:1712.07766, 2017.
[NJW02] Andrew Y Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and algorithm. In Advances in neural information processing systems (NeurIPS), pages 849-856, 2002.
[NN19] Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in euclidean space. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1064-1069, 2019.
[NS41] J. Von Neumann and I. J. Schoenberg. Fourier integrals and metric geometry. Transac- tions of the American Mathematical Society, 50(2):22-251, 1941.
[O'D14] Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, New York, NY, USA, 2014.
[On96] Mark JL. Orr. Introduction to radial basis function networks, 1996.
[Par12] Pablo A. Parrilo. Algebraic techniques and semidefinite optimization, February 2012.
[Per07] Oskar Perron. Zur theorie der matrices. Mathematische Annalen, 64(2):244-263 1907.
[RNS 18] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et Improving language understanding by generative pre-training. 2018.
[RR08] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems (NIPS), pages 1177-1184, 2008.
[RS722] Aravind Reddy, Zhao Song, and Lichen Zhang. Dynamic tensor product regression. In Conference on Neural Information Processing Systems (NeurIPS), pages 4791-4804, 2022.
[RWC+19] 19] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 1(8):9, 2019.
19YW+19] Emily Reif, Ann Yuan, Martin Wattenberg, Fernanda B Viegas, Andy Coenen, Adam Pearce, and Been Kim. Visualizing and measuring the geometry of bert. Advances in Neural Information Processing Systems, 32, 2019.
[Sch35] I. J. Schoenberg. Remarks to maurice frechet's 's article" sur la definition axiomatique d' une classe d' espace distancies vector! ellement applicable sur l'espace de hilbertl. Ann. of Math, 36:724-732, 1935.
[Sch37] I. Schoenberg. On certain metric spaces arising from euclidean spaces by change of metric and their imbedding in hilbert space. Annals of Mathematics, 38(4)7787-793, 1937.
[Sch38] I. J. Schoenberg. Metric spaces and positive definite functions. Trans. Amer. Math. Soc., 44:522-536. 1938.
[Sch42] Schoenberg. Positive definite functions on spheres. Duke Math. J, 1:172, 1942.
[Smo96] Alex J Smola. Regression estimation with support vector learning machines. PhD thesis. Master's thesis, Technische Universität München, 1996.
16

---

[Sou10] César R Souza. Kernel functions for machine learning applications. Creative Commons
Share Alike, 3:29, 2010.
[SOW01] Alex J Smola, Zoltan Ovari, and Robert C Williamson. Regularization with dot- product kernels. In Advances in neural information processing systems (NeurIPS), pages 308-314, 2001.
[SS01] Bernhard Scholkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001.
[SSB+97] Bernhard Scholkopf, Kah-Kay Sung, Christopher JC Burges, Federico Girosi, Partha Niyogi, Tomaso Poggio, and Vladimir Vapnik. Comparing support vector machines with gaussian kernels to radial basis function classifiers. IEEE transactions on Signal Processing, 45(11)2275 2265, 1997.
[SSL24] Yiyou Sun, Zhenmei Shi, and Yixuan Li. A graph- thepeethe framework for understand- ing open-world world semi supervised learning. Advances in Neural Information Processing Systems, 36, 2024.
[SSLL23] Yiyou Sun. Zhenmei Shi, Yingyu Liang, and Yixuan Li. When and how does known class help discover unknown ones? provable understanding through spectral analysis. In International Conference on Machine Learning, pages 33014-33043. PMLR, 2023,
[SSM98] Alex Smola, Bernhard Schölkopf, and Klaus-Robert Müller. The connection between regularization operators and support vector kernels. Neural networks, 1 11(4):637-66 1998.
[SSWZ23a] Tamas Sarlos, Xingyou Song, David Woodruff, and Richard Zhang. Hardness of low rank approximation of entrywise transformed matrix products. Advances in Neural Information Processing Systems, 36, 2023.
[SSW723b] Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang. Quartic samples suffice for fourier interpolation. In FOCS, 2023.
[SWYZ21] Zhao Song, David P. Woodruff, Zheng Yu, and Lichen Zhang. Fast sketching of polynomial kernels of polynomial degree. In ICML, 2021.
[SYZ21] Zhao Song, Shuo Yang, and Ruizhe Zhang. Does preprocessing help training over- parameterized neural networks? Advances in Neural Information Processing Systems, 34, 2021.
[SYZ24] Zhao Song, Junze Yin, and Lichen Zhang. Solving attention kernel regression problem via pre-conditioner. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 208-216. PMLR, 2024.
[S7724] Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training multi-layer over-parametrized neural network subquadratic time. In ITCS, 2024.
[TBY+19] 19] Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. Transformer dissection: An unified understanding for trans- former's attention via the lens of kernel. Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan, editors, Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLL 2019, Hong Kong. China, November 3-7, 2019, pages 1343-4352.
Association for Computational Linguistics, 2019.
[Va112] Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 11 11-20, 2012.
[vL07] Ulrike von Luxburg. A tutorial spectral clustering, 2007.
[VSP+17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz. Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems (NeurIPS), 30, 2017.
17

---

[Wil18] R Ryan Williams. Faster all- shortest paths via circuit complexity. SIAM Journal on Computing. 47(5):1965-1985, 2018.
[WLK+ Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint urXiv:2006.04766 2020.
[WZP05] Liwei Wang, Yan Zhang, and Jufu Feng. On the euclidean distance of images. IEEE transactions on pattern analysis and machine intelligence, 27(8):1334-1333 2005.
[X7Z18] Chang Xiao, Peilin Zhong, and Changxi Zheng. Bourgan: generative networks with metric embeddings. Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS), pages 2275-2286, 2018.
[Zha22] Lichen Zhang. Speeding up optimizations via data structures: Faster search, sample and maintenance. PhDD thesis, Master's thesis, Carnegie Mellon University, 2022.
[ZHDK23] Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. Kdeformer: Accelerating transformers via kernel density estimation. In ICML. arXiv preprint arXiv:2302.02451, 2023.
[Zhu05a] Xiaojin Zhu. Semi-supervised learning with graphs PhD thesis, Carnegie Mellon University, language technologies institute, school of Computer Science, 2005.
[Zhu05b] Xiaojin Jerry Zhu. University of Semi-supervised learning literature survey. Technical report, Department of Computer Sciences, 2005.
[Z1.224] Shijun Zhang, Jianfeng Lu, and Hongkai Zhao. Deep network approximation: Beyond relu to diverse activation functions. Journal of Machine Learning Research, 25(35):1-
39, 2024.
[ZRG+22 Susan Zhang. Stephen Roller, Naman Goyal. Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0000 01066, 2022.
[3SZ+23] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, and Beidi Chen. H 2 Heavy-hitter oracle for efficient generative inference of large language models. In NeurIPS. arXiv preprint arXiv:2306.14048 2023.
[ZZP*21] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang. Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-seriee forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11 111111 2021.
18

---

Appendix
Contents
1
Introduction
Fast Attention and the Polynomial Method
2.1
Converse for the Polynomial Method
2.2 Weaker Polynomial Methods
3
Kernel Methods
4
Metric Transforms
5
Core Tool: Representation Theory of the Real Hyperrectangle
6 Conclusion
7 Limitations
10
8 Societal Impacts
10
9
Acknowledgments
10
A Preliminaries
21
A.I Notations
A.2 Definitions..
21
A.3 Alternate Classifications of Completely Monotone and Bernstein Functions
22
A.4 Metric Hierarchies
23
A.5 Negative Type Metrics and Fuclidean Embeddability
24
A.6 Schur's Lemma for Abelian Groups
24
A.7 Baire Category Theorem
24
A.8
Applications of Polynomial Methods
25
B Technique Overview
26
B.1
Starting Point: Eigenvalues of the Kernel Matrix of Hyperrectangle
26
B.2
Polynomial Method Converse
27
B.2.1
Exact Low Rank
27
B.2.2
Approximate Low Rank
27
B.3 Metric Transforms
28
B.4 Kernel Methods
28
Polynomial Method Converse
29
C.1 Preliminaries
29
C.2 Functions with Algebraically Zero Eigenvalues
29
19

---

C.3 Eigenvalues of Low Rank Preserving Functions
30
C.4 Bridging Eigenvalues and Finite Differences
32
C.5 Function Sums and Finite Differences
33
C.6 No Functions Other Than Polynomials Preserve Low Rank
34
C.7 Proof of Continuity
34
C.8 Comparison with Prior Work
35
D Approximate Polynomial Method Converse
36
D.I Main Approximate Result
37
D.2 Real Analytic Functions
................................
37
D.3 Lipschitz Functions
38
Transtorming Manhattan Euclidean
38
E,1 Manhattan Euclidean Transforms are Increasing
39
E,2 Manhattan to Euclidean Transforms are Bernstein
39
E.3 Manhattan Euclidean Transforms Bounded
40
Transforming Manhattan to Manhattan
F.1
Explicit Embeddings for Manhattan to Euclidean Transforms
41
F22
Manhattan Manhattan Transforms are Equivalent Manhattan to Squared- Euclidean Transforms
41
F3 Metric Transforms for Distances with Group Symmetries
42
Positive Definite Manhattan Kernels
42
G.1
Positive Definite Manhattan Kernels map Positive Reals to Positive Reals
42
G.2 Positive Definite Manhattan Kernels are Completely Monotone
42
Positive Definite Euclidean Kernels
43
I Eigenvalue of Kernels from the Hyperrectangle
43
LI Matrices with Reflectional Symmetries have Hadamard Eigenvectors
43
1.2 Eigenvalues of Kernels from the Hyperrectangle, Restated
43
Converse to Stable Rank
44
J.1 Lipschitz functions preserve stable rank
44
J.2 Fast-Growing functions do not preserve stable rank
46
20

---

Roadmap. In Section A, we define notations, and provide several basic definitions and fundamental tools. Section B, we provide several techniques used to prove the theorems. In Section C, we prove the converse to the polynomial method, proving Theorem 2.5. In Section D, we prove an approximate converse to the polynomial method, proving Theorem 2.6. In Section E, we prove condition 1 and condition 2 in Theorem 4.4 on Manhattan metric transforms are equivalent. In Section F, we prove condition 2 and condition in Theorem 4.4 are equivalent. Overall, Section E and Section together prove Theorem 4.4. In Section G, we have a proof of Theorem 3.4 about Manhattan distance kernels. In Section H, we have a new proof for the known, full classification of Euclidean distance kernels. In Section I, prove slightly different restatement of Lemma B.1. We show our results about stable rank in Jection
A Preliminaries
This section is organized as follows:
In Section A.I, we define several basic notations.
In Section A.2, provide some definitions piccewise functions, open/closed/dense sets, real analytic functions, and finite differences.
In Section A.3, we provide some previous work about the classifications of completely monotone and Bernstein function.
In Section A.4, state well-known results about metric hierarchies.
In Section A.5, we define negative metrics and euclidean embeddability.
Section A.6, we present previous work about representation theory tools.
In Section A.7, we present the Baire category theorem.
In Section A.8, we discuss some applications of polynomial methods.
A.1 Notations
For a vector x, we use |a]|| to denote the entry-wise & norm of x. We use ||>||| to denote the entry-wise & norm of x. We use || to denote the foo norm of æ. For two vectors b, we use (a, b) to denote the inner product between and b. For vector x, we use x. to denote the transpose of For any matrix A, we use A, 's to denote its eigenvalues. For any square matrix A, we use (A) to denote its determinant.
For any d 2 we define Hadamard matrix Ha E R22xx2 x2d as follows Ha=
Ha-1 Haa1
Ha-1
and
-Ha-1
Ho 1.
Often times in our proof, we may say things like "let 21. Z2d be the corners d dimensional hyperrectangle". For these statements to make sense, we must specify which corner refers to. Scale the d dimensional hyperrectangle to be an axis-aligned hypercube, and place one of the hypereube corners at the origin. Each corner then has binary number b as its coordinate bit string. We let Tb+1 refer to the original hyperrectangle corner corresponding
A.2 Definitions
Piecewise function A piecewise function function defined by multiple sub-functions, where each sub-function applies to a different interval in the domain.
Open, closed and dense set Open sets are a generalization of open intervals in the real line. In a metric space (with pre-defined distance function) open sets are the sets that, with every point P. contain all points that are sufficiently near to P (that is, all points whose distance to P is less than some value depending P).
closed set a set whose complement is an open set. A set that is closed under an operation or collection of operations is said to satisfy closure property.
21

---

A subset A of topological space X is called dense (in X) if every point r in X either belongs to A or is limit point of A; that is, the closure of A constitutes the whole set X.
The interior a subset of topological space is the union all subsets of S that are open in X.
Real Analytic Formally, function f is real analytic open set D in the real line if for any To E D one can write
f(x) Σ an - 100" = + a1 (x zo) + 02(a - zo)² + as(x zo) + ... ==0
in which the coefficients do, 01:'. are real numbers and the series is convergent to / ((x) for x in neighborhood of z0-
The following conditions are equivalent:
f is real analytic
open set D.
There is a complex analytic extension of f to open set G C C which contains D.
f is real smooth and for every compact set K C D there exists a constant C such that for every K and every non-negative integer the following bound holds Ck+
|* a (x)) S
Finite Difference A finite difference is mathematical expression of the form f(x - f(x + a).
Three basic types commonly considered: forward, backward, and central finite differences. forward difference, denoted A, [/]. of a function / a function defined as [n]f(()) f( + h)) f(z).
backward difference uses the function values at x and x - h, instead the values at x - h and x:
Vn(f(<>) f() f(x
AxIf](> h)).
Finally, the central difference is given by
(x[f((x) = f(x + h/2) - f(x - h/2) Anlf( h/2).
In this paper, we will mainly focus foward difference.
We use (x) to denote d-th difference any Rd at E For each E [d], we use to denote the i-th entry of h. For each j E [d]. the j-th finite difference can be written as the following recursive way. For j = 1, we have
A1, = f( + h2) f(x).
For j = 2, we have
A ho [f(x)) Ah. An.If((x h2) (f)x)()).
For each j E [d], we have
D Nar My [f((x) -
-1-1 hh [f](x h2) D ba [f](x).
We will frequently apply these finite differences to functions g : Idd R the form g(a) f(1a, 1)) for function f R R similar. In these cases, will abuse notation and write Ag 1)) to refer to A (a).
A.3 Alternate Classifications of Completely Monotone and Bernstein Functions
Here recall the classical Bersstein Theorem from analysis constructively classifying completely monotone (Definition 3.2) and Bernstein functions (Definition 4.3).
Proposition A.I (Chapter 14, Theorems and in [Lax02]].. For a function f I - R20- the following equivalent:
22

---

1. f is completely monotone.
2. Letting (Daf)(z) = f(x a) - for any (d1....,aa, an) non-negative we have
(-1)"
II
Da. f(x) 20
i=1
for all x O.
3. There exists a positive finite measure μ on Rz0 such that
f(x) = e du(t),
x x>0 0.
The part 2 of Proposition A.1 is essentially the definition gave for completely monotone, except that it does not assume any smoothness or even continuity a priori. The third shows that all completely monotone functions in fact mixtures of decaying exponentials. From the above one easily derives a corresponding classification of Bernstein functions. If also has 0 in its domain, then the above result applies the way, however (with the same measure y in part 3 of Proposition A. have
f(0) (R2o)
since we did require any continuity O. Proposition A.2 (Theorem 6.7 in [BCR84)), For a function f Rzo + R2o with f(0) 0, the following are equivalent:
1. f is Bernstein.
2. Letting (D)f) f(x a) for any (ai...., an) non-negative have
n Do,
(-1)"
II Do, [(x) 50 O.
3. There exists positive measure μ on R and a, b, 2 0 such that
f(x) a br / (1 (1-e-")dmpt), x> 0.
Here y must satisfy Jx, min(1, (dd((1)) < xc.
Due to the second criterion just above, Bernstein functions also sometimes called completely alternating. We remark that these results apply more generally in the setting of abelian semigroups, where the integral is taken over measure the space of positive characters. This general point of view is explained in [BCR84, Chapter 6], and applies, for instance, to the semigroup of compact subsets of I under union.
A.4 Metric Hierarchies
Here are well-known facts we will use throughout our proof:
Lemma A.3. For any n points TT, in Es, there exist points y1.-.-yo such that ||ar; - x.yl1 llys yj lI and y1... Yo are a subset of corners of a dimensional hyperrectangle for some d.
Proof. This follows from the equivalence the cut cone and e distance (Theorem 4.2.2 in (DL09]).
Lemma A.A. The squared Fuclidean distance between points the corners of a hyperrectangle isometrically embeds into Manhattan distance.
23

---

Proof. This follows from the Pythagorean theorem.
Lemma A.5. Manhattan distances embed isometrically into squared Euclidean distances.
Proof. This follows from Corollary 6.1.4 and Lemma 6.1.7 in [DL09].
A.5 Negative Type Metrics and Euclidean Embeddability
We now present a criterion by Schoenberg [Sch35] on when metric isometrically embeddable into squared Euclidean distances?.
Definition A.6 (negative type). matrix iff x: Dæ S for all x: x.1.1
Lemma A.7 (Schoenberg [Sch35]). Consider æ1,... ,,,.,,,d7 Tn where da.j is the distance between and F, Let D be an n by matrix where Dag = c. The distances di.j are isometrically embeddable into Euclidean space iff the matrix D is negative type.
We note that if D happens to have the all ones vector 1 as an eigenvector, we have a simpler criterion for testing if D is negative type:
Lemma A.8 (Schoenberg Variant). Consider T1, EI where d,, is the distance between 2; and J... Let D be an n by n matrix where Di.j = d².5-
If the all ones vector is an eigenvector of D, then the di,j are isometrically embeddable into Euclidean space iff every eigenvalue of D, excluding the eigenvalue correseponding to the all ones vector, is non-positive.
Proof. Lemma A.8 follows from Lemma A.7 and the fact that every symmetric matrix has an orthonormal set of eigenvectors.
diy is isometrically embeddable into Euclidean space, we can find an explicit embedding:
Lemma A.9. Consider I1.... In where dug is the distance between x; and xz. Let D be the matrix where Di, = d, Let II be the projection matrix off the all ones vector, i.e, II can be expressed explicitly as 1 - J/n, where J is the all-ones matrix, and I is identity matrix.
Let M - IT
-/n are such that 119--1 dr,j and Ei= then M.,- (yi, Us). Moreover, if M = U U for some U, then the columns of U are embedding of 21.... Zn. into Euclidean space.
,.
This follows from Eq. 2 in [Cri88]. longer exposition of the link between distance matrices and inner product matrices can be found in [Cri88).
A.6 Schur's Lemma for Abelian Groups
We present Schur's lemma for Abelian groups G. Schur's lemma is of the comnertones of representation theory [EGH+ 11].
Lemma A.10 (Schur's lemma for Abelian groups). IfG is a finite Abelian group of n matrices under multiplication, and M is an n X diagonalizable matrix satisfying Mg gM, M, for all E G, then there exists a set of linearly independent vectors VI.... Un that are eigenvectors of M and all E G. In other words, M and G are simultaneously diagonalizable.
Schur's Lemma will be useful in proving key result about representation theory of the real hyperrectangle, or Lemma B.I.
A.7 Baire Category Theorem
The Baire category theorem (BCT) is an important result in general topology and functional analysis.
Baire space is topological space with the property that for each countable collection of open dense sets ) their intersection NneN U,,i dense.
We note that Schoenberg's 's criteria has beautiful proof, which find direction of in [Par12].

---

Theorem A.11 (Baire category theorem [Bai99]). Every complete pseudometric space is Baire
space. Every locally compact Hausdorff space is a Baire space.
A.8 Applications of Polynomial Methods
Attention Computation: Question 2.3 is also important to the theory of polynomial kernels. A common computational task which arises when training transformers is to calculate the 'self attention' [VSP+17] Recently, [ZHDK23, AS23] define formal math computation problem for this attention mechanism. Formally, in this task, we are given three matrices Q, K, V RRadd where n >> d and we would like to compute (QK') y V where J R + IR is a non-linear function that we apply entry-wise to the matrix AB E I=**", then we multiply the result on the right by V. In many applications, f is the soft-max function, which can be mathematically described as follows (see [ZHDK23, AS23J):
(QKTY == D- exp(QKT), where D = diag(exp(QK )1n)
Here exp() is an entry-wise function that exp(QK exp(((X )a,)) for all i.j E [m] x [n]. D E R= is diagonal matrix, 1, is vector that all entries are ones.
Naively evaluating (QKT)² V takes time (n²d) (without using fast matrix multiplication).
However, if we can quickly find matrices Q, K E R=n for some d < such that (QKT)²-
x KTT then can evaluate it more quickly by first computing K V and then computing Q x (KT V), for a total running time of just (ndd)).
Since QKT can be any rank matrix, and x RT has rank most d, follows that an upper bound on the best we can achieve is the maximum, over all matrices M of rank d. of rank(M Question 2.3 asks whether it is possible to achieve d' for functions like the soft-max function which are not a polynomial. If not, then we can only hope to carry out this plan of attack we can find a low-degree polynomial approximation to our function f-
Algorithm Design:
For one example of polynomial method in algorithm design, consider the fastest known algorithm for batch Hamming Nearest Neighbor Search due Alman, Chan, and Williams [ACW16] this problem, one is given as input 2n vectors
F1,..., In V1. .i....... ..... Un E 10,
for d' = (log n), and a threshold value t E {0, I,... . d}. and one wants to find a pair (i,5) e [n] x [n] such that the Hamming distance between I; and My is at most t. [ACW16] takes algebraic approach to this problem, by first considering the matrix M E R=*x where Mr, is the Hamming distance between 2; and V/- One see that rank(M) < 2d, and one could use fast matrix multiplication to quickly compute all the entries of M. However, since M itself has n² entries, this could not improve much on the straightforward (n² log rı) time algorithm. They instead take the following approach.
First, pick a parameter g = n for a constant 8 0, and a function f: R - TR such that f(x) > g² for all x E {0, 1,..., t). and f() E [o. 1] for all i E [t+1,t+2 2...+,,.. d]. [ACW16] use Chebyshev polynomials to construct such an which is a low-degree polynomial, so that the matrix M has low rank by Fact 2.1. Next, let S./g S be a partition of [n] into n/g groups of size g, and consider
the matrix F E R x given by
Fo,b Σ M/ JES.
'The matrices Q, K and correspond to the query, key, and value matrices, respectively, when training transformers in NLP applications. For more background, we refer the reader to [VSP* 17, DCLTI8, RNS 18. RWC+ 19, BMR KKL19, CLD*20 20, FZS21, WLK+ CDW ZSZ 23, LWD+233. The n >> d is reasonable assumption in long sequence model problems, since n the length of documents and is size of each word embedding.
9We first construct the matrices X R=x2d and Y E 22dxn such that M X x Y. We can then compute the product X x Y in Ō(n²) time using fast rectangular matrix multiplication [Cop82, Wil18] as long as d < ne The reason of obtaining 2d (instead of d) is due to the construction of [ACW16].
25

---

It is not hard to verify that rank < rank(M Fa, is larger than g if and only if there an (i.j) Sa Sp such that the Hamming distance between n; and yj is at most I.
Moreover, by the way f was defined, an entry
There is trade-off between the parameter ó and the degree of f. and hence the rank of F. [ACW16] balance this trade-off to yield a matrix F of low rank 10 and dimensions n 1-6 n for some > 0. Since F' now has subquadratic total number of entries, fast matrix multiplication can be used to compute all its entries and solve the problem, in roughly O 26) time.
B Technique Overview
In this section, we describe the techniques used to prove our main theorems. In Section B.I, we introduce the eigenvalue properties of kernel matrices derived from hyperrectangles. In Section B.2, we introduce the techniques used to prove Theorem 2.5 and 2.6. In Section B.3, we introduce techniques used to prove Theorem 4.4. In Section B.4, introduce techniques used to prove Theorem 3.4.
B.1 Starting Point: Eigenvalues of the Kernel Matrix of a Hyperrectangle
All of our proofs start by using simple but powerful technique. This technique computes eigenvectors and eigenvalues of the kernel matrix for any set of points which arise as the vertices of a hyperrectangle (d-dimensional rectangle). After describing the technique in more detail, we will explain how it leads to our applications by demonstrating why these matrices and their eigenvalues are relevant to the three main questions stated in Section 1.
The eigenvectors of the family of matrices we define shortly will come from columns of Walsh- Hadamard matrices. For a positive integer d, let u1.... 022a E {0, 1}d d be the enumeration of all n-bit vectors in lexicographical order. The Walsh-Hadammrd matrix Ha is the 2d x 2d matrix defined by (1, v2) = (-1) (1),5)), The technique is as follows:
Lemma B.1 (Eigenvalue of Manhattan Kernels, informal version of Lemma 1.2), For a vector E IR let p1,.... P2e E TR denote the vertices (#a/) /2, at...//...... ",,....,,a,/.. =aaa2)
of a hyperrectangle in lexicographical order. For any f R + R, let D be the 2d by 2 matrix given by Dig f(lp. - -P;ll). Then, the columns of the Hadamard matrix Hn are the eigenvectors of D.
For i (24), let B(i) E 10, 4 be the binary representation i. Then, the eigenvalue corresponding column of H, is: >3- = E
f((b, a))-
We will see shortly that this expression for the eigenvalue X; can also be rewritten in terms of integrals and derivatives of the function f. allowing us to use analytic techniques when computing or applying these eigenvalues.
Lemma B.1 can be proved using a direct calculation, although its inspiration comes from repre- sentation theory. The matrix 1) has the property that: for any permutation matrix a corresponding to a reflection about one of the hyperrectangle's 's axes, we have o = Do. Schur's lemma from representation theory (see Lemma 10 below) states that D and all a in the reflectional symmetry group of the hyperrectangle have a common set of cigenvectors. It is not hard to verify that the only common set of eigenvectors for all the columns of the Hadamard matrix, and thus D must have the columns of H. as its eigenvectors.
Our analysis of eigenvalues in Lemma B.1 is closely related to the Fourier analysis of the Boolean hypercube, which has been studied for decades in computer science theory [O'D14]. Fourier analysis of the Boolean hypercube can be seen as instance of our technique, by setting a to be the all ones vector in d dimensions. It is important in some of our proofs that a is not the all ones vector: kernel matrices from a hyperrectangle with varying side lengths have eigenvectors that approximate finite differences. This is key for our proofs of Theorem 4.4 and 3.4. See Section E.2 for details.
We next give overview of how we use Lemma B. to derive our three applications. We focus on explaining how the matrices described by Lemma B.1 and their eigenvalues arise in each setting.
Thhee pick rank ~ 0.1 in order to apply fast rectangular matrix multiplication as in footnote 9, although different applications of the polynomial method have aimed for different target ranks.
26

---

B.2 Polynomial Method Converse
B.2.1 Exact Low Rank
We begin by explaining our techniques for the exact low rank case (Theorem 2.5). This theorem seems hard to prove for a number of reasons.
First, we assumee very little structure on f: in particular, we do not asssume f is differentiable or even continuous. Rather, we assume much weaker condition than continuity: indeed, Theorem 2.5 holds for all piecewise continuous functions f. This is large space of functions, and in particular covers all non-differentiable continuous functions including oddities such as the everywhere-contmnng and wwwhere-differentabbe Weirstrauss function.
Second, prove matrix M is low rank, one might typically compute either the determinant or an eigenvalue and show they must be O. However, explicit formulas for determinants and eigenvalues can often be complicated, large algebraic expressions in terms of and elements of M. We overcome this barrier by selecting special family of matrices M whose eigenvalues can be expressed as simple sum. This family of matrices restrictive enough to have a set of common eigenvectors (and thus easily computable cigenvalues), but expansive enough to express all finite differences of f in terms of these eigenvalues. Our proof proceeds as follows.
Step 1: We begin by showing that if f TR - preserves low-rank n x n matrices, and does not have any essential discontunuities of the first kind, then I must be continuous. We do this by constructing a family of n x matrices of rank at most 5 such that, for any jump, point, removeable, or soeettial-f--eeood--iiii discontinuity that the function f has, one can pick a corresponding matrix from our family that f maps to a full-rank matrix. In other words, such functions f are very far from preserving n low-rank matrices.
Step 2:
We next show that if a continuous function f preserves low-rank n X n matrices, then must be a piecewise polynomial function. We will do this by considering the family of n kemel matrices of a hyperrectangle, from Section B. If f preserves low-rank matrices, then it must, in particular, map all these matrices to matrices which do not have full rank.
For any fixed i, we will show that the d-th order finite difference of f at point x can be written as linear combination of the i-th eigenvalue A, of number of different matrices in our family (see Lemma B. for definition of A; and our kernel matrices). Hence, if X is for all of the above- mentioned kernel matrices, this will imply that the d-th order finite difference of f is 0 at every point I, and thus f is a polynomial of degree at most d.
Although we are guaranteed that one of the eigenvalues of each kernel matrix is O, we are not guaranteed that there a fixed such that it always the i-th eigenvalue which
In order to address this, we apply the Baire Category Theorem from topology to the zero-sets of X; for each fixed i. Roughly, this theorem allows us show that for all R (except for whose intersection with any finite interval is finite), one can manipulate which matrices determine the finite difference of f the details, this implies that f is a piecewise polynomial.
ensure that they all have the same eigenvalue X equal to O. Working through
Step 3: Next, show that the function f must be exactly a polynomial. From step that f is piecewise polynomial. We then use a series of algebraic manipulations, and the fact that a linear combination of X, from different matrices gives the finite difference of f. to show that each d-th finite difference of / evaluated at any point for any gap is O. This implies that f is a polynomial, finishing our proof.
know
B.2.2 Approximate Low Rank
Our proof of Theorem 2.6 is similar to the exact setting (Theorem 2.5). The main new technical difficulty which arises is that we must more carefully bound the finite differences in terms of the eigenvalues; in the previous proof, we could assume one of the eigenvalues is 0 and so many terms cancelled out. We omit further details here the interest of space, but refer the reader to Section D for more details.
27

---

B.3 Metric Transforms
At the onset, Theorem 4.4 seemed difficult to prove for a number of reasons.
It is known, and not hard to show, that any Bernstein function transforms squared Fuclidean distances to squared Euclidean distances [BCR84]. was also known that Manhattan distances isometrically embed into squared Euclidean distances. Thus Theorem 4.4 immediately implies that Bernstein functions are equivalent functions that transform squared Euclidean to squared Euclidean distances. This equivalence is Schoenberg's 's foundational theorem Euclidean metric transforms [Sch37], which is considered difficult to prove from scratch.
Schoenberg's s proof uses multivariable calculus and complex analysis in Hilbert space, which has natural Euclidean distance structure; Manhattan distances not have such structure, so we cannot proceed in this way prove Theorem 4.4. Our proof takes an entirely new approach, and our result stronger than Schoenberg's.
Moreover, we note that most squared Euclidean distances are not Manhattan distances: indeed, most squared Euclidean distances are not even metries. Thus, it was highly conceivable before our work that non-Bernstein functions could transform Manhattan distances to squared Euclidean distances. Our work rules this possibility out. It was also unclear prior our work why functions transforming Manhattan to Manhattan, and functions transforming Manhattan to squared Euclidean, should be the same set of functions.
Notably, we do not assume any kind of structure on metric transforms f: we do not assume f is bounded, continuous, Fourier-transformable and so forth. Thus, theorem applies any conceivable function with no underlying structure assumed at all.
First, show that a function transforms Manhattan distances to squared Euclidean distances, if and only if f applied entrywise to our kernel matrices from hyperrectangles (see Lemma B.1 for how these defined) always results in matrix whose eigenvalues are all negative except for Å1- Here X; is defined as in Lemma B.1. This follows from the well-known fact that all Manhattan distances can be isometrically embedded into Manhattan distances between points on a hyperrectangle, combined with a criterion of Schoenberg [Sch35] on when a given set of (R) distances be realized pairwise squared Euclidean distances from points.
Step 1:
Step 2: Next, we show that only Bernstein functions transform Manhattan distances to squared Euclidean distances. We do this by showing the d-th order finite difference of evaluated x, be written as (-1)d times the limit of a sequence of eigenvalues of well-chosen kernel matrices from hyperrectangles. We can bound this limit using step 1, show that if transforms Manhattan distances to squared Euclidean distances, then the d-th order finite difference for f have the opposite sign as ( (-1)d. This property implies that f is Bernstein, even without assuming priori that is bounded or continuous.
Step 3: We will then show that any function that transforms Manhattan distance to squared Eu- clidean distance, must transform Manhattan distances to Manhattan distances.
We first show that f transforms Manhattan distances to squared Euclidean distances if and only transforms Manhattan distances from hyperrectangle corners to squared Euclidean distances. We then find the explicit embedding of these squared Euclidean distances via classic idea of Schoenberg [Sch35], which will reveal that these transformed distances can be embedded as squared Euclidean distances from corners a different, higher dimensional hyperrectangle. Squared Eu- clidean distances from corners of a hyperrectangle are isometric to Manhattan distances, by the Pythagorean theorem.
B.4 Kernel Methods
Theorem 3.4 represents a non-trivial advance kernel theory for the following reason:
One of the fundamental results of kernel methods is classification of all Fuclidean kernels. From this, one can deduce that function is a squared Fuclidean kernel if and only if completely monotone function. Since Manhattan distances are measure-zero set of squared Euclidean distances,
28

---

it is clear that completely monotone functions are Manhattan kernels, but it is not at all clear that all Manhattan kernels should be completely monotone.
The proof steps for kernel methods are very similar to those for metric transforms. The reason is that there is known connection between matrices of squared Euclidean distances between pairs of points, and matrices of inner products between pairs of points.
The main difference between the proof of Theorem 3,4 on kernels and the proof of Theorem 4.4 on metric transforms (whose steps are listed Section B.3) is that in Step of our proof on kernels, we show that function is Manhattan distance kernel if and only if f applied entrywise to kernel matrices from hyperrectangles always results matrix whose eigenvalues are all non-negative. We propagate this change through the proof steps accordingly.
C Polynomial Method Converse
The major goal of this section is to prove Theorem C.11, the formal restatement of Theorem 2.5. This section is organized as follows
In Section C.I, we restate some preliminaries about kernel matrices from real hyperrectan- gles. We define matrices M (a), M ( (a), and eigenvalues X (a).
In Section C.2, we prove that low degree polynomials are the only functions such that M (a) has an eigenvalue that is the zero function in terms of E Tdd
In Section C.3, we show that for any function that preserves low rank, one eigenvalue of M (a) must be zero in terms of
In Section C.4, provide algebraic computation, which is key step for equating sum eigenvalues with the formula for finite differences.
In Section C.5, we formally relate a key sum of f evaluated at various points, with the finite differences of f-
In Section C.6, we prove that only low-degree polynomials preserve low rank. This proves the main result of this section, Theorem C.11, 1, which is formal restatement of Theorem 2.5.
In Section C.7, we show a large class of discontinuous functions do not preserve low-rank matrices.
C.1 Preliminaries
We start by defining the matrix (a) from the real hyperrectangle, and its eigenvalues.
2d 1} - Definition C.1 (Matrix (a)). Consider mapping B {00, .....2
10, 1)dd corresponding
to the conversion of integers into d-digit binary strings, which we interpret as d dimensional vectors. For any fixed vector Rd. we define matrix (aa)
M(a)ij (a, B(i j])).
Definition C.2 (Figenvalues of M(a)). For each matrix Ma) E Raxn, we established previ- ously that ((M( E Raxn has eigenvectors equal to the Hadamard matrix columns, and the corresponding eigenvalues are:
Σ (-1)(8(0)))) f((b,a)) bE10.11
We also give the following definition:
Definition C.3 (Real hyperrectangle). The d-dimensional real hyperrectangle parameterized by d variables .1....0g is the convex hull of the 2 points {#0.//2 /t../ ..... an/2).
C.2 Functions with Algebraically Zero Eigenvalues
The goal of this section is prove Lemma C.4.
29

---

Lemma C.4 (Only polynomials have a zero cigenvalue). For any function f. any n that is power 2f 2, and == log + 1: find M RR + gnx=" and X _2 - IR satisfying:
1. M(a) has rank I d for all Rd
2. (a).... (.(a) is the full set of eigenvalues of f(M())) for all E Rdd.
3. If there exists i E [n] such that X (a) = 0 for all E R2, then J is degree S log n + 1 polynomial.
Proof. We note that for any & > 0,
(-1)(B())))
Σ
(-1)110: 2/ cb) = Σ (-1)lbbl f((( + eb, 1)
(1)
bE(0,1)
bE{0,1)
by the following computation:
()
Σ bEf0,1)
(-1)llblls X (a +b)
(Σ Σ (-1)(B())bb) f((b2, a + ebi))
(B)))
Σ
(-1)lbbill
b (0.1))
(2
(-1)2(B(i).))
Σ (-1)1101h f((( + eb, 1))
bE(D,13
= Σ (-1)11011 f((a + cb, 1)
(0
where the first equality follows from the definition of X and the second equality follows from Lemma C.9.
follows that if X/ 0, then
Σ
(-1)llblb f((a + eb, 1) =0
be [0,1)4
for all and a. By Lemma 10. the above equation implies that A 1)) 0 for all e. If all n order finite differences are equal to 0 at a, then the tt derivative of at a exists and is also equal to O.
Therefore, f at most a degree d polynomial as desired. Thus, we complete the proof.
We conjecture that the above lemma is true without requiring a power of 2, but it is necessary for our other results.
C.3 Eigenvalues of Low Rank Preserving Functions
The goal of this section is to prove Lemma C.5.
Lemma C.5 (One Eigenvalue is identically zero). If is a power of and given:
1. A function f TR RR with no essential discontimuities of the first type
2. A function M Rd Raxx, mapping = [log n dimensional vectors to n dimensional matrices.
3. A set of n functions N.N X1, such that each X Rd B, and the full set of eigenvalues of f applied entry-wise M (a) for all Rd
is
30

---

Then if f transforms matrices M (a) to rank < for all E R then there exists [n] where function X O.
Proof. Lemma C.8 says that if f preserves low rank and has no essential discontinuities the first type, then it is piecewise polynomial. We will prove that if it preserves low rank and is piecewise polynomial, must be polynomial.
We consider the family of matrices (J - M(a),, where J E R is the all ones matrix. Note that (a) has rank at most + 1 and one of the eigenvectors all ones vector. Thus, matrices of the form J M (a) have rank most + 1.
Suppose otherwise, that preserves low rank and is piecewise polynomial but not polynomial. Without loss of generality, we can assume that f(x) = Pi(z) on [r, s] and f(z) P2(x) on [s, for some r
for some polynomials P1 + P2.
There exists an open set X C R and an open set Y C IRd such that x E |r; s) and x + (y. a) is {0, 1]d. X,Y can be attained by choosing to
in [s, t] for all æ E X, y E Y, and non-zero < and and Y to be the set of y with < Vi < 2e, for any O < c (t (2d) for all S j
be the set of satisfying
We use our eigenvalue computation in Definition C.2 to see that:
x(+J+M(w)) (z) +
Σ
(-1) P2(x (y. a)).
OE (0.1)
Here, B(i) is the d dimensional binary representation of [n] in Eq. (2).
preserves low rank, then for each x X and for each y Y, there exists an i such that the RHS of Eq. (2) identically zero. Since X Y is an open set in d there exists i such that the roots of RHS Eq. has non-zero measure. Since this RHS is multivariate polynomial x and yı for 1 < k < d, and since the only multivariate polynomial with non-zero measure is O everywhere, then X (IJJ M(y)) must be 0 for all Rdd and y Rd for chosen value of i, and thus for this value X (M)) = 0 for all
We conjecture that Lemma C.5 is true for all n, not just powers of 2. However, that is not necessary for our other results.
The proof above holds assuming Lemma C.8. We now build up series of Lemmas leading up to that point. First, we need a technical lemma.
Lemma C.6 (Locally Zero Eigenvalue Implies Vanishing tth Derivative). Let be a power of 2 and d = [log n + 1. If there exists i E [n] such that. for fixed E Rd we have
A(aa h1) =0
for all h E IRd with || < Ha for some Ha then Aifi((a, 1)) 0 for all || Ha and thus ((d) ((a, 1)) exists and is equal to
Proof. For fixed a, d, and i, we know by Eq. (1) and Lemma C.10 that (g can be written as linear combination of ΣtEK cedi(a + hg) for some E RlKI and hg Hg for all Lemma C.6 follows.
Lemma C.7. Let Ti, Ta C Rd be closed sets such that
Usetn Rd
Let R3 be the interior of T,. Then when taking the union of the projections of R. onto the line e- la Rd for E the result is the entire line except set Q of points, where Q intersected with any finite interval contains only finitely many points.
Proof. First, we prove that this holds when d and T; are the closure of open sets. We will reduce the general case to the case in the previous sentence.
31

---

One-dimensional case If T, is the closure of open sets in one dimension, then it is the union of disjoint closed sets where each finite interval on the real line contains only finitely many closed sets contained in T. We can assume without loss of generality that the interiors of T; are disjoint. In this case, the set T; R3 is the union (over all i) of endpoints of closed intervals in 7: It follows that T, \ R, is set Q of points such that every finite interval on the real line contains only finitely many elements of Q, as desired.
Reduction to one-dimensional case. We will reduce to the case where each T₃ is the closure of its interior. Once we have this, we can project T; and R2 onto the line l c 1a, c E IR) and thus reduce to the one dimensional case.
First, we show that all points q of the form (c, (,,,,...c) E Rd that are not in the union of R., must be on the boundary of some Rg This will prove that we do not lose any generality by considering the case when T; is the closure of its interior Rg.
If not, then there is some open set S containing that avoids all R, so now S is covered by one of the Ug- := T, R4 The Ug are all closed and have empty interior, so their complements V, are all open and dense since the U, cover S.
Since the U2 cover S, the intersection of the V, must be empty. However this contradicts the Baire Category theorem (Theorem A.11), which states that the intersection sets is also open and dense (and in particular nonempty). This means that must be on the boundary of some R2 and thus we have proven that we can reduce to the case when T is the closure of its interior R4.
family of open and dense
Reduction to the one dimensional case. Since we only need to concern with the case where Ti is the closure of its interior R. this means each point in T; R2 is the limit of sequence of points in R2 for each i. Therefore, the projection of each point T2 R2 is the limit of a sequence of points in the projection of R; and thus the projection of T; onto the line (c, ....... c) E Rd is contained in the closure of the projection of Rg This reduces the problem to the one dimensional case where each T; the closure of its interior.
Lemma C.8 (Piecewise Polynomial). If preserves low rank for all n x n matrices where n is any power 2, and has no essential discontinuities of the first type, then f must be piecewise polynomial.
Since f preserves low rank, we know that for any there exists i E [n]] such that (MM 0. By Lemma C.13, we know that must be continuous. Therefore, the T. of where (M)(()) must satisfy
UsE|n] S; = Rdd
Because f is continuous, X is continuous for all i, and so each T; is closed. Let R2 be the interior of each T.. We know by Lemma C.6 that for each point a' in RG, we know that (( 1)) 0. By Lemma C.7, this implies (x) 0 for all intersection with any finite interval is finite. This implies that f is piecewise polynomial.
\ Q, where Q C has the property that its
C.4 Bridging Eigenvalues and Finite Differences
The goal of this section is to prove Lemma C.9, key lemma which is used to relate eigenvalues and finite differences.
Lemma C.9 (Rewriting the sum).
Σ
(-1)1bii
Σ (-1)(B(0)bb)) a(by,, ebz))
b 10.10
= (B1)
Σ
(-1)llba. f((a + eb, 1))
bE(0,1)
where and b are d-dimensional vectors.
32

---

Proof. First, we can show: If by is d dimensional vector with any Os in its vector notation, we know
Σ (-1)llblll 5( <b,)) 0
for any 6, and any constant dimensional vector The reason is if b2 has any 0's in its vector notation, then flipping the corresponding bit in d1 causes (-1)l16rl to change sign, while leaving (b2, a + c unchanged.
Now, we know that:
Σ 11110.134
(-1)1bbl
Σ b2E(U.13"
(-1) s((b2, eb1))
Σ (-1)(B(0),b)
Σ (-1)llbali f((b,,, a + ebi))
10,10
11E(0.132
= (-1)(1((),)
Σ (-1)llblll f((1, a +(11))+bb1))
(0,10
where the first equality follows by rearranging sums, and the second equality follows from Eq. (3). This completes the proof.
C.5 Function Sums and Finite Differences
The goal of this section is to prove Lemma C.10.
Lemma C.10 (Function Sums and Finite Differences). Part 1. Suppose the thh derivative of f.
denoted as f(d), is continuous. Then, we huve
lim 800
Σ (-1)1ibl -((a 1)) ((a) 1)). DE(O,1)
Part 2. Suppose (=) is the d-th finite difference of function then we have
Σ (-1) I((a + eb, 17) A2 17).
bE bE(0.11
Proof. We have:
Σ (-1)lbb f((a + eb, 1)) = (-1)) (
f(la + (bb eb,1))
be(0,114
==0
(-1)) dd) ==0
(
[((a, 1) + se)
((() ((a + 1))dz
(4)
p.g" AfM 1))
where the first and second equality follow from grouping b by the number ones it has, which we denote as 8, the third step follows from the fundamental theorem of calculus, and the last step follows from definition of finite difference.
In addition, we note that the above calculation is independent of i.
33

---

Thus:
lim d
Σ (-1)llelh f((a + tb, 1b)
c+0
bE(0,1
-o Jo ... (1a v, 1))dr1 daa
lime c-0
= ((a 1))
where the first equality follows from Eq. (4) and the last equality follows from the continuity of f(a). This completes the proof of Lemma C.10.
C.6 No Functions Other Than Polynomials Preserve Low Rank
In this section, we prove main result Theorem C.11 using Lemma C.4 and Lemma C.5.
Theorem C.11 (Formal statement of Theorem 2.5). Suppose the function f :R + E does have any essential discontinuities of the first kind. For any positive integer n 2 2, the function J preserves low rank matrices and only if polynomial of degree less than [logg(n)]
Proof. First, prove it for powers of 2, and then we generalize to all
For now, suppose a power of Suppose f is function without essential discontinuities of the first type. By Lemma C.4, we can find M _ + gaxx and X glogg+t1 n+1 + IR such that the image of M has rank < logn + 1, and {2 (a)))) is the full set of eigenvalues of M (a). Further, if there exists in] with function X (a) = 0 for all a, then f degree d S log n polynomial.
Now, suppose that f is function that transforms all rank log n + matrices to rank < n matrices. Then it must transform all matrices (a) to rank < n matrices. By Lemma C.5, it must follow that
X = 0 for some i. However, we just established via Lemma C.4 that X = 0, then f a degree d < log n + 1 polynomial. This completes the proof of Theorem C.11 if is power 2f
The statement for all follows directly from the statement for n power of 2. This because of the fact from linear algebra that if an N x N matrix M has full rank, then for any fixed n S N, there exists an minors.) Suppose n is not power of 2, and let 2 be the smallest power of 2 bigger than n. If is not a low-degree polynomial, our work as-stated proves that there exists low rank 2d x 2d matrix M where M is full rank. By the previous, there exists an x minor M, of M (with low rank, since rank less than that of M) where M is full rank. Therefore, f cannot preserve low rank matrices of dimension n X n, if f is not low degree polynomial.
minor of M with full rank. (This follows, for instance, from expansion by
C.7 Proof of Continuity
The goal of this section is to prove the following lemma, which shows that a large class of functions f: IR + do not preserve low-rank matrices.
Lemma C.12. Suppose f R - I has any point R such that limg fx) exists and f(c) + lim f(x). Then, f does not preserve low-rank matrices. The same is true with 'ct" replaced by 'c='.
Lemma C.12 will follow from Lemma C.15, which we now build up to and prove.
Lemma C.13. Suppose that f - TR satisfies: lim fxx + f()). Then, for any positive integer n, there is a rank-2 matrix M Raxn such that M has full rank.
Proof. Let a = f(0) and b lim f(x). By assumption, * b. We define the n x n matrix A as follows
A = Sa ifi=
otherwise.
34

---

The definition of b means that, for all c > O, there is a >> 0 such that if x E R satisfies < | < 5, then f(z) bl Let us pick > 0 to be sufficiently small that
0.1
0 <<s n1 nl max [b], bb c1,16 =1}n-I det(A),
and let 8 > 0 be the corresponding value.
Let M (é j). We can see that (a) 2.
From assumption, we have
a Mr = {e cb
i;
otherwise.
We can upper bound
n [de) - del(A)) = Σ sgn(o) II
12
M L,a,
Σ sgn(a) II
oES,
oES
M dES
II
Ai.o.
10
F=1
1=1
Σ
e (maax(a] [b], 1b t1, -|))-
dESp
S nl e. n- (max[la), (|], 16], 16 c). 1b + cl})
where the first step follows from definition of matrix determinant.
Then we bound
det(M²) det(A) + det(A det(A)
det( A) /det(M/) det(A))
det(A) (A) - 0.1 det(A)
0.9 det(A)
> 0.
By picking a matrix M whose entries are all nonnegative, we can extend the same idea to functions f where only one side of lim, (x) must exist:
Lemma C.14. Suppose that f R -> R satisfies: lim f(x) F f(0). Then, for any positive integer there is rank-4 matrix M E gaxa such that M has full rank.
Proof. The matrix we use is Ma, é (i j-?, which has rank(M) = 4. We then proceed exactly in Lemma C.13.
Lemma C.15. Suppose that f R + R and e E IR satisfy: lim f(x) + f(). Then, for any posilive integer n, there is matrix M E Ruxn rank at most such that M has full rank.
Proof. The matrix we use is Mrj (i= 2 + c, which has rank(M) S 5. Again, proceed as in Lemma C.13.
C.8
Comparison with Prior Work
The work of [GKR17] classifies what functions transform low rank matrices into low rank matrices. They show:
Theorem C.16 (Theorem B [GKRI7]. For integers 2 2,1 S k n 1, and S S n.
suppose f has l derivatives. Then the following are equivalent:
35

---

1. f transforms rank PSD by n matrices into matrices whose rank is upper bounded by k.
2. f is a polynomial Et= ayxh for some Oe E .R and some in E N such that
Σ
+1+1- 1-1 Sk
Moreover, i S n don't need the assumption that has derivatives.
This is near-full classification functions that transform low rank matrices into low rank matrices, with few holes: first, the primary piece of the theorem requires k-fold differentiability of f. something that doesn't 't hold true for commonly used functions such as the ReI.U function. The part of the thcorem which doesn't require k-fold differentiability forces in [GKRI7], [7], these existing techniques are fundamentally incapable of extending to the settings when 2, n 1.
3. As discussed
In contrast to Theorem C.16, our Theorem C. uses very different techniques, and addresses the case where k: The consequence of extending to = n is that we have less control over our results primarily hold for 1 = lg n + whereas Theorem C.16 applies for more general 1. Additionally, our result is not exact: we show that if / preserves low rank, then f must be polynomial, but we only bound the degree of this polynomial up factor of 2, whereas theorem C.16 has tighter control over what kind of polynomial f is. Thus, Theorem 16 is tighter, but their methods are fundamentally unable without assuming k-fold differentiability. Our result
when f is not required to be differentiable, which is not covered by Theorem C.16.
handle the case when k is able to handle the k = 1 case, at the expense of tight bounds on the polynomial degree of f and at the expense of requiring that Ig
D Approximate Polynomial Method Converse
In this section, we generalize the proof in Section C from exact to approximate here.
In Section C, we claim that if function, when applied termwise, transforms low rank matrix to a low rank matrix, then it must be low degree polynomial. We will define function that approximately preserves low rank, and then prove that a function approximately preserves low rank, then its th order finite differences must be bounded in two settings: when f is analytic, and when f is Lipschitz.
Definition D.1. Let f RR-Raadd 5 O. We say f d-approximately preserves low rank matrices if. for every matrix M E [R=xn with (ank(M) < log n, the matrix f(M) has at least one eigenvalue in (-8/n, 8/m).
is not hard to show the following fact,
Fact D.2. For a fixed vector a E R2,, let matrix M(a) E Ruxn defined as Definition C. Let f: IR + R,, then have
max (aMM) = Σ f((a,b))
RE(d]
be (0,1)
Proof. By definition of eigenvalue of matrix M (a). we have
max
(a)(
Σ I))(
Σ [((ab)))
iE|d
DE(0.1)
DE(0,13
where the second step follows from f is positive function.
On the other hand, we also know there is eigenvalue is equal to Eoe [((a,b) b)). Thus,
max (M(M)))) 2 Σ f((a, b)).
*E|d
60
36

---

D.1 Main Approximate Result
Let E 2 a Rd, ha E RR n 24.
Theorem D.3. Let log n. Lei (0, 1) denote some sufficiently small purameter. Let function
satisfy:
min [M(M)
I 8/n
(5)
maxie[m] D (M)
for all rank d matrices M. Let Ka Ebe(o.1) f((a, b)).
Part If is real analytic, there exists Ha such that for all h Ha, we have
A 1)) S 8Ka
Part 2. If f is an U-Lipschitr,functinnn then for all h 2 0, we have
Alf 1)) - 8Ka hLdn.
Proof.
We will consider two regimes separately:
Not assuming Lipschitz (Lemma D.4).
Assuming f (Lipschitz D.5).
D.2 Real Analytic Functions
Lemma D.4 (real analytic functions with no Lipschitz assumption, part Theorem D.3), We have
lim Ai 1)) s ōK.. h
Proof. Let h By Lemma C.10
Σ (-1) [((a+ +eb, A( 1)). (E(0.1)
By proof of Lemma C.4, we have
Σ (-1)l101),
f((a + 1) (-1)(B(0..)
Σ (-1)1101 2/(a + eb)
bE (0.11a
[0.1)
Let us pick i" E [d] to be the index that XL. (a) is the smallest eigenvalue for matrix (a). Choose Ha to be such that Xf, (M(a + e'b)) 5, for all g' Ha.
Thus, we have
--
Σ
(-1)llblt (f-
6E(0.1]
< 24 (a)
< Kg5/n
8Ka
where the second step follows from the fact that H, is chosen so that N, (a + eb) S 8/n for all Ho. This is doable for all real analytic functions
37

---

D.3 Lipschitz Functions
The goal of this section prove the following lemma, Lemma D.5 (f is L-Lipschitz, part of Theorem D.3). Suppose f L-Lipschitz we can show
( 1)) S 6K. + hLdn
(6)
Proof. In the proof, we let 6. By Lemma 10,0, we have
Σ (-1) f((a + cb, 17) 1),
(E(1.)
By proof of Lemma C.4, we have
Σ (-1)ll611 S((a +6,1) (-1)
Σ (-1)ll81ls
2a + cb)
(0(0,1)
Let us pick 8 E [d] be the index that X (a) is the smallest eigenvalue for matrix M (a).
Thus, we have
Aiff((aa, 1)) (-1)
Σ (-1)11011
(f.
De (0,
= =(-1)(B(r>))
Σ
be (0.1
(-1))B(())))
Σ
(-1)
(2/. +b) xa)
bE(0,1)
22 (a))+
Σ
bE(0.11
For the first term in the above equation, we can show
A. (a)l s 2d max (a(a))8// 24 K.ō/n 8. Ka
iE[d]
where the first step follows from Assumption, and the second step follows from Fact D.2 and definition of Ka. and the last step follows from n 2d.
For the second term in the above equation, we can show
Σ
(a + eb) <
Σ
Σ
If(la +((aabb,,c) cb,c)) - f((a.
be (0,1))
be (o(11)) (0011)ece0..))) (0,1)))
Σ
Σ
L. (cb,b,))
= -. (
Σ b
Σ
6E10,134
= -- 2d
I. d.
where the second step follows from function f is L-Lipschitz. Thus, we complete the proof.
E Transforming Manhattan to Euclidean
In this section, we prove Theorem E.2, which states that functions f that transform Manhattan distances to squared Euclidean distances are Bernstein. This section is organized as follows
38

---

In Section E.1, we show that any function f 1220 + Rz0 transforming Manhattan to squared Euclidean increasing. This serves as a warm-up for our main theorem.
In Section E.2, we prove the main result of this section, Theorem E.2. We do this by showing that there is a sequence of d-dimensional hyperrectangles such that the kernel matrix associated with them has an eigenvalue which converges to the d order finite difference of f.
In Section E.3, Lemma E.3 shows must be bounded and continuous. This lemma is used in the proof of our main result.
E.1
Manhattan to Euclidean Transforms are Increasing
Lemma E.I. If transforms Manhattan to squared Euclidean, then f is increasing on 12..
Proof.
We fix 0 and show f'(c) 0. Consider X : [d]] - {0. 1} which transforms 1 to 1 and 2c d. Here, is a constant which we will adjust later.
everything else to 0. Let d1 and 02,...
The eigenvalue corresponding to x (by Lemma 1.2) is, by straightforward calculation:
Σ )
d-1
2cs d
- 1(2r
2cs +C) +e))
we divide by 2d-1 and take to infinity, the quantity Eq. (7) becomes f(c) f(c +)
for continuous functions f. Indeed, nearly all of the probability mass in the binomial coefficients concentrates around d/2 by the law of large numbers and the limit follows from continuity of and the boundedness on bounded sets established below in Lemma E.3.
Applying Lemma A.8, we see that if f transforms Manhattan to squared Euclidean distances, then f(c) f(c+ <) 0 for any > 0. This implies the desired result.
E.2 Manhattan to Euclidean Transforms are Bernstein
The goal of this section is prove Theorem E.2.
Theorem E.2 (Manhattan to squared Euclidean, formal version of part (1) part (3) of Theorem 4.4). If f transforms Manhattan distances to squared Euclidean distances, it must be Bernstein.
Proof. Fix a k-tuple =E1,...,EEz) of positive real numbers and define
Af(f.t) := f(t) Σ f(t fn)+ hEM
Σ
f(t c. + (442) +... +-..+((11)4p
t+ Σ G
Consider that transforms 1, .2..... k to 1 and everything else to O. Let a, e, for i E [k] and ak+1 ... Od 26 where c, k and are fixed.
The eigenvalue corresponding to X is, by direct calculation using Lemma I.2:
d-k
(d-
d
- x=
(8)
==0
Eq. (8) is the d-dimensional analog of Eq. (7), and this eigenvalue must satisfy x < by Lemma A.8. Dividing by 2d-k and taking d to infinity, obtain:
( S.
This because again the probability mass the binomial coefficients in Eq. (8) concentrates around the d/2 coefficient, where we use continuity and boundedness of f for any compact set (guaranteed by Lemma F.3). By Proposition A.2 this implies f is Bernstein (Definition 4.3) since k, were arbitrary. This completes the proof.
D
39

---

E.3 Manhattan to Euclidean Transforms are Bounded
The goal of this section is prove Lemma E.3.
Lemma E.3. Any function f R20 + R20 that transforms Manhattan to squared Euclidean is bounded on bounded sets and continuous on (0, xc).
Proof. By the triangle inequality, f(z) f(1/2) + f(1/2) for all 0 S S 1, so f bounded on [0, 1]. By scaling, from now on we assume f is bounded by on [0.
Now, we show f is continuous on (0, 1). Suppose there is a discontinuity some point 0 < 1. This means that there exists some & such that for all O, there are a, b ip 6.p such that f(a) f(b) 2 E. Since f(x) I 1 for all x E [0, 11. this means that for all 8 < min p), we
have that fia) E.
](b)
Now, fix some satisfying the above, and some n 2k. Consider points Zi.... Fn partitioned into sets A = Ii,.... 24 and B = Th+-1..... 2n. For some small that we will choose later, pick
b E (p- p.p p + 5] such that f(a) > 1 1 and define the metric f(b)
0 i=
a i.j e A, A
b i j is in B, +
Now apply f: this gives some metric d' (Ii; such that
0 i=
d' (x1, xT)) = f(a)
(((b)
We show that matrix D(, = (2i, ) is not negative type if n is sufficiently large (as a function of E). Consider the vector
= (1, 1, 1, -I,.....111
with the first & coordinates ones and the last coordinates are negative ones. This is orthogonal to the all ones vector, but
D'u k(k - ()) + (b)
= k(k - 1))((a) -kk())k(()+)(0))
Since f(a) f(b)
+ if we choose 100/s, we will have that
kkk - 1): f(a) - kck + 1) f(b) > 0.
Therefore, by Lemma A.7, d' does not embed into G2 Squared Euclidean space.
However, we show that if is sufficiently small (in terms of n. p). then d(x,, is embeddable into f. First note that the metric d, (i.j) which equals 0 if j and for some constant 0 is embeddable into L,, by transforming i to I; = 5 e, for all i, where e; is the ith unit vector. Likewise, the metric dę, et, j) which equals 0 if j if k l or i f,j k and otherwise is also e;, except which is sent to Fe = 2x
embeddable into f,, by transforming to I, Now, it is trivial to see that by adding finite number of these metrics, still get metric that is embeddable into E
6g-
But, if E [1 T 1007 then any metric such that d(i,j) {a, b) for all a, can be S n.
written as some positive finite combination of d, and dz, over all
Therefore, f is discontinuous at p. we can set n = 100 5 =
min(p.1-p)
and the metric on 100n
.i..... Zn defined previously. We will have that
a b
1
10n2
10n?
40

---

T(5] > 1 E, which means that while d is embeddable into &1, d' f(d) is not embeddable into fg. Thus, f is discontinuous at p, we have that f cannot transform Manhattan Distances to Squared Euclidean distances.
whereas M(a]
By scaling the r-axis, we have that f is bounded on any interval [0, a] and that is continuous all x > 0.
F
Transforming Manhattan to Manhattan
This section is organized as follows:
Section F.1 shows how to compute an explicit Euclidean embedding for the distances of Manhattan distances.
obtained after applying Manhattan-to-Fucet to-Eluliean transform
In Section F.2, we prove Theorem F.3, which states that Manhattan Manhattan transforms are equivalent to Manhattan to Squared Euclidean transforms. This may be surprising since Squared Euclidean distances much
general than Manhattan distances.
Section F.3 gives discussion for how to generalize our result if the initial metric space was any metric with a vertex-transitive symmetry group, instead of Manhattan distance. We emphasize the importance of vertex transitivity of the symmetry group, and explain why that feature is important for our techniques to apply.
F1 Explicit Embeddings for Manhattan to Euclidean Transforms
Suppose f transforms Manhattan distance to squared Euclidean distance. By definition, f satisfies the following: for any and any ..,... In E (R% {i), there exist pr,... Pr E (IR f2) such that f(lar; - Ø (11) Ilp. - Pyll We can assume without loss of generality that points I1, Ø2, In are distinct corners of a dimensional hyperrectangle (Definition C.3), and n = 2d. This is because any point set in & can be embedded isometrically into l on corners of hyperrectangle (Lemma A.3).
Lemma F.1. Let D be the matrix where Di, = f(1 Zz m1)l1,, and let M == IIDI. Then M has eigenvectors Ha.
Proof. This follows from Lemma B.1 and the definition of M. It is critically important that the columns of Ha are orthogonal the all ones vector (with the exception of the all ones column in Ha).
Lemma F.2. Let M HHLHHa be an eigendecomposition of M, where M is defined as Lemma F.1. If f transforms & to E2, then Σ has entirely non-negative entries.
For each i, we use p; to denote the i-th column of P VE.aa. we have (pi,Ps) = Ma,5 and f(lax - 21)11) = [pp 13
Proof. This follows from Lemma A.9 and Lemma F.I.
F.2 Manhattan to Manhattan Transforms are Equivalent to Manhattan to Squared-Faclidean Transforms
The goal of this section is prove Theorem F.3.
Theorem F.3 (Manhattan to squared Fuclidean, formal version of part (2) + part (3) of Theorem 4.4). Any function that transforms Manhattan distances to squared Euclidean distances must transform Manhattan distances to Manhattan distances, and vice versa.
Proof. Let Pş be defined as in Lemma F.2. By construction, the vectors P; subset of the corners of 20 oi-dimensional hyperrectangle, with side lengths / E/E,. Thus, the pairwise squared Euclidean distances between pd are isometrically embeddable into & by Lemma A.4. In other words, f(11=; 2y l1) llp, 1 l|q: 4 l for some q, E l₁ for all j. This shows that any f that transforms & to & transforms & to é as desired.
D
41

---

Note that for any the vectors are finite dimensional and can be explicitly written down in closed
form.
F.3 Metric Transforms for Distances with Group Symmetries
In our proof of Theorem F.3, we exploited that our points 21, In are points in a hyperrectangle, which has vertex transitive group symmetry. Similar theories be generated when the point set lives on any object with a vertex-transitive group symmetry, and the distance measure between points some function of the Euclidean distance. Such objects include higher dimensional platonie solids, spheres, equilateral triangular prisms, and more.
We remark that the group symmetry must be cortex-transiie to ensure the matrix D in Lemma B.1 has an eigenvector equal to the all ones vector. this were not the case, Lemma F.1 would no longer hold.
G Positive Definite Manhattan Kernels
The goal of this section to prove Theorem G.2, a formal restatement of Theorem 3.4.
The section is organized as follows:
In Section G.I, show that positive definite Manhattan kernels map positive numbers positive numbers. This will be used in our proof of Theorem G.2.
In Section G.2, we present and prove Theorem G.2. This result classifies all positive definite Manhattan kernels (Definition 3.1), and proves that positive definite Manhattan kernels are equivalent to completely monotone functions.
G.1 Positive Definite Manhattan Kernels map Positive Reals to Positive Reals
First, we prove the following lemma.
Lemma G.1. If f positive definite Manhattan kernel (Definition 3.1), then f(t) 2 0 for all 120 0.
Proof. Let X' denote metric space (R-N L)). For any 2 0 we consider the points x; = fe, X for i E [N] where
(0,... ... 0, 1, 0. ......... 0) is standard basis vector, so that ||x; - 2z I t for
any & j. Since the matrix of values (f([l - z, =)ll)),see must positive semidefinite, the sum
of all its entries must be positive, hence:
((((0) (N 1)f(()) 2
The above equation implies the following:
f(0)
+ f()) 0
N --1 1
for all integer N 2 0 and real t 2 0.
Since N can be arbitrarily large, therefore we conclude f() 2 0 as claimed.
G.2 Positive Definite Manhattan Kernels are Completely Monotone
The goal of this section is to prove Theorem G.2.
Theorem G.2 (Formal statement of Theorem 3.4). f: R220 - R is a positive definite Manhallan kernel (Definition 3. if and only if [xx is completely monotone (Deftmition 3.2).
Proof. First, prove that if ff is positive definite Manhattan kernel, then f must be completely monotone. The converse direction is previously known, and is a consequence of Lemma A.5 and Theorem of [SOW01]"1,
Theorem of [SOW01] is modern restatement of Schoenberg's work in [Sch42].
42

---

Suppose that f is positive definite Manhattan kernel (Definition 3.1). Cauchy-Schwarz easily
implies that f(t) - f(0) for t, f bounded.. Now, if ; then
Zn. correspond .i...... Vn
5(11> xzll1) (yi, (g)
=((0) l1ys - B3 -35112-
Therefore ([f(0)- f()) (equivalently, f(0)- f()) sends Manhattan distances to squared Euclidean
distances. Therefore f(0) f(t) is Bernstein (Definition 4.3). by Theorem 4.4. Combining with Lemma G.I we conclude that f must be completely monotone (Definition 3.2).
H Positive Definite Euclidean Kernels
The goal of this section is to prove the foundational classification of positive definite Euclidean kernels [Smo96, SOW01, Sch42j. We focus on proving the 'hard' direction, that a function f is positive definite Euclidean kernel only if f(vz) is completely monotone. Such a proof is straightforward from Theorem G.2, as seen below. For the other simpler direction, see the simple proof in Proposition 11 of [SSB 97].
Theorem H.1. [Sch42] f I2z0 + R is a positive definite Euclidean kernel (Definition 3.1) only if f(Vz)) a completely monotone function (Definition 3.2).
Proof. Theorem G.2 combined with the fact that Manhattan distances isometrically embed into squared Euclidean distances (see (DL09]) prove that f(vØ) must be completely monotone it is positive definite Euclidean kernel.
I Eigenvalue of Kernels from the Hyperrectangle
In this section, we prove Lemma I.2, a variation of Lemma B.1. This lemma uses representation theoretic ideas to compute the eigenvalues of matrices arising from the real hyperrectangle. We use this modified formulation in our proofs of Theorems 4.4 and 3.4. We introduce Lemma I.3, which expresses these same eigenvalues in terms of integrals, a lemma of independent interest.
I.1 Matrices with Reflectional Symmetries have Hadamard Eigenvectors
Lemma 1.1. Let (IR x (R) I. such that g(2, y) is invariant under axis reflection. Consider d-dimensional hyperrectangle with corners I1.... Let D be 2 by 2 matrix such that
Dig = g,);, Then there an eizendecomposition of D into H&LHa where E is a diagonal matrix.
Proof. This lemma can be proven directly via computation. However, is more instructive to view this through the representation theoretic lens. We note that D has the property that for any permutation matrix a corresponding to a reflection about one of the hyperrectangle's s axes, we have a = Do. Schur's 's lemma from representation theory (see Lemma A. states that D and all in the reflectional symmetry group of the hyperrectangle have a common set of eigenvectors. It is straightforward to verify that the only common set of eigenvectors for all a is the columns of the Hadamard matrix, and thus D must have the columns of Ha as its eigenvectors.
We note that variants of this lemma used prove Delsarte's linear programming bound in error correcting codes [De173, O'D14].
1.2 Figenvalues of Kernels from the Hyperrectangle, Restated
Lemma 1.2 (Figenvalue of Manhantan Kernels, formal version of Lemma B.1). Consider d- dimensional hyperrectangle (Definition C.3) parameterized by a1,... ag > O. Enumerate the vertices in lexicographical ordering as .ps.
43

---

For any : + R. let D be the 2 by 2 matrix given by Dr,, f(lps, - Ppll1)- Then:
1. E: = HaDHH is diagonal matrix whose entries are the eigenvalues of D multiplied by 2 and D = 4- H.
2. Let x: 1). Let k equal the integer corresponling to transforming (written as a dimensional binary vector) into integer via binary conversion. For each x. there is an eigenvector of D equal to the k-th columu of Hadamard matrix Ha. and its associated eigenvalue is:
Σ TCId
(-1)Ste7X0))
Σ
TET
The second part of this theorem on its surface differs from that in Lemma B.1, but the statements are in fact identical via straightforward computation.
Proof. By Lemma 1,1, we know that the Hadamard matrix columns are eigenvectors of the matrix D. The result follows by direct computation.
We now give alternate formulation of the eigenvalues in Lemma 1.2. This lemma is of independent interest.
Lemma L.3, Given a box with side lengths a1, ad. each eigenvalue corresponds to a function
X [d] + 10, Let Q {q1.... 9kk be the full set values which x is 1. Then the Eigenvalues
in Eq. (9) equal:
Doz +Eer
(-1)ad'
d dx
Σ Sq
dsi ... dsy.
Ciena
T
QEQ
Proof. The proof follows directly from Lemma 1.2 combined with the fundamental theorem of calculus.
J Converse to Stable Rank
Recall Definition 2.7, for matrix A, we use srank(A) denote the stable rank of A. For matrix A, we use ||||r to denote its Frobenius norm. We use ||||] to denote its spectral norm.
J.1 Lipschitz functions preserve stable rank
Definition J.1. We say function f is (L, Ll-iishitz on on entries of matrix A, for any x 2 0 in entries of such that
1
< f(x) S VTx
Ve"
Theorem J.2. We define B E R as follows Big f(Ai) 3. for all i E [m] and for all j E [n].
If function is (T, -ippsshhi on A Rax,, then we have the following
Part 1. 1/vl- || |B| S VL ||A]|
Part 2. 1/vI ||||| < |B| VL. |A]]
Part 3. I-1, (-1 srank(A) (A) S srank(B) S L. . srank(A).
Proof.
Proof of Part 1.
44

---

We can upper bound | p as follows
11
|B| )(A.g)
j=1
L ||||
(10)
where the first step follows from definition of || || the second step follows from f(A,)) S L. A.... and the last step follows from definition of || norm.
We can lower bound |B|
follows
BI
f(A
21
A
1- |
(11)
where first step follows from definition || || norm, the second step follows from f(A 1-1 Al and the last step follows from definition of |F norm.
2
Proof of Part 2.
We upper bound on |B| (BB) as follows
o(B)²
max (v Br)² M+lla=
1
max
U:0yf (Ai.))²
< max
( 2.
M
1=1 1=1
o (A)² T.
(12)
where the first step follows definition of spectral norm, the third step follows from f(Ac,)? = A?,- L.
We lower bound on |B| a (BB) follows
OB)²
max (v Bu)²
||
max ||
Usts Ne (AA.)))
max ||+||==1
Usuy Aig))
= (A))/e
(13)
where the third step follows from /(Aig) 2 /
Proof of Part 3.
45

---

We can upper bound srank( B) follows
1B
srank(B) (B)
o (B)²
L ||A||
(B))
L ||A||
( (A)3/R
L 8 srank(A)
where the first step follows from definition of stable rank, the second step follows from Eq. (10), the third step follows from Eq. (13), and the last step follows from stable rank.
We can lower bound (B) as follows
|BB
srank( (3)
o (B)2
/A////E
(B)2
Alli/
o (A)2L
= 1....--s.aaaaa
where the first step follows from definition of stable rank, the second step follows from Eq. (11,, the third step follows from Eq. (12), and the last step follows from definition of stable rank.
J.2 Fast-Growing functions not preserve stable rank
We start with presenting a tool for symmetric matrix.
Lemma J.3. Consider symmetric matrix M with non-negative entries, with the all ones vector as an eigenvector. The eigenvalue of this vector is the largest eigenvalue of M
Proof. This follows from the Perron Froebenius formula [Per07, Fro12] on non-negative matrices.
For matrix M, we use Mt, to denote the entry at i-th row and j-th column in the matrix. Lemma J.4. Let M be a n by n matrix with non-negative entries, with an eigenvector that the alll ones vector. Suppose that there exists permutation o [n] > [m] such that M is the unique largest element in row for all i [ni] Suppose that k == M), which is independent of and all other entries are less than where <
Then, we have
nk.
srank(M) 2
(k + ns)²
Proof. By Lemma J.3, the eigenvalue of M corresponding to the all ones vector, is the largest eigenvalue of M. Recall that the stable rank of M is defined as the Froebenius norm squared, divided by the spectral norm squared.
The largest eigenvalue of M Σ. M,1 which is bounded above by k + sn,. Meanwhile, the squared Froebenius norm of M is bounded above by nk? which is the sum of squares of the diagonal elements. This completes the proof. Dividing our two bounds gives our lemma.
Now, consider the distance matrix M arising from applied entry-wise to the matrix arising from the hypercube with side lengths 3 (this is the hyperrectangle where all side lengths are the same). We
46

---

note that the hypereube matrix has rank log n + 1, and thus its stable rank is also bounded by this quantity.
In this case, we note that M has non-negative entries, has the all ones vector as an eigenvector, and has the property that there exists a permutation such that M) is log n. Meanwhile, all the other entries are less than 3 log n - 3.
We note that if k/s > n then the stable rank of M is P(n).
The rest of the proof devoted understanding when k/s 0-5
This is equivalent to:
fB log n) [[3 T[3logm n -B) 2 0.5
(14)
Since 3 can be set to anything, we define 7 = B log n. and thus Eq. (14) is equivalent to
f(r(1+ 1 1ر 2 n 0.5 f(7).
(15)
log n
Theorem J.5 (Superpolynomials don't preserve stable rank). f(x) = m!ngg x + ofx 2) does not preserve stable rank for any 0.
Proof. It is sufficient to show that
f(y(1 c))
(16)
f(7)
is unbounded for fixed and variable > 0. Substituting f(x) x loo" x get
y (xx70))
(17)
1og y
Next, we need to show that
lim Eq. (17) 00. 7000
We define function
F(x) log
and compute
F'(x)= = c log (
I
1
1
F*(x)= = c. (c - 1) x2a
log log -- (x) c log 1og--(() (x)
=c (cc 1) c-2 (x) log c- (x)
Using mean- value forms of Taylor's theorem,
F(y) F(x) (y-z) + 1 (z) (y- x²2
where z [x. v). We can compute
F((x) (y x) =c log (7)
(
7
= -cclog--10 (7)
47

---

We can compute
F (z) (y -y=))²
x2 ((c =²((c
1
log ( 1og"~((x) (z)) (cy)²
6²
a1+ ((c - 1) log (2) log e- (z))
where choosing = = ary (where a E (1,(+
Then it is obvious to see that 1/2 (2) (y z) - 10 Fx:) (y x).
Finally, we can lower bound
F()(1+))) -(m) 2 (7) ed //2 Fx)] (e7)?
2
(7) .e
cclog 10og-~1p (7))
where = by, (1 + +)n]
Thus, we have
lim Eq. (17) = lim ()oog) (ogg) (x)) 7-000
7-030
=
lim
2 gec - (()
7-000
00.
Thus, complete the proof.
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In our research, we establish that low-degree polynomials are the exclusive functions that consistently yield low-rank matrix when applied entry-wise another low- rank matrix, comprehensively categorize functions that transform Manhattan distances into either Manhattan or squared Euclidean distances, and classify all positive definite kernels using Manhattan distance as input. The abstract and introduction accurately reflect our main results, introduce some background, and emphasise the importance our work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
The limitations are discussed in Section 7.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
49

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
All our main results in the paper have formal versions and verified formal proofs.
Justification:
For Theorem 2.5, see Theorem C.11 for formal statement and Section C for formal proofs.
For Theorem 2.6, see Theorem D.3 for formal statement and Section D for formal proofs.
For Theorem 2.8, see Theorem J.2 for formal statement and Section J for formal proofs.
For Theorem 4.4, see Theorem E.2 and F.3 for formal statement and Section and for formal proofs.
For Theorem 3.4, see Theorem G.2 for formal statement and Section for formal proofs.
The proof's of all other theoretical results are below the statements.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This is a theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make clear how reproduce that algorithm.
50

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (c.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
This is a theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c ca/
mablic/guides wttp///oooSuuimsiiiioiiii Policy) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: // //nips. mtips.ccppbblli. wwtpccccpc/pppececcccccccccceeee wwwpd//cgggie//eeeeeeeeooeeeeeee httpg//ddd///eeeubiiiiieese SeroodSSumisssonnt
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
This is theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
51

---

Answer: [NA]
Justification:
This is theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Fthics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpp:://///uiigee /ttp/ieuur.pp//e wttppcpccpccccceccccccccccccccct ceGuiieieees
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and ensured that our paper complies with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
52

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The societal impacts discussed in Section 8.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This is a theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
This is theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
53

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. . com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This is theoretical paper and does not conduct any experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is theoretical paper and does not conduct any experiments.
54

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
55


Reviews:
[{"review_id": "JKnaOqvOMf", "reviewer": "Reviewer_voKg", "summary": "This paper studies kernel functions with a particular interest to Manhattan distance kernels. The following three questions are studied:\n1) For which functions f, entrywise transformation f(M) is guaranteed to not be full rank if M is any sufficiently low-rank matrix?\n The authors show that if f does not have essential discontinuities of first type and entrywise f(M) has rank < n whenever M has rank $< log_2(n) + 2$, then f is necessarily a a polynomial of degree at most $log_2(n) +1$.   \nThe claim in the paper seems to be made for all n, though the proof seems to require n to be a power of 2.\n2) What functions are positive definite Manhattan kernels?\nThe authors show that f is positive definite Manhattan kernel iff f is completely monotone. (Theorem 3.4)\n3) What functions transform Manhattan distances to Manhattan distances?\nThe authors show that f transforms Manhattan distances to Manhattan distances iff f transforms Manhattan distances to squared Euclidean distances iff f is Bernstein.\n\nThe key technique used in this paper is connecting all three problems to study of the eigenvalues of $2^d \\times 2^d$ matrices whose entries are defined as $D_f = f(\\Vert x_i - x_j \\Vert)$, where $x_i, x_j$ are vertices of $d$-dimentional hyperrectangle. The key observation is that such matrices are preserved by a permutation group induced by reflections in $R^d$, which by Schurs lemma implies that eigenvectors are eigenvectors of Hadamard matrice H_d. This allows to explicitly compute and analyze eigenvalues of $D_f$ (Lemma B1), and this analysis allows to make progress on all three problems above.", "questions": "1) Is not Lemma B1, and hence any lemma that depend on calculation in this lemma, require n to be a power of 2? In particular, Lemma C4, C5, C6, Theorem C11, Theorem 2.5 etc all seem to require n to be a power of 2?\nIf not, how does the proof work for the case when n is not a power of 2? If yes, can you please make it explicit in all those statements that n should be a power of 2? I think results have somewhat substantially different flavor if they hold only for powers of 2, instead of for all integer n.  \n2) Theorem C11 has conditions missing, even though it is marked as \"formal statement\". At least it should be mentioned that f is assumed to not have essential discontinuities.\n3)  Line 1299 talks about matrix A which is only introduced in line 1303.\n4) The statement of Theorem 2.4 is somewhat confusing, more specifically the claim that Fact 2.1 is \"tight\".\n5) nitpicking: in statement of Lemma C15 rank of M can be less than 5, if n < 5.\n6) nitpicking: in line 1163 (and other places) if one wants to be pedantic, $\\Delta_{\\epsilon}^{d}$ is an operator applied to functions defined on $R^d$, while f is defined over $R$. I think it should be applied to $f(\\langle \\cdot , 1\\rangle)$ at $a$.\n7) L1191 closing ) is missing.\n8) $S_i$ and $T_i$ are mixed up in L 1245-1246\n9) Computation from lemma C9 is simple so it is a bit strange to keep it so far from Lemma C4 where it is used, and requires reader to jump back and forth.", "limitations": "na", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The problems studied in this paper are important, natural, and in some sense fundamental (e.g., classification of positive definite Manhattan kernels). Hence, I think this is a very nice paper, which is well-motivated. Similar classification for Euclidean distances was obtained almost a century ago, and Manhattan distance is one of the \"next\" natural metrics for which this question can be asked. It was known for a long time (in one direction) that Bernstein functions preserve Manhattan distances and completely monotone functions are Manhattan distance positive definite. However, this paper appears to be the first one to show that only these functions are the only functions with such properties, proving the opposite direction of the classification.\n\nI am not familiar whether idea to study eigenspaces and eigenvalues of entriwise transforms of hyperrectangles appeared before in the context of these problems, but the idea is very interesting and productive. The proofs are sufficiently rigorous and appear to be correct (I verified some but not all in detail).", "weaknesses": "I have mainly two concerns:\n1) I think the presentation of the results can be improved substantially, and I hope that the authors will polish the paper more for the final version if the paper gets accepted. In particular:\n --  I think it is important to include more insights about the proof technique and main novelties of the paper in the main text. At this point, only lines 365 - 380 (Section 5) provide some substantial insight into the proof. Some paragraphs of other sections can be shortened without  losing much content, which would allow for more insights into the technique, which, in my opinion, is important to do in the main text.  In particular, I find lines 999-1005 very insightful, and I think moving them up should help the reader a lot.\n -- Some statements and notation are imprecise or confusing (see below)\n -- There are a lot of forward references, which make it somewhat hard to read the proofs. For example, proofs in section E talk about \"eigenvalues corresponding to $\\xi$\" (e.g., line 1407), while this makes sense only after reading section I, which is much later. There is many forward references like this. \n -- There is non-negligible amount of typos\n\n2) I am not sure that this is the right venue for these results. The results proven in this paper are great, but they seem to belong to the field of metric geometry/analysis. While there is a connection to learning theory, as the authors indicate in the introduction, in my opinion, the connection is somewhat weak and tangential.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review.\n\nTo address weaknesses:\n1. Thank you for pointing this out. We will take your suggestions for a final draft, expand on the proof technique and main novelties in the introduction, correct typos, and make statements (such as the ones you point to) more precise. We will also remove forward references to improve readability.\n2. Our techniques are based on metric geometry, and they have strong applications to machine learning, including attention computation in LLMs, kernels, and more. For example, we show that low-rank fast attention (the theoretical state of the art for method fast attention computations) *must* rely on polynomial approximations or replacements for the softmax function in the definition of Attention. Such a result is more relevant to machine learning than metric geometry. The application of metric geometry techniques to a variety of machine learning fields such as LLMs and kernels should be considered a strength of our paper, and we are particularly excited about disseminating our results to the ML community.\n\n\nTo answer your questions:\n\n1. The lemma as stated has $n$ as a power of 2, but the statement for general $n$ follows directly from the statement for $n$ as a power of 2. This is because of the fact from linear algebra that if a $N \\times N$ matrix $M$ has full rank, then for any fixed $n \\leq N$ there exists an $n \\times n$ minor of $M$ with full rank. (This follows, for instance, from expansion by minors.)\nSuppose $n$ is not a power of $2$, and let $2^d$ be the smallest power of $2$ bigger than $n$. If $f$ is not a low-degree polynomial, our work as-stated proves that there exists a low rank $2^d \\times 2^d$ matrix $M$ where $M^f$ is full rank. By the above, there exists an $n \\times n$ minor $M_n$ of $M$ (with low rank, since its rank is less than that of $M$) where $M_n^f$ is full rank. Therefore, $f$ cannot preserve low rank matrices of dimension $n \\times n$, if $f$ is not a low degree polynomial.\n\n2. Thank you for pointing this out! Theorem 2.5 is actually our full formal statement as-is, and Theorem C11 is missing the essential discontinuities of the first kind (but nothing else). We will correct this in the final version.\n\n3. Thank you for noticing this; we will correct it in the final version.\n\n4. In Theorem 2.4, when we wrote “Fact 2.1 is tight”, we meant to say that the converse of Fact 2.1 is true when $f$ is $n-1$ differentiable. To be precise, if $f$ is $n-1$ differentiable and $f$ preserves low rank, then Theorem 2.4 states that $f$ must be a low degree polynomial. We will clarify this and remove the word “tight” from Theorem 2.4.\n(Just to clarify: Our new results show that this converse is true even without the $n-1$ differentiability, and is true for all piecewise continuous functions. As mentioned in Section 2, this set of functions is considerably more expansive than $n-1$ differentiable functions, and includes popular non-second-differentiable functions like ReLU, ELU, and SeLU, as well as analytic oddities like the no-where differentiable everywhere-continuous Weirstrauss function. Our new result also shows that approximate low rank preservation is impossible for piecewise continuous functions that aren’t approximations of low-rank polynomials, whereas Theorem 2.4 didn’t have any results about approximability.)\n\n\n\nOther questions: Thank you for noting these typos and other minor issues, we will correct them all in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5uEiPhi03T", "reviewer": "Reviewer_MC98", "summary": "The paper achieves three main results: Firstly, it demonstrates that polynomials are the only piece-wise continuous functions for which applying them entry-wise to a low-rank matrix results in another low-rank matrix. Secondly, it shows that if f is a Manhattan kernel, then it must be a completely monotone function. Thirdly, it shows Bernstein functions are the only ones that transform the Manhattan metric to the Manhattan Metric.", "questions": "To what extent can your results for metric transformation and kernel classification be extended beyond the Manhattan metric?", "limitations": "The authors have discussed the limitations of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. I found the paper well-written and highly readable, with a smooth flow. The related works are properly discussed, providing clear motivation for each problem. The proofs are divided into steps, and the ideas are explained clearly, allowing the reader to engage with the paper's storyline. I believe this paper will certainly be of interest to the NeurIPS community.\n\n2. The paper is mathematically solid. The results and the techniques used to obtain them are interesting and mathematically rigorous and effectively address the problems outlined in the summary.\n\n3. The technical core of all three main results involves a simple application of Schur’s lemma, which characterizes the eigenvectors of a 'Gram-like matrix' derived from the vertices of a hyper-rectangle. Another interesting aspect of the paper is the author's observation that this technical tool can be employed to address the aforementioned problems.", "weaknesses": "None.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review.\n\nGreat question: one can show with some work that the same theorem statements hold for a broader class of metrics, including effective resistance distances from electrical network theory, or the class of graph metrics arising from all star graphs. Exploring this type of result beyond Manhattan metrics is a rich area of exploration for future work, and we expect the landscape and necessary techniques to vary for different types of metrics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3dbLchEhw5", "reviewer": "Reviewer_iDXR", "summary": "This paper studies three seperate problems relating to metric transformations of kernel matrices via a new mathematical technique which the authors refer to as the representation theory of the hyperrectangle.\n\nThe first problem is about characterising the entrywise transformations which, when applies to a low-rank matrix, preserve its low-rank structure. The problem is considered in the context of speeding up attention compuations in LLMs. They\n\n1. show that polynomials are the only class of functions (without essential discontinuities of the first kind) which, when applied entrywise to a low-rank matrix, preserve the low-rankness of the matrix (as defined in Def. 2.2). This result generalises an existing result in the literature for a more restrictive class of functions.\n2. show that the result is still true even is \"low-rank\" is relaxed to \"approximately low-rank\" (matrices with small inverse condition number), and \"polynomial\" is relaxed to \"approximately polynomial\" (functions with small finite differences). \n3. show that entrywise \"functions that do not grow too quickly\" preserve a relaxation of low-rankness known as \"stable rank\". This includes non-polynomial functions. However, most applications of matrices with low stable rank require the whole matrix to be computed, which does not achieve the goal of fast attention computation. \n\nThe second problem is a complete categorisation of all funcions of l_1 norm distance which result in positive semi-definite kernel matrices. These are shown to be the class of completely monotone functions.\n\nThe third problem is to characterise the set of functions which transform one semi-metric space into another. They show the equivalence between a function being Bernstein, it transforming l_1 distances to l_1 distances, and transforming l_1 distances to squared l_2 distances.", "questions": "- I was surprised by the lack of mention of Mercer's theorem on the existence of the feature maps F in Section 3. Is this covered by other references?\n- I would be interested to see simulated experiments to demonstrate Theorems 2.6 and 2.7.\n- Please could you explain the implications of Theorem 4.4 on a problem in machine-learning.", "limitations": "The authors are upfront about limitations, particularly with relation to stable rank, which I think opens up interesting directions for future research.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper, including the proofs, are accurate and well-written. The first section answers some important questions about the rank of matrices after entrywise transformations. I believe this section of the work will be of great interest to those working on attention in LLMs. The section essentially closes the question of which transformations preserve low-rankness by proving that it is only functions in the class of polynomials (bar functions with essential discontinuities of the first kind, which the authors conjecture do not preserve low-rank anyway, and I am inclined to believe them). The exploration of how the answer to this question changes which the notion of \"low-rank\" is relaxed to \"approximately low-rank\" and \"of low stable rank\" is informative and compliments the first result nicely. \n\nThe characterisation of semi-positive definite kernel matrices which are function of l_1 distance also closes an open question with an elegant result. This result will likely be of interest to researchers in the theory of kernel methods.\n\nThe theoretical work in Section 4 is also interesting, however the significance the machine-learning community is perhaps slightly less than the previous sections.\n\nThe mathematical tools developed to study the spectral properties of matrices whose entries are the l_1 distances between the vertices of a hyperrectangle do not receive much attention in the main text, but may well be of independent interest to mathematics research is many disciplines.", "weaknesses": "One might argue that this paper tries to do too much for a conference paper, and as a result much of it feels rushed or unduly relegates details to the appendix. The sections sometimes feel unrelated, and the paper lacks a clear narrative. Empirical experiments to demonstrate the results in Section 2 would be very welcomed, and I think would enhance the message of the paper. However, there is clearly not space for this as it stands. I can imagine a more focused version of this paper which moves the results in Sections 3 and 4 to another paper, and which focuses only the results in this Section 2, which I believe have the most value to the machine learning community. This would give more space to the mathematical tools in Section 5, and to experiments.\n\nThat said, all of the individual contributions are strong, and I have no criticisms of any of content of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. \n\nRe: “the sections sometimes feel unrelated, and the paper lacks a clear narrative”: The sections are related through the unifying technique: the representation theory of the real hyperrectangle. Indeed, all our results (from LLMs to kernels) follow from this one new technique. We plan to emphasize this early in the introduction in the final version of the paper.\n\nTo answer your questions:\n1. Indeed, Mercer’s Theorem is covered by our other references. For instance, it is heavily referenced in our citation [SOW01]. But you’re right that it’s important and we implicitly use it; we will cite it directly in the final version.\n2. We agree that experiments relating to Section 2 would be exciting. Some prior empirical papers have performed experiments showing that polynomials in attention are effective. See, for instance, reference [KMZ23] (which appeared in ICML 2024). More experiments on our results, including a search for optimal low-degree polynomials to use in attention, would be an exciting area for future work.\n\n\n3. The areas of metric transforms have numerous applications to machine learning (see lines 67-77 on page 2), and our Theorem 4.4 gives a new structural result about what is possible in metric transforms.  \n   The known statement using Euclidean instead of Manhattan distances (which our Theorem 4.4 extends) is widely used in machine learning. Some specific examples include the converse to Theorem 2 in our citation [RYW+19] about interpretability (“Visualizing and measuring the geometry of BERT” [NeurIPS ‘19]), and in Theorem 4 and 5 of our citation [FLH 15] giving a framework for kernels on popular Riemannian data manifolds in computer vision (“Geodesic Exponential Kernels: When Curvature and Linearity Conflict” [CVPR ‘15]). Again, Lines 67-77 on page 2 of our paper give a longer list of applications.   \n    We are confident that our Theorem 4.4 will be useful for proving future results similarly. Perhaps the most striking part of our Theorem 4.4 is that it is proved using the exact same technique as our other results.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduce a new linear-algebraic tool based on Abelian group representation theory, and use it to address three key problems in machine learning, leading to three new results:
*  It demonstrates that polynomials are the only piecewise continuous functions for which applying them entrywise to a low-rank matrix results in another low-rank matrix.

*  It shows that if $f$ is a Manhattan kernel, then it must be a completely monotone function. 

* It establishes that Bernstein functions are the only ones that transform the Manhattan metric into the Manhattan metric.

All reviewers acknowledge the novelty and significant contributions of these results, and especially the potential application to the attention mechanism in LLM. Therefore, I recommend accepting this paper.
Decision: Accept (spotlight)