Extending Mercer's expansion to indefinite and asymmetric kernels
Authors: Sungwoo Jeong
Alex Townsend
Venue: ICLR 2025 Poster (2025)
Keywords: Kernel methods
Mercer's expansion
Indefinite kernels
Convergence behavior.
Primary area: learning theory
TL;DR: We extend and prove new convergence properties of Mercer's expansion for general continuous kernels.

Abstract: Mercer's expansion and Mercer's theorem are cornerstone results in kernel theory. While the classical Mercer's theorem only considers continuous symmetric positive definite kernels, analogous expansions are effective in practice for indefinite and asymmetric kernels. In this paper we extend Mercer's expansion to continuous kernels, providing a rigorous theoretical underpinning for indefinite and asymmetric kernels. We begin by demonstrating that Mercer's expansion may not be pointwise convergent for continuous indefinite kernels, before proving that the expansion of continuous kernels with bounded variation uniformly in each variable separably converges pointwise almost everywhere, almost uniformly, and unconditionally almost everywhere. We also describe an algorithm for computing Mercer's expansion for general kernels and give new decay bounds on its terms.

Published as a conference paper at ICLR 2025
EXTENDING MERCER'S EXPANSION TO INDEFINITE AND ASYMMETRIC KERNELS
Sungwoo Jeong
Alex Townsend
Department of Mathematics Cornell University s sjeong@cornell edu
Department of Mathematics
Cornell University
townsend@ccone edu
ABSTRACT
Mercer's expansion and Mercer's theorem are cornerstone results in kernel the- ory. While the classical Mercer's theorem only considers continuous symmetric positive definite kernels, analogous expansions are effective in practice for indefi- nite and asymmetric kernels. In this paper we extend Mercer's expansion to con- tinuous kernels, providing a rigorous theoretical underpinning for indefinite and asymmetric kernels. We begin by demonstrating that Mercer's expansion may not be pointwise convergent for continuous indefinite kernels, before proving that the expansion of continuous kernels with bounded variation uniformly in each variable separably converges pointwise almost everywhere, almost uniformly, and unconditionally almost everywhere. We also describe an algorithm for computing Mercer's expansion for general kernels and give new decay bounds on its terms.
INTRODUCTION
Before the singular value decomposition (SVD) of matrix, several pioneers of modern functional analysis in the early 20th Hattury-HHmmmrstter (1923), Schmidt (1907). Smithies (1938), and Weyl (1912) -igured out the properties of the eigenfunction expansion and the singular value ex- pansion (SVE) for a general square- integrablee kernel (Stewart 1993). Within these developments, Mercer, in 1909, showed that any continuous, symmetric positive definite kernel K [a, (a, b) + IR with oo < < b can be expressed as an absolutely and uniformly convergent sum of orthonormal eigenfunctions multiplied by their corresponding eigenvalues, i.e.,
K(x, v) Σ Xn (n)u(())unn (x. [a, b] (),
The expansion in eq. ① is typically called Mercer's expansion of K (Mercer 1909).
Mercer's expansion is an important result in functional analysis. It plays a crucial role in many machine learning applications because it underpins the theory of kernel methods (Scholkopf & Smola 2002; Kung 2014). allowing researchers to develop theoretical foundations for Gaussian processes (Kanagawa et 2018), support vector machines (SVM) (Cortes & Vapnik 1995 Stein-
wart & Christmann 2008). Transformer models (Vaswani et al. 2017 Wright & Gonzalez 2021
and many other applications (Ghojogh et al. 2021).
Several researchers have been interested in using Mercer-like expansions for continuous kernels that are symmetric but not positive definite (indefinite kernels) as well as general continuous ker- nels that are not symmetric (asymmetric kernels). There are at least three reasons why indefinite and asymmetric kernels are useful: (1) Checking whether a kernel is positive definite can be com- putationally expensive (Luss & d' d'Aspremont 2007) [Huang et al.) (017). (2) Often one finds that Mircer-like expansions continue to hold for indefinite and asymmetric kernels, even though the the- oretical underpinnings have been lacking, and (3) Indefinite and asymmetric kernels, such as the sigmoid (tanh) kernel, naturally arise applications such as Transformers (Wright & Gonzalez,
2021
Chen al. 2024), kernel learning theory (Haasdonk & Keysers 2002 Ong al. [2004] He
ct al.
2023), H control theory (Hassibi et al. 1999). protein sequence similarity (Saigo et al. 2004), and many others.
2004
Vert et al.

---

Published as a conference paper at ICLR 2025
Surprisingly, continuous symmetric kernel may not have Mercer-like expansion that converges pointwise (see Proposition!! [T.. We hope this new example clarifies some confusion in the literature on Mercer's expansion for general kernels. We also prove that general continuous kernels may also have Mercer's s expansions that converge pointwise, but not uniformly and absolutely, meaning that Mercer's expansion must be used with some care for general kernels.
This work provides a rigorous theoretical underpinning of Mercer's expansion for indefinite and asymmetric kernels. For indefinite kernels, the eigenfunction expansion is the most natural gen- eralization of Mercer's expansion. For asymmetric kernels, the most natural generalization is the following singular value expansion (SVE) that was considered in the early 1900s (Schmidtt 1907
K (xx, v) = Σ un (n)n(())n(())
(2)
where oi T2 2 ..... 0 are the singular values of K and {un JeeN and {u, MeN are sets of orthonormal functions called the right and left singular functions of K, respectively. The expansion eq. (2) can replace Mercer's expansion for asymmetric kernels (see Section (3). We regard eq. P
as natural generalization of Mercer's expansion to general continuous kernels.
Schmidt proved the existence of the expansion in eq. for all square-integrable kernels and showed that the equality holds in the L sense (Schmidt 1907 He also proved that for continuous kernels K, if o > 0, the corresponding left and right singular functions can be selected as continuous. Later, in 1923, Hammerstein showed that the expansion in eq. (2) converges uniformly for any continuous kernel that also satisfies a contrived square-integrated Lipschitz-like condition (Ham- merstein 1923). Later, in 1938, Smithies gave finicky condition on continuous kernel that ensures specific decay rates of the singular values, and he used that decay to prove almost everywhere point- wise and almost everywhere absolute convergence (Smithies) 1938). More recently, was realized that both Hammerstein's 's and Smithies' conditions are satisfied by continuous kernels that are Lips- chitz continuous uniformly in each variable separably (Townsend) 2014).
We prove results for larger class of general continuous kernels K : b] x [c. + R than Lipschitz continuous kernels. We only need the kernels to have bounded variation uniformly each variable separately, i.e., for any fixed b) and any fixed E [c, d]. we have
J" 0 K ydd <V, Oz
[.
v) <V, Jy [6
K(
(3)
for some fixed uniform constant < 00. We say a kernel is of uniform bounded variation satisfies the conditions in eq. (3) The partial derivatives in eq. (3) are replaced by the notion of weak derivatives if the kernel is not differentiable (Trefethen) [011 Chap. 7). We also provide new decay bounds on a, for smoother kernels (see Section 4), which we believe are asymptotically tight, and can be used to rigorously truncate Mercer's expansion.
We prove new result that continuous kernels of uniform bounded variation have a Mercer's expan- sion that converges pointwise almost everywhere, unconditionally almost everywhere, and almost uniformly. We have not been able prove that the expansion converges pointwise, absolutely, and uniformly, so there could still be some subtleties in using Mercer's expansion for general kernels. However, we believe that continuous kernels of uniform bounded variation have a Mercer's expan- sion that converges pointwise, absolutely, and uniformly, and we hope later research will prove this.
1.1 OUR CONTRIBUTIONS
We generalize Mercer's expansion to a general continuous kernel, where the kernel may be indefinite or a asymmetric. The following two theorems summarize our main theoretical results about Mercer's expansion for general continuous kernels (see Section
Theorem. For any [a,b] C there are continuous symmetric indefinite kernels on [a, x [a, b] such that Mercer's 's expansion in eq. (2): (i) does not converge pointwise, (ii) converges pointwise but not uniformly, and (ii) converges pointwise but not absolutely.
Theorem. For any [a, b), [c, dl C R. let K [a, [c, d]
R be continuous kernel of uniform bounded variation (see eq. 3)). Then, Mercer's 's expansion of K in eq. (2) converges pointwise, unconditionally almost everywhere, and almost uniformly.
2

---

Published as a conference paper at ICLR 2025
The first theorem shows that Mercer's expansion for continuous kernel must be treated with significant care. However, our result resolve some of these subtleties for continuous kernels of uniform bounded variation. Bounded variation is a weak extra smoothness condition kernel, e.g.. any uniform Lipschitz continuous kernel (in each variable separably) is also of uniform prove new decay bounds the
continuous
main theorems, singular values on for smoother kernels (see Section 4). We also describe an efficient algorithm to compute Mercer's expansion in eq. (2) for general continuous kernels (see Section 5).
bounded variation. In addition to these
2
BACKGROUND: MERCER'S THEOREM FOR GENERAL KERNELS
In this section, we provide some background material on Mercer's theorem and review some of the literature's efforts extend Mercer's expansion to general kernels.
2.1 MERCER'S S THEOREM FOR CONTINUOUS SYMMETRIC POSITIVE DEFINITE KERNELS
Given continuous symmetric positive definite kemnel K, Mercer's theorem ensures the pointwise, uniform, and absolute convergence of Mercer's expansion K (Mercer 1909).
Theorem 1 (Mercer's theorem). For any [a, C R. ler ja, b) x b - be a continu- symmetric function. Suppose K is positive definite, i.e., Li.j=1 CeeK (11,,3)) 2z)) 2 0 for any Cis..., CN R and .......22. EN [a, b]. Then, there is set of continuous orthonormal functions InEN on (a, b) and corresponding positive real numbers x1 2 A2 2 ... > O such that
[. K(z, (y)ny = (n), DE [a.
Moreover, K has a series expansion given by
K(I, v) = Σ An un (x) a,y e Ja,
(4)
A=1
where the series converges pointwise, uniformly, and absolutely K.
Mercer's theorem is simple but powerful result showing that Mercer's expansion for continuous symmetric positive definite kernels can be used without any subtleties from an analysis perspective. In this setting, by spectral theory, λ1, A,..., are the positive eigenvalues of K with corresponding orthonormal eigenfunctions {
The convergence properties of Mercer's expansion are useful in integral operator theory (Stewart 2011]. For instance, if Mercer's 's expansion of K : [a, b] x [a, b] + R converges uniformly, one can interchange integration and the summation, i.e.,
S" K K(x, (z,,))(()dd
= Σ onvn(()) J. on (v))(
In particular, the integrals J e (y)dd do not depend on x, so 1ºd K(x, fy)(y can be com- puted efficiently using this formula. Moreover, the integral equation g(x) = K(x,) y))(y) with I unknown, can be easily solved by back substitution using Mercer's expansion (Schmidi 1907).
When Mercer's expansion converges uniformly, truncation error always bounded the uniform norm. This means that one safely truncate the series and use finite rank approximations of the kernel. On the other hand, Mercer's expansion does not converge uniformly, the uniform norm error between K and truncation may not converge zero the rank increases (see Section 3.3
Finally, when Mercer's expansion converges absolutely (or unconditionally), one can write the ker- nel in factored form, i.e., K UEVT. Writing function in a decomposition format like this has several advantages, as linear algebra algorithms immediately extend to the continuous setting (see (Townsend & Trefethen 2015)). Our result in Section 3.4 implies similar but weaker conclusion.

---

Published as a conference paper at ICLR 2025
2.2 PREVIOUS WORK ON INDEFINITE AND ASYMMETRIC KERNELS
There are several attempts to establish a theoretical framework for Mercer's expansions of indefinite and asymmetric kernels. One of the most popular attempts is the theory of Reproducing Kernel Krein Space (RKKS) (Alpay) 2001; Ong et al. 2004, Loosli et al.) 2015 Huang et al. 2017) for indefinite kernels. Here, kernel K needs to have so-called positive decomposition K (z. y) K (z. y)-K (r. y). where K and K_ are continuous symmetric positive definite kernels (which also required for the generalized Mercer's theorem in (Chen et al. 2008)). Another attempt is the Reproducing Kernel Banach Space (RKBS), which removes the inner-product requirement from an RKHS. It can be defined in several ways (Zhang al. 2009 Georgiev et al. 2013 Xu & Ye 2019
ei al. 2022), for example, the RKBS requires a semi-inner product in (Zhang et al. 2009 and a
L in (Georgiev et al. 2013).
Unfortunately, not all continuous indefinite kernels induce an RKKS, and not all continuous kernels induce an RKBS. Characterizing what properties kernel must have induce an RKKS or RKBS remains an open problem. For example, the continuous indefinite kemell Kabs in eq. 6 does not have a positive decomposition, so it does not define an RKKS. Likewise, there are continuous kernels for which Mercer's expansion does not converge pointwise (see Proposition and hence does not satisfy the conditions in (Xu & Ye 2019) to generate an associated RKBS.
Aside from reproducing kernel approaches, researchers have tried to generate feature spaces induced by indefinite kernels. Using pseudo-Euclidenn spaces, (Haasdonk) 2005) shows that SVMs are a sort of distance minimizer in such space, although it is not metric space. Other studies handle indefinite kernel learning by modifying problems to continuous symmetric positive definite kernel learning either by transforming the kernels themselves (Wu et al.) 2005) by finding nearby positive definite kernel (Luss & d' Assprmmott, (007). In fact, such modification may not be possible for some kernels (see, for example, proots of Propositions 2 [ thus careful rigorous analysis has to be entailed. We hope the theoretical underpinnings detailed in this paper can aid future attempts in these directions.
3 MERCER'S 'S EXPANSION FOR GENERAL CONTINUOUS KERNELS
We detail Mercer's expansion for continuous kernels and investigate its convergence behavior.
3.1 MERCER'S 'S EXPANSION
Consider a general continuous kernel K : [a, x [e. + R, where [a, [c, C R. If is symmetric, then the interval [c, d] will equal [a, bj. As hinted by the SVD for matrices, for general kernel K, we will need to consider two sets of functions: (1) Right singular functions denoted by U1 U2,..., which are orthonormal with respect to L b)) and (2) Left singular functions denoted by u1, o....., which are orthonormal with respect to [[e, d)) The functions are defined to satisfy
S K K(x, (v)dy,
Cx ( - 1." K (z, (x)d(r)
(x) (x) [
(5)
The values 0, 2 02
O are called the positive singular values of K. The SVE of K, which we refer to as Mercer's expansion, is given in eq. 2
The SVE of K is not completely unique. However, the convergence properties the same for any SVE of K. One can modify the left and right singular functions with signs and potentially reindex terms when singular values plateau. Moreover, the integral definition in eq. (5) allows the left and right singular functions to be modified on sets of measure zero. For continuous kernels, if a > O, we select u, and U, to be continuous, which Schmidi (1907) showed is always possible. With this convention, the SVE of K is equivalent to Mercer's 's expansion for continuous symmetric positive definite kernels.
IIf K is continuous, then the equality least holds in the f,2 sense.
4

---

Published as a conference paper at ICLR 2025
3.2 MERCER'S EXPANSION MAY NOT CONVERGE POINTIWSE
Given a continuous symmetric but indefinite kernel K [a, x [a, - R, Mercer's expansion in eq. (2) may not converge pointwise.
Proposition 1. For any (a, b] C R. there exists a continuous symmettrc indefinite kernel Kpr la, b] x (a, + E with a Mercer's expansion that does not converge pointwise.
Proof. We prove this by providing an example and, without loss of generality, we assume that b) = [-1,1]. Consider continuous even -prppooo function f [-Tt, T] + R whose
Fourier series does not converge pointwise at 0. Such a function exists, for example, f(t) = sin(2" _ - 1)t/2)/n2² Fejér 1911). Let f(t) = En=-x Cne =co +o En= 2c,, cos(nt) be the Fourier expansion of f(t), Le., Cn 2x J_x ((t)e dt. Now, consider Kp y) == f(x y)- Since f is -prriodic we find that for fixed y, we have S_, Kp((1, y)eine dx = 2 for n E Z. 2n cos(ny) and f", (2, y) sin(nx)d 0 by Eu- ler's formula. Since {cos nz MeN {sin næ meN form a complete orthogonal basis of L2 n, m)), we have the full set of eigenfunctions of Kpc. Thus,
We also have __ Kp (z. y) cos(nx)dz
cos(nar) 1 V
Kn((2, v) co
2T V
cos(ny) co 20n (os cos(ny);
where equality holds in the 2 sense. To conclude that the series does not converge pointwise, consider the expansion at y = O. We find that Kp((z;,) 0) co E 2c,, cos(ner) f(x). Since this is the Fourier series of f. we know that this series does not converge pointwise at O. We conclude that we have Mercer's expansion for Kp that is not pointwise convergent (0, 0). This example can be transplanted to have a domain (a, 6] x Ja, b] by a linear translation for any [a, 6] C IR
Since a general kernel may be indefinite, the example in the proof of Proposition Talso shows that Mercer's expansion may not converge pointwise for general kernels.
3.3 MERCER'S 'S EXPANSION MAY NOT CONVERGE ABSOLUTELY OR UNIFORMLY
For continuous kernel, Mercer's expansion might converge pointwise but not absolutely might converge pointwise but not uniformly. One must treat Mercer's ' expansion carefully for indefinite or asymmetric continuous kernels because its convergence properties can be subtle.
Proposition 2. For any [a, b] R there exists continuous symmetric indefinite kernel K (a, b] x [a, b] + IR with a Mercer's 's expansion that converges pointwise but not absolutely.
Proposition 3. For any [a, bj C R there exists a continuous symmetric indefinite kernel Kuni : (a, b] (a, b] IR with Mercer's expansion that converges pointwise but not uniformly.
We prove these two propositions in Appendix by finding kernels that possess Mercer's 's expansion with the desired propertics. a kernel has only a finite number negative (positive) eigenvalues, can subtract finite rank function from K to make it positive (negative) definite. This allows one to use the classic Mercer's 's theorem for continuous positive definite kernels, ensuring that Mercer's s expansion converges pointwise, absolutely, and uniformly. Thus, the kernels we search for must have an infinite number of both positive and negative eigenvalues.
For example, proof of Proposition
show that the following continuous kernel K [-1,1] x 1, + IR has a Mercer's expansion that converges pointwise but not absolutely:
(-1)² n²
Kabs (x, y)
Pon.))
(6)
where P,, is the degree n normalized Legendre polynomial (in the I sense), i.e., P,, = 2n+1 (x) The alternating signs in (-1)" in eq. (6) are essential to create a kernel with in- finitely many positive and infinitely many negative eigenvalues. See Appendix for details.
5

---

Published as a conference paper at ICLR 2025
3.4 ON THE CONVERGENCE OF MERCER'S EXPANSION
We now prove convergence results Mercer's expansion of continuous kemnels of uniform bounded variation (see eq. (3) for definition). Intuitively, a continuous function with bounded varia- tion does not have infinitely many oscillations with non-negligible variation. Almost all continuous functions that appear in practice are of uniform bounded variation. In particular, we believe that all the continuous kernels used in machine learning are of uniform bounded variation. Therefore, our extra smoothness requirement on continuous kernels is technical assumption needed for the analysis but not a restrictive condition practice.
We also remark that while Mercer's 's theorem holds for any compact domain, we only consider closed subsets of E in this work. However, any case, Propositions for Mercer's s theorem for general kernels on general domains. Mercer's theorem is special since the series has small amount of cancellation, thus the convergence does not rely on properties of orthonormal functions. However for general domains cancellation of orthonormal series has to be carefully examined, which a relatively less-known subject except for closed subsets of
[ too still serve as counterexamples
3.4.1 UNCONDITIONALLY ALMOST EVERYWHERE CONVERGENCE
We first prove a decay rate on the singular values. We use recent result in Waag 2023) to obtain bound of the coefficients Legendre expansion and then use Eckart- Soant-ooung--isss theorem for the SVE (Schmidi 1907 Eekart & Young. 1936; Mirsky 1960) to conclude Proposition _
Proposition For any [a. bl. [c, d] c: R. continuous kernel K [a, [c, dl of uniform
bounded variation (see eq. ( has o, =O(n as
oc.
A proof and discussion of Proposition 4 is given in Section 4 Proposition 4 tells us that the extra smoothness assumption on K leads to a faster decay of the singular values. For a general continuous kernel K [a, b) [c, d] IR, we can conclude that it is square-integrable that > of < This only allows us to conclude that an O(n 1/2), not on O(n The extra decay of the singular values allows us to show that Mercer's 's expansion convergence unconditionally almost everywhere. We prove a more general result (see Appendix for the proof).
Theorem 2 (Unconditional Convergence of Mercer's expansion). For any bl, [c, d] C R and continuous kernel K [a, b) x [c, - R with singular values satisfying on S Cn for some > 1/2 and some C' > 0, Mercer's expansion of K converges unconditionally almost everywhere.
To prove Theorem 2 we use the theory of orthonormal series (sce Lemma 3). which can be thought of as an extension of the Rademacher-MMenchov theorem. We immediately conclude the following result by combining Proposition 4 and Theorem 2
Corollary 1. Let (a, b), [c, d] C R.. Any continuous kernel K [a, b| (c, dI of uniform bounded
variation (see eq. 3h) has Mercer's expansion that converges unconditionally almost everywhere.
Corollary tellss that continuous kernels of uniform bounded variation have Mercer's expansion that converges almost everywhere, regardless of the order in which the terms are summed. Uncon- ditional almost everywhere convergence is closely related to absolute convergence. Unconditional almost everywhere convergence ensures that the expansion's 's convergence behavior is stable across the domain and that almost every point adheres to the same convergence properties. It is weaker than absolute convergence because there is possibly an exception set of measure zero.
One can also use Theorem to conclude that Mercer's expansions converge unconditionally almost everywhere under alternative smoothness assumptions. For example, all continuous kernels that are Hölder continuous uniformly in each variable separately, i.e., there a constant < oc and 7 > such that
K (II - K (I2, a)1 < Cl -22
[Ix,, v1) - K(x, v2)1 S Clyi y2l",
for all 11, 22, Vr, M/, y, have a Mercer's expansion that converges unconditionally almost every- where. This is because such kernels have the singular value decay o, I Cn --7, which can be proved by Theorem 12 of (Smithies) 1938) with the choice of p = 2.

---

Published as a conference paper at ICLR 2025
3.4.2 ALMOST UNIFORM CONVERGENCE
We now consider the uniform convergence of Mercer's expansion. We show that the expansion converges almost uniformly for continuous kernels with uniform bounded variation.
Definition 1. A sequence of functions fnnne called almost uniformly convergent on a measur- able set E for any c there exists set E, with measure smaller than such that the sequence {Jn Jnnn converges uniformly on EXE,
We obtain our second main convergence result as follows.
Theorem 3. With the same assumptions as Corollary 7 Mercer's expansion of K converges almost uniformly in y for almost every (fixed) and it converges almost uniformly in for almost every y-
Proof. From Corollary 1 for almost every (fixed) x, we have the unconditional convergence of Mer- cer's 's expansion for almost every y. Since unconditional convergence implies pointwise convergence, Egorov's 's theorem (Egoroff) 1911) tells us that Mercer's 's expansion converges almost uniformly for y, for almost every The two-dimensional almost uniform convergence property also follows from the fact that Mercer's expansion converges pointwisely for almost every (x, y) E [a, b] x [c, d]. O
The distinction between almost uniform convergence and uniform convergence subtle. Uniform convergence means that the expansion converges to limit so that the convergence rate is the same across the entire domain. In contrast, almost uniform convergence a relaxation by allowing ex- ceptional sets of arbitrarily small measure.
4 DECAY OF SINGULAR VALUES FOR SMOOTH KERNELS
Mercer's expansion is equivalent to the SVE of a kernel, and this means that if Mercer's expansion for K is truncated after & terms, then it forms a rank & kernel that is a best rank-k approximatior K in the T.2 sense (Schmidt 1907). Thus, singular value bounds help understand the approximation power of low-rank approximations (Reade 1983 Townsend 2014).
Recall that (1) is normalized Legendre polynomial of degree n. If [[]1,1] + ous function of bounded variation, then its Legendre expansion is given by
is a continu-
((x) = Σ on (x)), On = / [(x) [(x) Pn(x)ds,
n=
which converges absolutely and uniformly to f WWag 2023 Moreover, the L projection of f onto the space of polynomials of degree
precisely the truncation of this series, i.e., fb(()) =
Σ On (z)). When f is (r- ti-times continuously differenniable and its ,th derivative, f(r) has bounded variation, < co, then for any 1: > r 1, it holds that (Wang 2023
Thm 3.5)
V2V
|| - fa- Sn-illes
O(k (r+4((+))...
I(( 2) r 1)r+
One use eq. to bound the singular values of kernels defined on [-1,1] x [-1, using an analogous argument to that found in (Reade) 1983). If K (z, -) is (r - 1)-times continuously differentiable and its th derivative in æ has bounded variation, YokarttYoung-Mirkk theorem shows that k/ v) = K an Px()) satisfies
co, uniformly in y then the
2V (1) 1))
2 n=
<
K
K-ley
S max /2 k(( VE[-1,1]
Σ an (v) 0=
(Ie 1
2 A nonzero kernel K is rank-1 if it can be written as K(2, v) (y)))(y). A of rank-1 kernels is of
rank <
'Recall that say that K(x.)) -) is of bounded variation uniformly in y if the function x - K(x,, y) is of bounded variation for every y with the same constant V.
7

---

Published as a conference paper at ICLR 2025
10"
10"
maxy V - A4-1
max, 2 Enno an (w) L
10"
10
1
V - 02
mmm an (n)
10a
10
m
10"4
10"4
02
10
10a
10
10
10
5
10
15
20
25
30
35
40
46
50
Figure Singular value decay of two kernels defined [-1,1] [-1, 1}: (Lefft) K K(x,y) y)
max {0, 1 - |.| - [y]) and (Right) (xr y) = exp(-<x² + y )/200) max(0, (1 |0|| lvl)) The
bounds given by the truncated Legendre expansions can be tight, allowing one to determine the number of terms required in Mercer's s expansion to achieve a desired accuracy.
where the first inequality comes from the fact that error to K and the last inequality comes from eq.
Em of is the best rank- approximation
Since the singular values are indexed in non-increasing order, we have kozz En on Thus, for k r have
2h Em=k+1
o S
2V + + -))
T2k S Viikk - - 1)r
O (++)))
(8)
The same bound on holds if K(:,)) is (r time continuously differentiable and its Thh derivative in y has bounded variation V. uniformly in æ. By transplanting kernels defined on [a, 6] x [c, d]. the bounds in eq. (8) can be modified for kernels defined any domain. We believe the bounds in eq. (8) are asymptotically tight. reader can refer to Figure 2.4 (right) of (Townsend) 2014) for related numerical experiments.
When K is continuous with uniform bounded variation, we have r = and eq. ( shows that On O(n-1), which proves Proposition 4 The bounds in eq. (8) show us that the smoother kernel, the faster its singular values decay to zero. In practice, if a kernel has rapidly decaying singular values its Mercer's expansion can be truncated after small number of terms.
COMPUTING MERCER'S S EXPANSION FOR GENERAL KERNELS
We now describe an algorithm for computing Mereer's expansion of a kernel, which is described in (Townsend Trefethen, 2013) for computing low-rank function approximations. Here, we use the fact that is observed compute near-best low-rank function approximations (Toowssedd] 2014). It involves two main steps: (1) Forming a low-rank approximant using a pseudo-skeleton approxima- tion and (2) Compressing the approximant using a low-rank SVD (Bebendorf) 20088 Chapt. 1.1.4). This procedure can be much more efficient than sampling the kernel on a large grid and computing the matrix SVD. An algorithmic summary (and discussion on its complexity) can also be found in Figure 6.1 of (Townsend & Trefethen, 2013).
5.1 STEP 1: COMPUTING A
APPROXIMANT
In the first step, we compute a pseudo-skeleton approximation using Gaussian elimination with complete pivoting (GECP), which is an iterative procedure to approximate the kernel K K(x, y) sum of rank-1 I functions (Townsend & Trefethen] 2013). The algorithm is implemented the two- dimensional side of Chebfun (Driscoll et al. 20144). Similar algorithms called Adaptive Cross Approximation (Bebendori] 2000) and maximum volume pseudo-skeleton approximation (Goreinov
al. 1997)
8

---

Published as a conference paper at ICLR 2025
10"
ΙK K
10
30 -jz+t1 o3
10"
10
20
60 80
100
T
Figure 2: The kernel ((x, y) tanh(1 (10(00000))) (000y 1) [-1,1] [-1,1] Left: Step 1 of our algorithm
selects = 96 pivot locations (red dots). The algorithm densely samples K along 2R lines (blue lines) form its pseudoskeleton approximant. Right: The best L error compared to | Kr for 1 - S 96, where Kr is the rank < pscudoskeleton approximation of K. At R = 96, step of our algorithm terminates as it has pointwise approximated K' extremely high accuracy.
The algorithm starts by defining eo = K and finding an approximate location of a maximum abso- lute value of eo(2, y). rank-1 function approximation is constructed that interpolates K along the Zo and y = lines, i.e.
Ki (I, y) ea( ()) vo)
Co Co vo)
Then, we define the residual e = K - K1, and the process is repeated on e1 to form 62, and so on. After R steps, rank- R approximation is constructed that interpolates K along 2R lines. We stop the iteration when the residual error is below user-defined tolerance such as 10-5
To find approximate location of maximum absolute value, i.e., the pivot location, each step of the algorithm, we sample ej for j = 0, 1,..., on a coarse Chebyshev tensor grid of an adaptively selected size and select absolute maximum from that grid. In this way, only need to evaluate the kernel K on coarse grids, and K does not need to be densely sampled. At the end of step 1, we have constructed rank S R approximation, given by
KR(2, v) = Σ (z)
(9)
are the reciprocals of the pivot values, and dz(x)) Ej-1 (at, Mi- (xj- 1
where 0j =
and v (y) = e- ( y) are univariate functions. We represent Φj and th as Chebyshev expan- sions of an adaptively selected degree, which requires that K is densely sampled along 2R lines.
This first step is observed to compute near-optimal rank S. R approximation to kernels. In Figure use approximate K (z, y) tanh (00h(1000m) zy + 1) the domain [-1, 1] [-1, 1]. where decides that / = 96 is sufficient to approximation K to extremely high precision. More algorithmic details and experiments are given (Townsend & Trefethen 2013 Townsend 2014).
5.2 STEP 2: LOW-RANK SVD OF THE PSEUDO-SKELETON APPROXIMANT
After have computed rank R pseudo-skeleton approximation in step improve it by performing a low-rank SVD. The SVD decomposes K (R y) into sum of outer products of or- thonormal functions with singular values and gives accurate truncated Mercer's expansion of K. To do this, we write in the form K KR(x, v) = (x (Y) where
Cc
(xr) = [z)(z) (R(()), ((x) = (x)
dR(M), C=
CR.

---

Published as a conference paper at ICLR 2025
The procedure for computing the low-rank SVD of K involves the following steps, which is sentially a fast way to compute a Mercer's s expansion of a finite rank kernel:
Perform two QR decompositions of ((x) and (ty, using function analogue of Householder
QR (Trefethen 2010). We can write this QR decomposition (xx) (z) Ri and ('()))
Q"aah (y) where R1, R2 gxxx and the columns of Qlen (x) and Qrishi (y) are orthonormal functions.
Compute the SVD an R x R matrix formed by R = UEVT. Construct the final SVD-based approximation by combining the singular values and the orthonor- malized functions to form:
KR u) = Σ (,,us())os())
(10)
j=1
where oy...,, OR are the diagonal entries of E, uz(x) I Us,Q."(x), and vy(v)
ΣR Vaz VajQueen y)-
After we have formed eq. 10). we truncate the expansion down to R terms to give a Mercer's expansion of K truncated after terms. Then, this final approximation not only compresses the pseudo-skeleton approximant from step and ensures that the resulting representation is very close to optimal rank < k approximation with respect to the L norm.
a rank- R approximation of is computed and each slice needs to be evaluated ((n) times, then the cost of GECP and compression is about ORR2n + R²) operations. If we discretize first and then compute the discrete SVD, the cost would be ((n3) operations.
CONCLUSION
We derive new examples of kernels show that the convergence properties of Mercer's expansion can be subtle for continuous kernels that are not symmetric positive definite. In particular, continuity alone is not enough guarantee that kernel has Mercer's expansion, which holds pointwise. We then prove that any continuous kernel with uniform bounded variation has a Mercer's expansion that converges pointwise almost everywhere, unconditionally almost everywhere, and almost uniformly. We derive new bound on the decay of singular values for smooth kernels and also provide an efficient algorithm for computing Mercer's expansion.
7
ACKNOWLEDGEMEENT
The second author was supported by the SciAl Center, funded by the Office of Naval Research under Grant Number N00014-23-1-2729 and NSF CAREER (DMS-20k) (0MS-2045646).
REFERENCES
Daniel Alpay. The Schur algorithm, reproducing kernel spaces and system theory. American Math- ematical Soc., 2001.
Mario Bebendorf. Approximation of boundary element matrices. Numerische Mathematik, 86:
565-589, 2000.
Mario Bebendorf. Hierarchical matrices. Springer, 2008
De-Gang Chen, Heng- Heng-You You Wang, and Eric CC Tsang. Generalized Mercer theorem and its applica- tion to feature space related to indefinite kernels. In 2008 International Conference on Machine Learning and Cybernetics, volume pp. 774-777. IEEE, 2008.
Yingyi Chen, Qinghua Tao, Francesco Tonin, and Johan Suykens. Primal-attention: Self-attention through asymmetric kernel SVD in primal representation. Advances Neural Information Pro- cessing Systems, 36, 2024.
10

---

Published as a conference paper at ICLR 2025
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273-29) 1995.
DLMF. NIST Digital Library of Mathematical Functions, https:://dmmm gov/ Release 1.2.1 of 2024-06-15. F. W. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F.
Boisvert, W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
Tobin A Driscoll, Nicholas Hale, and Lloyd N Trefethen. Chebfun guide, 2014.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- frika, (3):221-2188) 1936.
Dmitri Fyodorovich Egoroff. Sur les suites de fonctions mesurables. CR Acad. Sci. Paris, 152: 244-246, 1911.
Arthur Erdélyi, Wilhelm Magnus, Fritz Oberhettinger, Francesco G Tricomi, and Harry Bateman. Higher transcendental functions, volume McGraw-Hill New York, 1953.
Léopold Fejér. Sur les singularités de la série de Fourier des fonetions continues. In Annales scientifiques de l'École Normale Supérieure, volume 28, pp. 63-104, 1911.
Pando G Georgiev, Luis Sánnhez-Gonzzälez, and Panos M Pardalos. Construction of pairs of re- producing kernel Banach spaces. In Constructive Nonsmooth Analysis and Related Topics, pp- 39-57. Springer, 2013.
Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley. Reproducing kernel Hilbert space, Mercer's theorem, eigenfunctions, Nyström method, and use of kernels in machine learn- ing: Tutorial and survey. arXiv preprini arXiv:2106.0844 2021.
Sergei Goreinov, Eugene E Tyrtyshnikov, and Nickolai L Zamarashkin. A theory of pseudoskele- ton approximations. Linear Algebra and its Applications, 261(1-3):1-21, 1997.
Uffe Haagerup and Henrik Schlichtkrull. Inequalities for Jacobi polynomials. The Ramanujan Journal, 33(2)227-2246, 2014.
Bernard Haasdonk. Feature space interpretation of SVMs with indefinite kernels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(4):482-492, 2005.
Bernard Haasdonk and Daniel Keysers. Tangent distance kernels for support vector machines. In 2002 International Conference on Puttern Recognition, volume 2, pp. 864 868. IEEE, 2002.
Hammerstein. Über die entwickelung des kernes linearer integralgleichungen nach eigenfunktio- nen. Sirzungsberichte Preuss. Akad. Wiss, pp. 181-184, 1923.
B Hassibi, AH Sayed, and T Kailath. Indefinite-quadrate estimation and control: A unified approach to H² and H Theories. STAM Philadelphia, 1999.
Mingzhen He, Fan He, Lei Shi, Xiaolin Huang, and Johan AK Suykens. Learning with asymmetric kernels: Least squares and feature interpretation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(8): 10044-00054, 2023.
Xiaolin Huang, Andreas Maier, Joachim Hornegger, and Johan AK Suykens. Indefinite kernels in least squares support vector machines and principal component analysis. Applied and Computa- tional Harmonic Analysis, 1321) 2017.
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. arXiv preprint 187 2018.
Boris Sergeevic Kashin and Artur Artushovich Saakyan. Orthogonal series, volume 75, American Mathematical Soc., 2005.
Tom Koornwinder, Aleksey Kostenko, and Gerald Teschl. Jacobi polynomials, Bemstein-type in- equalities and dispersion estimates for the discrete Laguerre operator. Advances in Mathematics, 333:796-821, 2018.
11

---

Published as a conference paper at ICLR 2025
Sun Yuan Kung. Kernel methods and machine learning. Cambridge University Press, 2014.
Rong Rong Lin, Hai Zhang Zhang, and Jun Zhang. On reproducing kernel Banach spaces: Generic definitions and unified framework of constructions. Acta Mathematica Sinica, English Series, 38 (8):1459 1483, 2022.
Gaälle Loosli, Stéphane Canu, and Cheng Soon Ong. Learning SVM in Krein spaces. IEEE Trans- actions Pattern Analysis and Machine Intelligence, 3866):104-2) 2015.
Ronny Luss and Alexandre d' Aspremont. Support vector machine classification with indefinite kernels. Advances in Neural Information Processing Systems, 20, 2007.
James Mercer. XVI. Functions of positive and negative type, and their connection the theory of integral equations. Philosophical Transactions of the Royal Society of London. Series A, 209 (441-458):415-446 1909.
Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The Quarterly Journal of Mathematics, 11(1):50-59, 1960.
Cheng Soon Ong, Xavier Mary, Stéphane Canu, and Alexander Smola. Learning with non-positive kernels. In Proceedings of the Twenty-firs International Conference on Machine learning, pp. 81, 2004.
JB Reade. Eigenvalues of positive definite kernels. SIAM Journal on Mathematical Analysis. 14(1): 152-157, 1983.
Hiroto Saigo, Jean-
Jean-Philippe Philippe Vert, Nobuhisa Ueda, and Tatsuya Akutsu. Protein homology detection using string alignment kernels. Bioinformatiis, 20(1 (1111)668-1169) 2004.
Erhard Schmidt. Zur theorie der linearen und nichtlinearen integralgleichungen. Mathematische Annalen, 63(4):433-477 1907.
Bernhard Scholkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Frank Smithies. The eigen-values and singular values of integral equations. Proceedings of the London mathematical society, 2(1):255-279) 1938.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science Business Media, 2008
Gilbert W Stewart. On the early history of the singular value decomposition. SIAM Review, 35(4): 551-566, 1993.
Gilbert W Stewart. Fredholm, Hilbert, Schmidt: Three fundamental papers on integral equa- tions. translation with commentary. 2011. URL htttps://sseree umwacs. umd. edu/ "stewazt/FHs.pcr
Gabor Szego. Orthogonal polynomials, volume 23. American Mathematical Soc., 1939.
Alex Townsend. Computing with functions in two dimensions. PhD thesis, Oxford University, UK, 2014.
Alex Townsend and Lloyd N Trefethen. An extension of Chebfun two dimensions. SIAM Journal on Scientific Computing, 35(6))C45-CC518 2013.
Alex Townsend and Lloyd N Trefethen. Continuous analogues of matrix factorizations. Proc. Roy. Soc. A, 471((173)::01 40585, 2015.
Lloyd N Trefethen. Householder triangularization of a quasimatrix. IMA Journal of Numerical
Analysis, 3084) 2010.
Lloyd N Trefethen. Approximation theory and approximation practice, extended edition. SIAM, 2019.
12

---

Published as a conference paper at ICLR 2025
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances Neural Infor- mation Processing Systems, volume 30. Curran Associates, Inc., 2017.
Jean-Philippe Vert, Hiroto Saigo, and Tatsuya Akutsu. Local alignment kernels for biological quences. Kernel methods in computational biology, pp. 131-154, 2004.
Haiyong Wang. New error bounds for Legendre approximations of differentiable functions, Journal of Fourier Analysis and Applications, 29(4):42, 2023.
Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differen- tialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen, 7 41(4):44 1912.
Matthew A Wright and Joseph E. Gonzalez. Transformers are deep infnite-dimensional non-Mercer binary kernel machines. arXiv preprint arXiv:2106.015500 2021.
Gang Wu, Edward Chang, and Zhihua Zhang. An analysis transformation on non-positive semidefinite similarity matrix for kernel machines. In Proceedings of the 22nd International Conference on Machine Learning, volume 8. Citeseer, 2005.
Yuesheng Xu and Qi Ye. Generalized Mercer kernels and reproducing kernel Banach spaces, vol- ume 258. American Mathematical Society, 2019.
Haizhang Zhang, Yuesheng Xu, and Jun Zhang. Reproducing kernel Banach spaces for machine learning. Journal of Machine Learning Research, 10(12), 2009.
A INDEFINITE KERNELS WHOSE MERCER'S ' EXPANSION CONVERGES POINTWISE BUT NOT ABSOLUTELY OR UNIFORMLY.
In this section, prove that Mercer's expansion converge pointwise, but not absolutely, and may converge pointwise, but not uniformly.
A. A MERCER'S 'S EXPANSION THAT CONVERGES POINTWISE, BUT NOT ABSOLUTELY
We begin by proving that for any Ja, bj C E there exists a symmetric indefinite kernel Kass |a, b] x [a, b] + IR with a Mercer's expansion that converges pointwise, but not absolutely.
Proof of Proposition 2 Without loss of generality, we assume that [a, bj = [-1, 1]; otherwise, we can transplant the example below have this domain. Consider the kernel Kats [-1, x]x [- RR (also defined in eq. (6)):
(-1)a n²
Kabs (x, 3)
Pen Pzn()))
(11)
where P., is the degree normalized Legendre polynomial. First, we show that the expansion in eq. 111 converges pointwise so that the value of Kata (xx y) is well-defined. Recall that Bernstein's inequality for (), says that
2
[x(x))
<
n 2 O.
(1 22)1/41
Furthermore, [p.( S / + 1/2 for x E [-1, 1] (see DLMF 18.14.4) with X = 1/2). Con- sider any closed set S = [a, 6] x [-1, with -1 < < < and let M = v maxxe
-2/11 Then, [v)) < M for any 2 0 and y [a, b]. Thus, for any (z, v) E S, we have
1)"
n 1/2
Σ
P.n (x)
< M
< 00,
n²
n2
n=
13

---

Published as a conference paper at ICLR 2025
which, by the Weierstrass M-test, implies that the series in eq. converges absolutely and uni- formly on a. b] x [-1,1], Similarly, the series converges absolutely and uniformly on [-1, [. x (a, b) for any -1
b < 1. Consequently, we have pointwise convergence of the series in eq. [1] and continuity of K everywhere except possibly at the four corners (+1, +1). To check that the series converges pointwise at the four corners, note that P2n (+1) 2 + 1/2 so
Kanc (+1, = Σ (-1)a n² 212 v 2n + 1/2
2 ++++ 2n
Σ (-1)
n=
which is an alternating series that converges. Thus Kan (2, y) is well-defined pointwise by its ex- pansion for any (I, y) E 1, [-1,1].
To prove that Kass is continuous at (1), we prove that Rana (, -> (-1) P2n (x) (2) (v) is continuous the four corners. This suffices Kabs and K only differ by continuous function. Moreover, by symmetry, continuity at (1,1) guarantees continuity at all four corners.
Let us first prove the continuity of Kans along the edge 12 1] x {1}, which will be useful. For any (I, u) on [ 1] {1} we have
(-1)
Kaba (I, 3)
Pan -
Using the generating function of Legendre polynomials
Szego 1939), we find that
00
Pa(x)e"
x E 1-111.
tv1 12 2rt
n=1
Integrating both sides against from 0 to we see that
1 - 2xt -
!) dt log
4(x - v 8² 28x
8
t"
(r()).
(1 x1 + v1 + 82 28z)
n
We now do the substitution s multiply by and take the real part, obtain
(1+ log (1 2z) 21) (
(-1)" Pan(2)) = G(x),
(12)
for x 12. The left-hand side is smooth function, which proves the continuity of G(x) [1. 1). particular, we have the continuity of (zz) at 1.
on
Using the product formula for Legendre functions (Erdélyi et al. 1953 $3.15, eq. (20))
1 -
( Pzn ry + cos 01 x²)(1 x3)(1- d0,
(2)(
we have
Kana (x, 1)
Σ
00
(-1)"
Pan ay cos -1-1)) - y2)) do (21
117
0
n=1
1
G (ay + cos 0 12) d0,
by eq. 12). (We can interchange the integration and summation due to uniform convergence of G on la, C (-1,1) 1).) Note that æy + cos 0 [² y²)) 1 by the Cauchy-Schwarz inequality. From the mean value theorem and continuity of G. for any x; y sufficiently close to 1, we have some
2 E [ry- v(1 x²)(1 - --) xy + (1-x1)( y² such that
(-1)" (an = G(z).
Σ
14

---

Published as a conference paper at ICLR 2025
As æ, + 1, the interval ry V(1 =2) xy + v x²) -y²) shrinks down to
and + 1. By the smoothness of G, conclude that Σ (-1)" P2 P2n (v) is continuous (1,
Finally show that eq. have
(11 does converge absolutely, consider the point (x, y) (1, 1).
We
Σ
E|
Pa (1)
Σ
n 2n 2m + 1/2 2 + 1/2
2n +
n²
n²
n=
which does not converge.
The kernel Kabs tells us that the convergence of Mercer's expansion can be subtle for general con- tinuous kernels.
A.2 A MERCAR'S 'S EXPANSION THAT CONVERGES POINTWISE, BUT NOT UNIFORMLY
We now prove that for any (a, bj R there exists symmettii indefinite kernel Kuii [a, b] [a, b] with a Mercer's 's expansion that converges pointwise, but not uniformly. This section contains a proof Proposition 3
Without loss of generality, we assume that (a, b] = [-11 11, otherwise, we can transplant the example where Un is the degree Chebyshev polynomial of the second kind. Note that {Ū, Jee is an orthonormal set of polynomials with respect the standard 1,2 inner-product [-1, Also, Ün(-1) (1) 0 and Ü, is continuous.
below to have this domain. First, define (x) ==
We now divide [-1, 1] into infinite number of disjoint subintervals I1, ......, defined by
12 n-
12 n π
In
Σ
7
j=1
1=1
which designed so that length(In)) vals, define un for all E N, as
an? while Σx length (Ta) 2. Using these subinter-
mm
Uzm (Im (x)),
if = 2m -
(x)
min U 22m+2(mm (x)), if n 2m
(13)
V6
where im : mm + (-1, 1] is linear bijection (shift) from Im onto [-1, The functions U1, 02 are orthonormal ([-1,, 1]) and Un vanishes outside of Lm.
We now consider the kernel Kuni
1- + IR given by
00
(-1)a
Kuni (I,
Σ
Un (x)un))))
(14)
The kernel Kuni is continuous, symmetric, and has an infinite number of positive and an infinite number of negative eigenvalues. Also since {Un heN is orthonormal set, eq. (14) is Mercer's expansion for Ku turns out that this expansion does not converge uniformly to Kuni
Remark 1. The singular values of Kam in eq. are 1 I. which have a decay rate of of as n > 00.
To prove Proposition 3 we introduce two useful lemmas about the functions U,.. Lemma (Uniform norm bound of Ü.). For any N we have
2n Vn < | llx S /4(n + 1)x-1 where [| oloo is the absolute maximum value of Ü, (1) for E [-1,1].
15

---

Published as a conference paper at ICLR 2025
Proof. With the change of variables cos for A E [0, x], find that
V
T ([(())== sin(n 1)8
vsin
This means that we have
sin zz
2n
" Un(en) sin 2(n-1) 1]
1n+ V
π
π
for Jn = co8 I[++J] using sin( < &nn This proves the lower bound on ||0n||o0.
To prove the upper bound, first consider
n+1 to see that
sin(n + 1)0
(n+ + 1)0
v0/2 < 2 + +1) < 2 1),
Vsin
using 2 < sin 0 for 0 [0, x/ For a+l 0 S x, have
sin(n + 1)0
2 g 22
S V
Vsin 0
vsin A
Finally, the upper bound on || holds since [U,(- = (x)).
Lemma 1 is a weaker version of Bernstein-type bound for Chebyshev polynomials of the second kind. Recall that the Chebyshev polynomials of the second kind are the Jacobi polynomials with pa- rameter (). For Jacobi polynomials with integer parameters, similar bound is known (Haagerup) & Schlichtkrul] 2014), while it is discussed only numerically so far for Jacobi polynomals with noninteger parameters (Koornwinder et al. 2018 Remark 4.4).
Lemma (Sum of Consecutive (- (-1)" For any n E N, we have
U2n (x) - (2
V8
Proof. Using the trigonometric definition of Ün. we have
π
(2m((2) U2m+2(x)) sin((2m + 1)0) sin (2m + 3)0)
2
Vsin 0
2 2-22ccmmmmmmm 2)i)
which gives the desired inequality.
Lemma 2 shows that if one adds two consecutive terms from ((-1)* (x)) JuE,, the norm of the resulting function is bounded by a constant, whereas Lemma] states that each term on its own has norm least O(yn). In other words, there will be significant pointwise cancellations happening everywhere in Mercer's expansion for Kuni in eq. (14).
We ready to prove Proposition 3 by giving an explicit example of symmetric indefinite kernel with pointwise convergent Mercer's 's expansion that does not converge uniformly.
First, notice that from the definition of Un and (u, 3), there are at most two nonzero terms the series for each fixed x, [-1, 1]2 If m an integer such that I then Kuml (z. y) = 0 if & Tm; otherwise, for y E Tm. we find that
Proof of Proposition 3
1
Kuni u)
m3 (U2m (U2m-1 (x))2m ( + v2m (2)(2)) U2m (y))
1
m
(2m+z2im
(w)) - Cmm (im (15)
m
6
16

---

Published as a conference paper at ICLR 2025
which converges for every 2, y. For any y, in ([-1,1] x (11, 1] x [b, 1]) with < the expansion in eq. (14) is a finite sum, which converges uniformly and Ku continuous on [-1,1|x[-1, except possibly at the point (z, (1, 1) the functions {2a JeeN are continuous.
To prove continuity at the upper right corner (1, 1), consider small open set B around (1, 1). For any 2, y E B suppose x. y m- Letting x' im (2), in (v) and from eq. (15) we have
n²2 Kuni (z, y) 6m
(Uemt2(o') (22((()) U2m+2(1))
+ U2m(1)) (x') (U2m+2(0') U2m (v)))
By Lemma 2 the terms U2m+2(a') - U2m(2* and U2 23y) U2m(1') are bounded above by 2 a and U2m+2, U2m are both bounded above by v(mm 12)/TT. Thus obtain
2 6m V
π²²
8m - 12 < Cm 11/2
Kuni (z), v)1 S
2
where C does not depend on As B gets smaller, we have z, + 1, which implies m
Hence, limit the value of Kuni (2r, y) as (x. y) - (1, 1) is zero, which equal to Kuni (1, 1), proving the continuity of Kuii at 11. Altogether, find that Kui is continuous
[-1, x [-1,1].
For the final step, let us prove that the convergence eq. (66 is not uniform. The norm of (2m) th
term of the right-hand side of eq. [4 is bounded below by
m²=²
2
2
max 11
122 (22m (2) (y)
2m
m
m3
3
using the lower bound of Ü2m42 obtained in Lemma any (2m)th term, it can be deduced from the Cauchy condition that the series does not converge uniformly.
Since this constant lower bound holds for
The following proposition gives an additional example of continuous asymmetric kernel where its SVE converges pointwise but not uniformly. Once more, we use the functions {v,} defined in eq. (13).
Proposition 5 (Asymmetric kernel with Mercer's expansion that does not converge uniformly). Define Kas [-1, [- -
R
Kas (x
Un (z)
(16)
with un = U2n and Un defined in eq. (3). Then, Kas is a continuous function which is well-defined for all (ur,y) [-1, 11,, Moreover, the right-hand side of eq. (16) is Mercer's expansion of Kas which does not converge uniformly.
We omit the proof as it is analogous to that of Proposition
B ON THE CONVERGENCE OF MERCER'S 'S EXPANSION FOR CONTINUOUS KERNELS OF UNIFORM BOUNDED VARIATION
For any (a, b). [c, d C TR and continuous kernel K [a, [c, d] + IR with uniform bounded variation (see eq. (3)), we prove that Mercer's expansion of K converges unconditionally almost everywhere.
To show this, we first give the following lemma, which generalization of the Rademacher- Menchov Theorem.
Lemma 3 Kashin & Saakyan 2005), Chapter VIII.2.. Let (0x(x) be a set of orthonormal functions and {an EREN be set of coefficients. If 01 ag.... satisfy En |a, 12-r for some O then the seriey Ex0 (n),(() converges unconditionally almost everywhere.
17

---

Published as a conference paper at ICLR 2025
Lemma allows us prove that Mercer's expansion, i.e.,
( v) = Σ on
converges unconditionally almost everywhere for continuous kernels of uniform bounded variation.
Proof of Theorem 2
Let
By Hölder's inequality the following inequality holds for any å > 0:
Un (x))2-2)
Σ
onn (lo,l [lon|2-c-(luu
(xn(2))
n=1
x=1
(lom18)3 15)2))
(x))))-))
(17)
The first term (E==) 0n
converges when
25 >
(18)
while the second term can be written as
3
Σ (1om1 (( (x)
1-2r-26 (x))
2
Integrating the sum inside the parenthesis with respect x, find that
2-2e-2
Jun 2x =
Σ
(L Jaal
4-2e-26 a-e |un(z))
Σ
[o
4-2c-28
2-c
n=1
m=1
provided that the right-hand side converges, i.e.,
4-2c 25 2 E
1.
(19)
In this case, we have a monotonic series of functions given by
fa(=)= Σ |o,l 20_ un, (x)1²
which converges in the T,- sense. Since we have I,1 convergence, we know that the second term of eq. (17) converges pointwise for almost every x.
From the assumption that we have satisfied by selecting 8, such that 8 > > 0 and
2, the two conditions in eq. and eq. 19 are both
8 2a -
(There is always solution when > as one can take =
2a and = min (0.001, 5/2).)
Thus, for any given a > 1 there is d, > such that eq. 17 converges for almost every x.
From Lemmal) we see that Ene on (w) ce)c,, (v) converges unconditionally for almost every x and almost every y.
18


Reviews:
[{"review_id": "PCeZJqBmB2", "reviewer": "Reviewer_VyrL", "summary": "This paper extended  Mercer’s theorem to any continuous kernels with bounded range, removing the original requirement for the kernel function to be symmetric and positive definite. Two main results are derived in this paper: first, it is proven that Mercer's expansion may not converge absolutely and uniformly for indefinite kernel; second, it is proven that a kernel with uniform bounded variation has Mercer's expansion that coverges pointwise a.e., a.u. and unconditionally a.e.. Notably, the authors described an algorithm for computing Mercer's expansion for general kernels.", "questions": "The present results apply only to kernel functions defined on product intervals, specifically  $K: [a,b]\\times [c,d]\\to R$.  My question is whether by following a similar argument as that in your manuscript, these results could be extended to more general settings, such as compact domains or multiple dimensions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analysis in this paper is comprehensive and rigorous.\n\n2. The paper establishes a theoretical foundation for Mercer’s expansion applied to non-regular kernels, such as indefinite and asymmetric kernels, potentially offering fundamental tools for future research in the theory of kernel-based method.\n\n3.  A sufficient condition of uniformly bounded variation is proposed to ensure the validity of Mercer’s expansion.", "weaknesses": "The parameter $\\alpha$  first appears in Theorem 2 (maybe I missed something)  before it is introduced (in Line 303). I suggest the authors make the writing more self-contained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "iOmcZzkCxH", "reviewer": "Reviewer_nauL", "summary": "This manuscript studied the Mecer's decomposition for indefinite and asymmetric kernel. \n\nThey extend Mercer's expansion to continuous kernels, providing some theoretical underpinning for indefinite and asymmetric kernels. \n\n1. Mercer's expansion may not be pointwise convergent for continuous indefinite kernels, \n2. Prove that the expansion of continuous kernels with bounded variation uniformly in each variable separably converges pointwise almost everywhere, almost uniformly, and unconditionally almost everywhere.\n3. Describe an algorithm for computing Mercer's expansion for general kernels and give new decay bounds on its terms.", "questions": "Same as the weakness. Especially the application consideration of the asymmetric kernel/", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors claim to have established some fundamental results for ``Mercer's decomposition'' for indefinite, asymmetric kernels.\n\nThe following points seem novel to me:\n\n1. It is generally expected that ``Mercer's decomposition'' does not behave well when the kernel \\( K \\) is not positive definite and asymmetric. The authors provide several examples of this behavior:\n   - 1. It does not converge pointwise.\n   - 2. It converges pointwise but not absolutely.\n   - 3. It converges pointwise but not uniformly.\n\n2. They demonstrate that if the decay rate of the singular values is sufficiently fast and there is some smoothness condition on the kernel, there are some unconditional convergence results.\n\n3. They assert that the smoother the kernel, the faster the decay rate of the singular values.", "weaknesses": "The concern regarding the mathematical novelty of this paper is that most of the results in this manuscript are anticipated.\n\nSince it is not fair to judge an ICLR paper solely based on its mathematical novelty, it would be beneficial if the authors could explore the necessity of studying Mercer's decomposition for indefinite, asymmetric kernels more thoroughly.\n\n1.Could the authors discuss why the utilization of asymmetric kernels is necessary in data analysis?\n2.Could the authors provide examples of several classes of asymmetric kernels of general interest?\n3.Are there any application examples that demonstrate the use of asymmetric kernels?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Pci2BNAqwx", "reviewer": "Reviewer_5Zo5", "summary": "This paper shows that if an asymmetric and non-positive definite kernel satisfies the uniform bounded variation property on the two coordinates (Eq. (3)), then it admits a Mercer decomposition which converges pointwise, unconditionally almost everywhere, and almost uniformly. Also, the paper provides an algorithm on computing Mercer expansion for general kernels.", "questions": "1. Could the authors explain why they did not extend the main theorem to kernels with high-dimensional compact input spaces?\n2. I am not very familiar with but interested in computing/approximating Mercer extension of a general kernel. Is the procedure in section 5 novel or is it a standard approach in the literature? If it is novel, it is worth to explain more on the algorithm's complexity and accuracy. \n3. In line 639 \"We believe the bounds in eq. (8) are asymptotically tight.\" Do you have any experimental results with general asymmetric kernels to support your hypothesis?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is written in a rigorous manner where the proof of the main theorem is stated clearly in the appendix. Also, the authors explain the importance of this paper as filling the gap in the literature on general asymmetric and non-positive definite kernels.", "weaknesses": "However, the contribution of the paper seems limited. The kernel needs to be defined on two (different) intervals in the theorem, which is too simple for practical implications. And the proof of the main theorem is more or less the result from Rademacher–Menchov Theorem and Hölder inequality. I think that the authors could have extended the proof to kernels with high-dimensional compact input spaces, or explain why it is difficult to perform such an extension.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)