Spectral Truncation Kernels: Noncommutativity in $C^*$-algebraic Kernel Machines

## Abstract

Abstract C ∗ superscript 𝐶 C^{*} italic_C start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT -algebra-valued kernels could pave the way for the next generation of kernel machines. To further our fundamental understanding of learning with C ∗ superscript 𝐶 C^{*} italic_C start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT -algebraic kernels, we propose a new class of positive definite kernels based on the spectral truncation. We focus on kernels whose inputs and outputs are vectors or functions and generalize typical kernels by introducing the noncommutativity of the products appearing in the kernels. The noncommutativity induces interactions along the data function domain. We show that it is a governing factor leading to performance enhancement: we can balance the representation power and the model complexity. We also propose a deep learning perspective to increase the representation capacity of spectral truncation kernels. The flexibility of the proposed class of kernels allows us to go beyond previous commutative kernels, addressing two of the foremost issues regarding learning in vector-valued RKHSs, namely the choice of the kernel and the computational cost.

## 1 Introduction

Kernel methods have been
one of the most fundamental tools
in machine learning (Schölkopf & Smola, ; Gretton et al., ; Hofmann et al., ; Muandet et al., ).
They have been applied, for example, to
ridge regression, principal component analysis, and support vector machine.
Kernel methods are characterized by reproducing kernel Hilbert spaces (RKHSs), which are constructed by positive definite kernels.
Typical positive definite kernels include the polynomial kernel, Gaussian kernel, and Laplacian kernel.
Product kernels, which are constructed by the product of multiple kernels, have also been considered (Schölkopf & Smola, ; Thomas, ).

Standard positive definite kernels are scalar-valued, and are well-suited to learn scalar-valued functions.
Kernel methods for vector- and function-valued outputs have also been investigated (Álvarez et al., ; Kadri et al., ). The kernels, in these cases, are instead operator-valued, and the associated feature space is vector-valued RKHSs (vvRKHSs) (Kadri et al., , ; Minh et al., ).
There are at least two challenges for vvRKHS methods: the computational cost and choice of kernels.
A typical kernel is the separable kernel, which is defined by the product of a scalar-valued kernel and a positive semi-definite operator (Álvarez et al., ).
Although applying the separable kernel is computationally efficient, it identifies dependencies between input and output variables separately, and cannot reflect information of input variables properly to output variables.
Several attempts have been made to construct kernels that go beyond separable kernels.
Huusari & Kadri () proposed entangled kernels based on concepts from quantum computing, such as partial trace and entanglement.
Hashimoto et al. () proposed to use the product of circulant matrices and general squared matrices to construct kernels.
Using this kernel, one can generalize the convolution and capture the effect of interactions of different Fourier components.
However, if we need an $m$-dimensional vector-valued outputs with nonseparable kernels, then we have to construct an $mN$ by $mN$ Gram matrix, where $N$ is the sample size, and the computational cost is $O(m^{3}N^{3})$ in general.
Thus, with vvRKHSs, we cannot resolve the two issues at the same time.

In this work, we address these two challenges by introducing a new class of kernels based on the framework of reproducing kernel Hilbert $C^{*}$-module (RKHM) (Hashimoto et al., ).
RKHM is a generalization of RKHS by means of $C^{*}$-algebra.
$C^{*}$-algebra is a generalization of the space of complex values and has structures of the norm, product, and involution (Murphy, ; Lance, ).
It unifies operators and functions.
In this framework, kernels are generalized to $C^{*}$-algebra-valued kernel functions and allow us to consider function-valued kernels, leading to function-valued Gram matrices.
By evaluating the values of the function-valued Gram matrix at $m$ different points, we obtain $m$ scalar-valued Gram matrices.
This allows us to obtain an $m$-dimensional vector-valued outputs with the computational cost of $O(mN^{3})$, which alleviates the dependency on $m$ from cubic
to linear compared to the case of vvRKHSs with nonseparable kernels.

To obtain kernels going beyond the separable kernels, we propose a new class of $C^{*}$-algebra-valued positive definite kernels based on the spectral truncation, which has been discussed in the fields of noncommutative geometry and $C^{*}$-algebra (D’Andrea et al., ; van Suijlekom, ; Connes & van Suijlekom, ).
Our class of kernels is large and encompasses previous commutative kernel functions such as polynomial, product, and separable kernels.
The proposed kernels are parameterized by a natural number $n$ corresponding to the dimension of the truncated space.
They can be applied to both vector and functional inputs.
For vector inputs, we regard the elements of them as the values of functions.
We approximate the input functions on the $n$-dimensional truncated space and obtain $n$ by $n$
Toeplitz matrices, whose $(i,j)$-entry depends only on $i-j$.
Thus, $n$ describes the resolution of the discretization, and we call it the truncation parameter.
We show that the proposed kernels converge to the commutative kernels as $n$ goes to infinity.

In the setting of functional data (Jim Ramsay, ; Wang et al., ; Hashimoto et al., ), the proposed truncation kernels shed light on the good effects of discretization (setting $n$ as a finite number) on the learning process.
The truncation parameter $n$
plays an important role from at least two perspectives.
First, an important structure in typical commutative kernels is the product, and $n$ describes the noncommutativity of the product.
For two functions $a$ and $b$, their product $ab$ is defined as just the pointwise product of each value, i.e., $ab(z)=a(z)b(z)$, and the product is commutative, i.e., $ab=ba$.
Therefore, we cannot capture the relationship between $a(z_{1})$ and $b(z_{2})$ for $z_{1}\neq z_{2}$ with this product.
This situation corresponds to the case of $n=\infty$.
On the other hand, the product of two Toeplitz matrices is not commutative, and it can be shown that this product involves the product of $a(z_{1})$ and $b(z_{2})$ for $z_{1}\neq z_{2}$.
This enables us to capture the relationship between $a(z_{1})$ and $b(z_{2})$.
This corresponds to the case $n<\infty$.
Second, the parameter $n$ controls the tradeoff between the representation power and the model complexity.
We show that if $n$ is small, then the representation power is low, and the model complexity is small.
On the other hand, if $n$ is large, then the representation power is high, and the model complexity is large.
The expectation loss for learning a function is controlled by the representation power and the complexity.
By introducing the parameter $n$ and setting $n$ to balance them, we obtain higher performance compared to the typical commutative kernels.
In addition, to resolve the issue of the interactions becoming weaker as $n$ becomes larger (i.e., representation power becomes higher), we propose a deep approach to obtain models with higher representation powers while keeping the interactions.

Our contributions are summarized as follows:

- •
We propose spectral truncation kernels, a new class of function-valued positive definite kernels that generalize typical kernels.
The proposed kernels are based on the spectral truncation and are indexed by a truncation parameter, which induces the interactions along the data function domain by introducing the noncommutativity into the learning process. (see Definition 6 and Subsection 3.1)
- •
We derive a generalization bound for the learning problem in the RKHMs associated with the proposed kernels.
The bound implies that the parameter $n$ controls the tradeoff between the representation power and the model complexity. (see Section 4)
- •
We propose a deep approach to gain the representation power while keeping the noncommutativity in the kernels.
(see Section 6)

Our framework allows us to go beyond the usual commutative kernels and to develop a new perspective on the significance of noncommutative structures in learning systems.

## 2 Preliminaries

### 2.1 C ∗ superscript 𝐶 C^{*} italic_C start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT -algebra and Reproducing kernel Hilbert C ∗ superscript 𝐶 C^{*} italic_C start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT -module

$C^{*}$-algebra is a Banach space equipped with a product and an involution satisfying the $C^{*}$ identity (condition 3 below).
It is a natural generalization of the space of complex numbers.

###### Definition 1 ( $C^{*}$ -algebra)

A set $\mathcal{A}$ is called a $C^{*}$-algebra if it satisfies the following conditions:

- 1.
$\mathcal{A}$ is an algebra over $\mathbb{C}$ and equipped with a bijection $(\cdot)^{*}:\mathcal{A}\to\mathcal{A}$ that satisfies the following conditions for $\alpha,\beta\in\mathbb{C}$ and $a,b\in\mathcal{A}$:
$\bullet$ $(\alpha a+\beta b)^{*}=\overline{\alpha}a^{*}+\overline{\beta}b^{*}$,  $\bullet$ $(ab)^{*}=b^{*}a^{*}$,  $\bullet$ $(a^{*})^{*}=a$.
- 2.
$\mathcal{A}$ is a normed space endowed with a norm $\|\cdot\|_{\mathcal{A}}$, and for $a,b\in\mathcal{A}$, $\|ab\|_{\mathcal{A}}\leq\|a\|_{\mathcal{A}}\|b\|_{\mathcal{A}}$ holds.
In addition, $\mathcal{A}$ is complete with respect to $\|\cdot\|_{\mathcal{A}}$.
- 3.
For $a\in\mathcal{A}$, the $C^{*}$ identity $\|a^{*}a\|_{\mathcal{A}}=\|a\|_{\mathcal{A}}^{2}$ holds.

If there exists $a\in\mathcal{A}$ such that $ab=b=ba$ for any $b\in\mathcal{A}$, $a$ is called the unit and denoted by $1_{\mathcal{A}}$.

In this paper, we focus on the $C^{*}$-algebra of continuous functions.

###### Example 1

Let $\mathbb{T}=\mathbb{R}/2\pi\mathbb{Z}$ be the torus and $C(\mathbb{T})$ be the space of continuous functions on $\mathbb{T}$.
Then, $\mathcal{A}:=C(\mathbb{T})$ is a $C^{*}$-algebra by means of the product: $(cd)(z)=c(z)d(z)$, involution: $c^{*}(z)=\overline{c(z)}$, and norm: $\|c\|_{\mathcal{A}}=\sup_{z\in\mathbb{T}}|c(z)|$ for $c,d\in\mathcal{A}$.
The unit is the constant function $1_{\mathcal{A}}\equiv 1$.

We now review basic notions regarding $C^{*}$-algebra.
In the following, let $\mathcal{A}$ be a $C^{*}$-algbra.

###### Definition 2 (Positive)

An element $a$ of $\mathcal{A}$ is called positive if there exists $b\in\mathcal{A}$ such that $a=b^{*}b$ holds.
For $a,b\in\mathcal{A}$, we write $a\leq_{\mathcal{A}}b$ if $b-a$ is positive.

###### Definition 3 (Infimum and minimum)

For a subset $\mathcal{S}$ of $\mathcal{A}$, $a\in\mathcal{A}$ is said to be a lower bound with respect to the order $\leq_{\mathcal{A}}$, if $a\leq_{\mathcal{A}}b$ for any $b\in\mathcal{S}$.
Then, a lower bound $c\in\mathcal{A}$ is said to be an infimum of $\mathcal{S}$, if $a\leq_{\mathcal{A}}c$ for any lower bound $a$ of $\mathcal{S}$.
If $c\in\mathcal{S}$, then $c$ is said to be a minimum of $\mathcal{S}$.

We now define RKHM.
Let $\mathcal{X}$ be a non-empty set for data.
To construct an RKHM, we first introduce $\mathcal{A}$-valued positive definite kernel.

###### Definition 4 ( $\mathcal{A}$ -valued positive definite kernel)

An $\mathcal{A}$-valued map $k:\mathcal{X}\times\mathcal{X}\to\mathcal{A}$ is called a positive definite kernel if it satisfies the following conditions:
$\bullet$ $k(x,y)=k(y,x)^{*}$  for $x,y\in\mathcal{X}$,
$\bullet$ $\sum_{i,j=1}^{N}c_{i}^{*}k(x_{i},x_{j})c_{j}$ is positive semi-definite  for $n\in\mathbb{N}$, $c_{i}\in\mathcal{A}$, $x_{i}\in\mathcal{X}$.

Let $\phi:\mathcal{X}\to\mathcal{A}^{\mathcal{X}}$ be the feature map associated with $k$, defined as $\phi(x)=k(\cdot,x)$ for $x\in\mathcal{X}$ and let
$\mathcal{M}_{k,0}=\{\sum_{i=1}^{N}\phi(x_{i})c_{i}|\ N\in\mathbb{N},\ c_{i}\in
\mathcal{A},\ x_{i}\in\mathcal{X}\ (i=1,\ldots,N)\}$.
We can define an $\mathcal{A}$-valued map $\big{\langle}\cdot,\cdot\big{\rangle}_{k}:\mathcal{M}_{k,0}\times\mathcal{M}_{
k,0}\to\mathcal{A}$ as

$$ $\displaystyle\bigg{\langle}\sum_{i=1}^{N}\phi(x_{i})c_{i},\sum_{j=1}^{M}\phi(y _{j})d_{j}\bigg{\rangle}_{k}=\sum_{i=1}^{N}\sum_{j=1}^{M}c_{i}^{*}k(x_{i},y_{j })d_{j},$ $$

which enjoys the reproducing property
$\left\langle\phi(x),f\right\rangle_{k}=f(x)$
for $f\in\mathcal{M}_{k,0}$ and $x\in\mathcal{X}$.

The norm in $\mathcal{M}_{k,0}$ is defined as $\|f\|_{k}^{2}=\|\left\langle f,f\right\rangle_{k}\|_{\mathcal{A}}$, and we can also define the $\mathcal{A}$-valued absolute value $|\cdot|_{k}$ as $|f|_{k}^{2}=\left\langle f,f\right\rangle_{k}$.
The reproducing kernel Hilbert $\mathcal{A}$-module (RKHM) $\mathcal{M}_{k}$ associated with $k$ is defined as the completion of $\mathcal{M}_{k,0}$ with respect to $\|\cdot\|_{k}$.
See, for example, the references (Lance, ; Murphy, ; Hashimoto et al., ) for more details about $C^{*}$-algebra and RKHM.

###### Definition 1 ( C ∗ superscript 𝐶 C^{*} italic_C start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT -algebra)

###### Example 1

###### Definition 2 (Positive)

###### Definition 3 (Infimum and minimum)

###### Definition 4 ( 𝒜 𝒜 \mathcal{A} caligraphic_A -valued positive definite kernel)

### 2.2 Spectral truncation on the torus

The product in $C(\mathbb{T})$ is commutative.
However, by approximating the multiplication of a function $x\in C(\mathbb{T})$ by a Toeplitz matrix, we can obtain a noncommutative product structure.
Let $e_{j}(z)=\mathrm{e}^{\mathrm{i}jz}$ for $j\in\mathbb{Z}$ and $z\in\mathbb{T}$ be the Fourier function and $M_{x}$ be the multiplication operator defined on $L^{2}(\mathbb{T})$ with respect to $x$.
Here, $\mathrm{i}$ is the imaginary unit, and $L^{2}(\mathbb{T})$ is the space of square-integrable functions on $\mathbb{T}$.
Let $P_{n}$ be the orthogonal projection onto the $n$-dimensional subspace $\operatorname{Span}\{e_{1},\ldots,e_{n}\}$.
We approximate $M_{x}$ by $P_{n}M_{x}P_{n}$, i.e., by truncating the spectrum.
Then, the $(j,l)$-entry of the representation matrix $R_{n}(x)\in\mathbb{C}^{n\times n}$ of $P_{n}M_{x}P_{n}$ is written as

$$ $\displaystyle R_{n}(x)_{j,l}=\left\langle e_{j},M_{x}e_{l}\right\rangle_{L^{2} (\mathbb{T})}=\int_{\mathbb{T}}x(t)\mathrm{e}^{-\mathrm{i}(j-l)t}\mathrm{d}t.$ $$

Since the $(j,l)$-entry of $R_{n}(x)$ depends only on $j-l$, $R_{n}(x)$ is a Toeplitz matrix (Gray, ).
It is characterized only by a vector $r_{n}(x)\in\mathbb{C}^{2n-1}$, where the $(j-l)$th element of $r_{n}(x)$ is $R_{n}(x)_{j,l}$.
Note that $R_{n}(x)_{j,l}$ is regarded as the $(j-l)$th Fourier component of $x$, and the vector $r_{n}(x)$ is the coordinate of the function $x$ projected on the space $\operatorname{Span}\{e_{-(n-1)},\ldots,e_{n-1}\}$.

For a matrix $A\in\mathbb{C}^{n\times n}$, let $S_{n}(A)\in C(\mathbb{T})$ be the function defined as $S_{n}(A)(z)=(1/n)\sum_{j,l=0}^{n-1}A_{j,l}\mathrm{e}^{\mathrm{i}(j-l)z}$, where $A_{j,l}$ is the $(j,l)$-entry of $A$.
The map $S_{n}$ takes the representation matrix $R_{n}(x)$ back to a function that approximates the original function $x$.
Indeed, we have

$$ $\displaystyle S_{n}(R_{n}(x))(z)=\int_{\mathbb{T}}x(t)\frac{1}{n}\sum_{j,l=0}^ {n-1}\mathrm{e}^{-\mathrm{i}(j-l)t}\mathrm{e}^{\mathrm{i}(j-l)z}\mathrm{d}t= \int_{\mathbb{T}}x(t)\frac{1}{n}\sum_{j=0}^{n-1}\sum_{l=-j}^{j}\mathrm{e}^{ \mathrm{i}l(z-t)}\mathrm{d}t=x\ast F_{n}(z),$ $$

where $F_{n}(t)=(1/n)\sum_{j=0}^{n-1}\sum_{l=-j}^{j}\mathrm{e}^{\mathrm{i}lt}$ is the Fejér kernel and $\ast$ represents the convolution.
By the following proposition, for each $z\in\mathbb{T}$, $S_{n}(R_{n}(x))(z)$ converges to $x(z)$ as $n\to\infty$ (Brandolini & Travaglini, ; van Suijlekom, ).

###### Proposition 5

For each $z\in\mathbb{T}$, $x\ast F_{n}(z)\to x(z)$ as $n\to\infty$.

A generalization of the Fejér kernel
on $\mathbb{T}$ to that on $\mathbb{T}^{q}$ with respect to the sum over a polyhedron has been theoretically investigated (Travaglini, ; Brandolini & Travaglini, ).
Let $P$ be a polyhedron and $jP=\{jz\,\mid\,z\in P\}$ for $j\in\mathbb{Z}$.
For $t\in\mathbb{T}^{q}$, the Fejér kernel on $\mathbb{T}^{q}$ is defined as

$$ $\displaystyle F_{n}^{q,P}(t)=\frac{1}{n}\sum_{j=1}^{n-1}\sum_{r\in jP\bigcap \mathbb{Z}^{q}}\mathrm{e}^{\mathrm{i}r\cdot t}.$ (1) $$

###### Proposition 5

## 3 C ∗ superscript 𝐶 C^{*} italic_C start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT -algebra-valued Positive Definite Kernel with Spectral Truncation

In the following, we set the $C^{*}$-algebra $\mathcal{A}$ as $C(\mathbb{T})$.
To obtain vector- or functional-valued outputs, applying vvRKHSs has been investigated.
However, as we stated in Section 1, to go beyond the separable kernel and reach higher performance, the computational cost scales as $O(m^{3}N^{3})$ for $m$-dimensional outputs with $N$ samples.
To resolve this issue, we consider function-valued ($\mathcal{A}$-valued) kernels and RKHMs.
As we will discuss in the last part of Section 5, the computational cost depends on $mN^{3}$ if we use an $\mathcal{A}$-valued kernel.
Hashimoto et al. () proposed to use the $\mathcal{A}$-valued kernel $k$ where $k(\cdot,\cdot)(z)$ is a complex-valued positive definite kernel for all $z\in\mathbb{T}$.
Combining it with typical existing kernels (Hashimoto et al., ; Schölkopf & Smola, ; Kadri et al., ; Álvarez et al., ), we obtain the following three kinds of $\mathcal{A}$-valued kernels.

###### Example 2

For $x=[x_{1},\ldots,x_{d}],y=[y_{1},\ldots,y_{d}]\in\mathcal{A}^{d}$ and $z\in\mathbb{T}$,

- 1.
polynomial kernel $k^{\operatorname{poly},q}(x,y)(z)=\sum_{i=1}^{d}\alpha_{i}(\overline{x_{i}(z)}
y_{i}(z))^{q}$,
- 2.
product kernel $k^{\operatorname{prod},q}(x,y)(z)=\prod_{j=1}^{q}\overline{\tilde{k}_{1,j}(x(z
),y(z))}\tilde{k}_{2,j}(x(z),y(z))$,
- 3.
separable kernel $k^{\operatorname{sep},q}(x,y)=\tilde{k}(x,y)\prod_{j=1}^{q}(a_{j}^{*})^{q}a_{j
}^{q}$.

Here, $q\in\mathbb{N}$ is the degree of the products in the kernel, $\alpha_{i}\geq 0$ is the parameter of $k^{\operatorname{poly},q}$, and for $i=1,2$ and $j=1,\ldots,q$, $\tilde{k}_{i,j}:\mathbb{C}\times\mathbb{C}\to\mathbb{C}$ and $\tilde{k}:\mathcal{A}^{d}\times\mathcal{A}^{d}\to\mathbb{C}$ are complex-valued continuous positive definite kernels.
In addition, $a_{j}\in\mathcal{A}$ is the parameter of $k^{\operatorname{sep},q}$.

We propose new $\mathcal{A}$-valued positive definite kernels by generalizing the typical kernels in Example 2.
The kernels in Example 2 involve the product of functions in $\mathcal{A}$.
For $x,y\in\mathcal{A}$, the product of $x$ and $y$ is commutative and is just the pointwise product defined as $(xy)(z)=x(z)y(z)$ (See Example 1).
Thus, the kernels defined in Examples 2.1 and 2.2 do not induce the interactions along $z\in\mathbb{T}$, that is, $k(x,y)(z)$ is determined only by the values $x(z)$ and $y(z)$ at $z$.
If the values $x(z_{1})$ and $x(z_{2})$, or $x(z_{1})$ and $y(z_{2})$ for different $z_{1}$ and $z_{2}$ are related, then the construction of the kernels only with this commutative product cannot extract that relationship.
On the other hand, if we introduce the truncation parameter $n$ and transform $x$ and $y$ into Toeplitz matrices using the map $R_{n}$ defined in Subsection 2.2, then the product of $R_{n}(x)$ and $R_{n}(y)$ is noncommutative.
Focusing on this feature, we define $\mathcal{A}$-valued kernels based on Example 2, but they have interactions along $z\in\mathbb{T}$.

###### Definition 6

With the notations in Example 2, for $x=[x_{1},\ldots,x_{d}],y=[y_{1},\ldots,y_{d}]\in\mathcal{A}^{d}$, let

$$ $\displaystyle k_{n}^{\operatorname{poly},q}(x,y)$ $\displaystyle=S_{n}\bigg{(}\sum_{i=1}^{d}\alpha_{i}(R_{n}(x_{i})^{*})^{q}R_{n} (y_{i})^{q}\bigg{)},$ $\displaystyle k_{n}^{\operatorname{prod},q}(x,y)$ $\displaystyle=S_{n}\bigg{(}\prod_{j=1}^{q}R_{n}(\tilde{k}_{1,j}(x,y))^{*}\prod _{j=1}^{q}R_{n}(\tilde{k}_{2,j}(x,y))\bigg{)},$ $\displaystyle k_{n}^{\operatorname{sep},q}(x,y)$ $\displaystyle=\tilde{k}(S_{n}(R_{n}(x)),S_{n}(R_{n}(y)))S_{n}\bigg{(}\prod_{j= 1}^{q}R_{n}(a_{j})^{*}\prod_{j=1}^{q}R_{n}(a_{j})\bigg{)}.$ $$

Here, $A^{*}$ for a matrix $A$ is the adjoint, and we denote by $\tilde{k}_{i,j}(x,y)$ the map $z\mapsto\tilde{k}_{i,j}(x(z),y(z))$.

###### Remark 7

Although the inputs of the kernels in Example 2 and Definition 6 are functions, we can also deal with vector inputs.
For vector inputs, we can regard them as values of functions, and approximate the integral by the discrete sum.

In Definition 6, to construct the kernels, we first project functions in $\mathcal{A}$ onto the space $\operatorname{Span}\{e_{-(n-1)},\ldots,e_{n-1}\}$ using the map $R_{n}$ and obtain Toeplitz matrices.
Then, we consider the product of the Toeplitz matrices.
Note that the product of two Toeplitz matrices is not always a Toeplitz matrix.
Finally, we apply $S_{n}$ to the matrix and take it back to the space $\operatorname{Span}\{e_{-(n-1)},\ldots,e_{n-1}\}$ and obtain the output function of the kernel.
Figure 1 schematically shows the construction of the simplest kernel $k_{n}^{\operatorname{poly},1}(x,y)=S_{n}(R_{n}(x)^{*}R_{n}(y))$ defined in Definition 6.

Figure: Figure 1: Overview of the construction of the simplest kernel $k_{n}^{\operatorname{poly},1}(x,y)=S_{n}(R_{n}(x)^{*}R_{n}(y))$
Refer to caption: extracted/5897533/kernel_overview.png

By the definitions of $S_{n}$ and $R_{n}$, we can show the following identity for $x_{1},\ldots,x_{q},y_{1},\ldots,y_{q}\in\mathcal{A}$ (see the proof of Theorem 8 in Appendix A):

$$ $\displaystyle S_{n}\bigg{(}\prod_{j=1}^{q}R_{n}(x_{j})^{*}\prod_{j=1}^{q}R_{n} (y)\bigg{)}(z)=\int_{\mathbb{T}^{2q}}\!\!\!\!\!\!\overline{x_{1}(t_{1})}\cdots \overline{x_{q}(t_{q})}y_{1}(t_{q+1})\cdots y_{q}(t_{2q})F_{n}^{2q,P}(z\mathbf {1}-t)\mathrm{d}t,$ (2) $$

where $t=[t_{1},\ldots,t_{2q}]$, $\mathbf{1}=[1,\ldots,1]$, $P=\{[r_{1},\ldots,r_{2q}]\in\mathbb{R}^{2q}\,\mid\,|\sum_{i=l}^{m}r_{i}|\leq 1
,\ l\leq m\}$, and $F_{n}^{q,P}$
is the Fejér kernel on $\mathbb{T}^{q}$ defined in Eq. (1).
Eq. (2) implies that the value of $S_{n}\big{(}\prod_{j=1}^{q}R_{n}(x_{j})^{*}\prod_{j=1}^{q}R_{n}(y_{j})\big{)}$ at $z$ is determined not only by $x_{1}(z),\ldots,x_{q}(z),y_{1}(z),\ldots,y_{q}(z)$, but also by $x_{1}(t_{1}),\ldots,x_{q}(t_{q}),y_{1}(t_{q+1}),\ldots,y_{q}(t_{2q})$ with different values $t_{1},\ldots,t_{2q}$ from $z$.
Note that $F_{n}^{q,P}(t)$ is a real-valued function since for $r\in P$, we have $-r\in P$.
Thus, if a kernel in Example 2 is real-valued, then the corresponding kernel in Definition 6 is also real-valued.

###### Example 2

###### Definition 6

###### Remark 7

### 3.1 Convergence and interactions

We first show that $k_{n}^{\operatorname{poly},q}$, $k_{n}^{\operatorname{prod},q}$, and $k_{n}^{\operatorname{sep},q}$ defined in Definition 6 converge to $k^{\operatorname{poly},q}$, $k^{\operatorname{prod},q}$, and $k^{\operatorname{sep},q}$ defined in Example 2 as $n$ goes to infinity, respectively.
In this sense, the kernels $k_{n}^{\operatorname{poly},q}$, $k_{n}^{\operatorname{prod},q}$, and $k_{n}^{\operatorname{sep},q}$ are generalizations of typical kernels.
In addition, these convergences imply that the interactions along $z\in\mathbb{T}$ in the kernels become smaller as $n$ grows since they disappear at $n=\infty$.
In the following, all the proofs of theoretical statements are documented in Appendix A.

###### Theorem 8

For $x,y\in\mathcal{A}^{d}$ and $z\in\mathbb{T}$, $k_{n}^{\operatorname{poly},q}(x,y)(z)\to k^{\operatorname{poly},q}(x,y)(z)$, $k_{n}^{\operatorname{prod},q}(x,y)(z)\to k^{\operatorname{prod},q}(x,y)(z)$ as $n\to\infty$.
If $x$ and $y$ are differentiable, then $k_{n}^{\operatorname{sep},q}(x,y)(z)\to k^{\operatorname{sep},q}(x,y)(z)$.

As we can see in Eq. (2), if the kernel involves $q$ products of Toeplitz matrices generated by $R_{n}$, it is represented by a Fejér kernel on $\mathbb{T}^{q}$.
To show Theorem 8, we apply the following lemmas.

###### Lemma 9

For $m\in\mathbb{N}$ and $j=0,\ldots 2q$, let $Q_{j}^{m}=\{r^{\prime}=[r_{1}^{\prime},\ldots,r_{2q}^{\prime}]\in\mathbb{R}^{2
q}\,\mid\,r_{i}^{\prime}=r_{i}-r_{i-1}\ (i=1,\ldots,2q),\ 0\leq r_{i}\leq m\ (
i=0,\ldots,2q),\ r_{j}=m\}$ and $P=\{r=[r_{1},\ldots,r_{2q}]\in\mathbb{R}^{2q}\,\mid\,|\sum_{i=l}^{k}r_{i}|\leq
1
,\ l\leq k\}$.
Then, we have $mP=\bigcup_{j=0}^{2q}Q_{j}^{m}$.

###### Lemma 10

Let $P$ be a convex polyhedron.
Let $F_{n}^{q,P}$ be the Fejér kernel on $\mathbb{T}^{q}$ defined as Eq. (1).
Then, for any $g\in C(\mathbb{T}^{q})$ and any $z\in\mathbb{T}^{q}$, $g\ast F_{n}^{q,P}(z)\to g(z)$ as $n\to\infty$.

Since the product of Toeplitz matrices in $k_{n}^{\operatorname{poly},q}$, $k_{n}^{\operatorname{prod},q}$, and $k_{n}^{\operatorname{sep},q}$ are represented by the sum over the indices in $\bigcup_{j=0}^{2q}Q_{j}^{m}$, Lemma 9 explains why the Fejér kernel with the polyhedron $P=\{r\in\mathbb{R}^{2q}\,\mid\,|\sum_{i=l}^{k}r_{i}|\leq 1,\ l\leq k\}$ appears in Eq. (2).
Lemma 10 generalizes the convergence of the Fejér kernel on $\mathbb{T}$ to that on $\mathbb{T}^{q}$, which is by Brandolini & Travaglini ().
We set $g(z)=\overline{x_{1}(z_{1})}\cdots\overline{x_{q}(z_{q})}y_{1}(z_{q+1})\cdots y
_{q}(z_{2q})$ for $z=[z_{1},\ldots,z_{2q}]$, based on Eq. (2), and apply Lemmas 9 and 10 to show Theorem 8.
See Appendix A for more details.

As seen in Theorem 8, the interactions along $z\in\mathbb{T}$ in the kernels become small as $n$ grows.
On the other hand, we also have the parameter $q$ that describes how many Toeplitz matrices created by $R_{n}$ are involved in the kernel.
Regarding the relationship between $q$ and the interactions, we have the following remark.

###### Remark 11

We expect that the convergence in Theorem 8 becomes slower as $q$ becomes larger, and the interaction along $z\in\mathbb{T}$ becomes larger.
This is based on the observation that the value related to the Fejér kernel on $\mathbb{T}^{q}$ is described by the corresponding value related to the Fejér kernel on $\mathbb{T}^{q-1}$, especially in the case of $q=2$.
See Appendix B for more details.

###### Theorem 8

###### Lemma 9

###### Lemma 10

###### Remark 11

### 3.2 Positive definiteness

To construct an RKHM, which is introduced in Subsection 2.1, the kernel $k$ has to be positive definite.
Thus, we investigate the positive definiteness of the proposed kernels.
Regarding $k_{n}^{\operatorname{poly},q}(x,y)$, we can show the positive definiteness since $x_{i}$ and $y_{i}$ are separated by the product.
Regarding $k_{n}^{\operatorname{sep}}(x,y)$, since $x$ and $y$ depend only on $\tilde{k}$, we can use the positive definiteness of $\tilde{k}$.

###### Proposition 12

The kernels $k_{n}^{\operatorname{poly},q}$ and $k_{n}^{\operatorname{sep},q}$ are positive definite.

As for $k_{n}^{\operatorname{prod},q}(x,y)$, it depends on $x$ and $y$ through $\tilde{k}_{i,j}$, and we cannot separate $x$ and $y$ as products.
Thus, we cannot show its positive definiteness.
However, we can modify the kernel to become positive definite as follows.

###### Proposition 13

Let $\beta_{n}\geq-\min_{z\in\mathbb{T}^{q}}F_{n}^{2q,P}(z)$.
Then, $\hat{k}_{n}^{\operatorname{prod},q}$ defined below is positive definite.

$$ $\displaystyle\hat{k}_{n}^{\operatorname{prod},q}(x,y)=k_{n}^{\operatorname{ prod},q}(x,y)+\beta_{n}\int_{\mathbb{T}^{2q}}\prod_{j=1}^{q}\overline{\tilde{k }_{1,j}(x(t_{j}),y(t_{j}))}\tilde{k}_{2,j}(x(t_{q+j}),y(t_{q+j}))\mathrm{d}t.$ $$

To set the value of the parameter $\beta_{n}$, we have the following bound.

###### Lemma 14

We have $|F_{n}^{q,P}(z)|\leq n^{q}$.

###### Remark 15

We can set $\beta_{n}$ in $\hat{k}_{n}^{\operatorname{prod},q}$ as $n^{q}$ to guarantee the positive definiteness.
However, even if we set a smaller $\beta_{n}$, $\hat{k}_{n}^{\operatorname{prod},q}$ may become positive definite.
In addition, considering non-positive kernels has also been investigated (Ong et al., ; Canu et al., ).
Indeed, in practical computations in Subsection 7, the algorithms can work even if we set $\beta_{n}<n^{2q}$.
Deriving a tighter bound of $\beta_{n}$ or developing the theory for non-positive kernels for RKHMs is future work.

###### Proposition 12

###### Proposition 13

###### Lemma 14

###### Remark 15

## 4 Generalization Bound

We now focus on what impact the truncation parameter $n$ has on generalization.
We provide a generalization bound allowing us to observe the tradeoff between the representation power and the model complexity associated with the proposed kernels.
According to Lemma 4.2 in Mohri et al. (), the generalization bound is described by the Rademacher complexity.
We apply this lemma and derive a generalization bound.

Let $\Omega$ be a probability space with a probability measure $\mu$.
Let $X_{1},\ldots,X_{N}$ and $Y_{1},\ldots,Y_{N}$ be samples from a distributions of $\mathcal{A}_{0}^{d}$-valued random variable $X$ and $\mathcal{A}_{1}$-valued random variable $Y$ on $\Omega$, respectively (i.e., for $z\in\mathbb{T}$, $X_{i}(z)$ is a sample from the distribution of $X(z)$).
Here, $\mathcal{A}_{0}$ and $\mathcal{A}_{1}$ are subsets of $\mathcal{A}$.
Let $\mathrm{E}$ be the Bochner integral on $\Omega$ with respect to $\mu$.
Let $B>0$ and $\mathcal{F}=\{f\in\mathcal{M}_{k}\,\mid\,\|f\|_{k}\leq B\}$.
Let $g:\mathbb{R}\times\mathbb{R}\to\mathbb{R}_{+}$ be an error function.
Assume there exists $L>0$ such that for $y\in\mathcal{A}_{1}$ and $z\in\mathbb{T}$, $x\mapsto g(x,y(z))$ is $L$-Lipschitz continuous.
We derive the following generalization bound for the kernels defined in Section 3.

###### Theorem 16

Assume $k_{n}^{\operatorname{poly},q}$, $k_{n}^{\operatorname{prod},q}$, and $k_{n}^{\operatorname{sep},q}$ are real-valued.
Let $D(k_{n}^{\operatorname{poly},q},x)=\sum_{j=1}^{d}\alpha_{j}\|R_{n}(x_{j})\|^{2
q}_{\operatorname{op}}$, $D(\hat{k}_{n}^{\operatorname{prod},q},x)=\prod_{j=1}^{q}(\|R_{n}(\tilde{k}_{1,
j}(x,x))\|_{\operatorname{op}}\|R_{n}(\tilde{k}_{2,j}(x,x))\|_{\operatorname{
op}})+\beta_{n}C$, and $D(k_{n}^{\operatorname{sep},q},x)=\tilde{k}(x,x)\prod_{j=1}^{q}\|R_{n}(a_{j})
\|_{\operatorname{op}}^{2}$ for $x\in\mathcal{A}_{0}^{d}$, where $\|\cdot\|_{\operatorname{op}}$ is the operator norm and $C=\prod_{j=1}^{q}\int_{\mathbb{T}}\tilde{k}_{1,j}(x(t),x(t))\mathrm{d}t\int_{
\mathbb{T}}\tilde{k}_{2,j}(x(t),x(t))\mathrm{d}t$.
Assume $\beta_{n}\leq\beta_{n+1}$ for $\hat{k}_{n}^{\operatorname{prod},q}$.
For $k_{n}=k_{n}^{\operatorname{poly},q},\hat{k}_{n}^{\operatorname{prod},q},k_{n}^
{\operatorname{sep},q}$ and
for any $\delta\in(0,1)$, with probability at least $1-\delta$, we have

$$ $\displaystyle\mathrm{E}[g(f(X),Y)]\leq_{\mathcal{A}}\frac{1}{N}\sum_{i=1}^{N}g (f(X_{i}),Y_{i})+2L\frac{B}{N}\bigg{(}\sum_{i=1}^{N}D(k_{n},X_{i})\bigg{)}^{1/ 2}1_{\mathcal{A}}+3\sqrt{\frac{\log 1/\delta}{N}}1_{\mathcal{A}}$ (3) $$

for any $f\in\mathcal{F}$.
In addition, we have $D(k_{n},x)\leq D(k_{n+1},x)$.

The first term of the right-hand side of (3) is the empirical loss, and the second term represents the model complexity of the RKHM $\mathcal{M}_{k_{n}}$.
There is a tradeoff between these terms.
If $n$ is larger, then since the approximation space $\operatorname{Span}\{e_{-(n-1)},\ldots,e_{n-1}\}$ in $\mathcal{A}$ is larger, the outputs of ${k_{n}}$ can represent more functions, which enables us to describe the dependency of outputs on inputs more.
Indeed, if $n=1$, then the output of $k_{n}$ is always a constant function, where the situation is the same as the existing separable kernel discussed in Section 1.
Thus, the empirical loss (the first term) can become small if $n$ is large.
On the other hand, according to Theorem 16, the complexity of $\mathcal{M}_{k_{n}}$ (the second term) is larger if $n$ is larger.
An advantage of introducing the parameter $n$ to construct the new kernels based on the typical kernels in Example 2 is that we can control the empirical loss and the complexity through $n$.
By setting a proper $n$, we can balance the two terms and make the expected loss $\mathrm{E}[g(f(X),Y)]$, the left-hand side of Eq. (3),
small.

###### Theorem 16

## 5 Application to Kernel Ridge Regression

We illustrate the effect of the proposed kernels by applying them to kernel ridge regression.
Let $x_{1},\ldots,x_{N}\in\mathcal{A}^{d}$ be input training samples and $y_{1},\ldots,y_{N}\in\mathcal{A}$ be output training samples.
We consider the RKHM $\mathcal{M}_{k}$ associated with $k=k_{n}^{\operatorname{poly},q}$, $k=k_{n}^{\operatorname{prod},q}$, or $k=k_{n}^{\operatorname{sep},q}$.
Consider the typical minimization problem for regression, which is also considered by Hashimoto et al. ():

$$ $\displaystyle\min_{f\in\mathcal{M}_{k}}\bigg{(}\sum_{i=1}^{N}|f(x_{i})-y_{i}|_ {\mathcal{A}}^{2}+\lambda|f|_{k}^{2}\bigg{)},$ (4) $$

where $\lambda\geq 0$ is the regularization parameter.
We apply the approximation version of the representer theorem for RKHMs over general $C^{*}$-algebras (see Appendix C).
Then, the solution of the problem (4) is approximated by a vector having the form of $\sum_{i=1}^{N}\phi_{i}(x_{i})c_{i}$.
The problem is reduced to

$$ $\displaystyle\min_{c_{j}\in\mathcal{A}}\bigg{(}\sum_{i=1}^{N}\bigg{|}\sum_{j=1 }^{N}k(x_{i},x_{j})c_{j}-y_{i}\bigg{|}_{{\mathcal{A}}}^{2}+\lambda\bigg{|}\sum _{j=1}^{N}\phi(x_{j})c_{j}\bigg{|}_{k}^{2}\bigg{)}$ $\displaystyle\quad=\min_{c_{j}\in\mathcal{A}}(\mathbf{c}^{*}\mathbf{G}^{2} \mathbf{c}-\mathbf{c}^{*}\mathbf{G}\mathbf{y}-\mathbf{y}^{*}\mathbf{G}\mathbf{ c}+\lambda\mathbf{c}^{*}\mathbf{G}\mathbf{c}),$ (5) $$

where $\mathbf{G}$ is the ${\mathcal{A}^{N\times N}}$-valued Gram matrix whose $(i,j)$-entry is defined as $k(x_{i},x_{j}){\in\mathcal{A}}$, $\mathbf{c}=[c_{1},\ldots,c_{N}]^{T}\in\mathcal{A}^{N}$, $\mathbf{y}=[y_{1},\ldots,y_{N}]^{T}\in\mathcal{A}^{N}$.
Then, the solution $\mathbf{c}$ of the problem (5) satisfies $\mathbf{y}=(\mathbf{G}+\lambda I)\mathbf{c}$, which means $\mathbf{y}(z)=(\mathbf{G}(z)+\lambda I)\mathbf{c}(z)$.
Therefore, for each $z\in\mathbb{T}$, we obtain $\mathbf{c}(z)$ by computing $(\mathbf{G}(z)+\lambda I)^{-1}\mathbf{y}(z)$.

#### Computational cost

The computational cost for the product of two $n$ by $n$ Toeplitz matrices is $O(n^{2})$, and computing $S_{n}(A)(z)$ for an $n$ by $n$ matrix $A$ and $z\in\mathbb{T}$ costs $O(n^{2})$.
Thus, the cost for constructing $\mathbf{G}(z_{1}),\ldots,\mathbf{G}(z_{m})$ for different $m$ points $z_{1},\ldots,z_{m}\in\mathbb{T}$ with $k_{n}^{\operatorname{poly},q}$ or $\hat{k}_{n}^{\operatorname{prod},q}$ is $O((qn^{2}+mn^{2})N^{2})$. As for the computation of $\mathbf{c}(z)$, we need to compute $(\mathbf{G}(z)+\lambda I)^{-1}\mathbf{y}(z)$, which costs $O(N^{3})$.
Thus, the total computational cost for obtaining $\mathbf{c}(z_{1}),\ldots,\mathbf{c}(z_{m})$ is $O((q+m)n^{2}N^{2}+mN^{3})$.
Note that the cost is linear with respect to $m$.
This is by virtue of considering function-valued kernels and RKHMs.
The situation is different if we use vvRKHSs.
For vvRKHSs, to obtain $m$ values as an output, we apply a $\mathbb{C}^{m\times m}$-valued kernel. If the kernel is nonseparable, the Gram matrix should be $mN$ by $mN$, which results in a computational cost of $O(m^{3}N^{3})$.
We can reduce the cost with respect to $N$, e.g., by Nyström method (Drineas & Mahoney, ).
Regarding $n$ and $q$, one approach to reducing the cost with respect to them is investigating the method to approximate the Fejér kernel. However, the main contribution of this paper is to show the advantage of introducing the noncommutivity in kernels, and investigating computationally effective methods is future work.

## 6 Deep model with the spectral truncation kernels

As we discussed in Section 4, there is a tradeoff between the representation power and the model complexity.
In fact, there are two directions of the representation power: one is about the dependency of the outputs on the inputs discussed in Section 4, and the other is about the interactions along the data function domain.
One shortcoming of the spectral truncation kernel is that to obtain a model with a high representation power in the sense of the dependency of the outputs on the inputs, the truncation parameter $n$ have to be large, which results in making the interactions along the data function domain weak.
To gain the two types of representation powers at the same time, we consider the following deep model $f$ with $L$ spectral truncation kernels $k_{n}^{1},\ldots,k_{n}^{L}$ and learnable parameters $c_{i}^{1},\ldots,c_{i}^{L}\!\!\in\!\mathcal{A}$:

$$ $\displaystyle f(x)=\prod_{j=1}^{L}\bigg{(}\sum_{i=1}^{N}k_{n}^{j}(x,x_{i})c^{j }_{i}\bigg{)}.$ (6) $$

We consider the case where $c_{i}^{j}$ in Eq. (6) is represented as a finite sum of functions in $\mathcal{A}$.
In the following case, the representation power of this model grows exponentially.

###### Proposition 17

Let $k^{j}_{n}(x,x_{i})=\sum_{l=-(n-1)}^{n-1}\tilde{d}_{i,l}^{j}\mathrm{e}^{\mathrm
{i}lz}$ with $\tilde{d}_{i,l}^{j}\in\mathbb{C}$.
Assume $c_{i}^{j}$ is parameterized as $c_{i}^{j}(z)=\sum_{l=-(n-1)}^{n-1}d_{i,l}^{j}e_{\tau_{j},l}$ with $d_{i,l}^{j}\in\mathbb{C}$ and $\tau_{j}\in\mathbb{R}$.
Here, $e_{\tau_{j},l}\in C(\mathbb{T})$ satisfies $e_{\tau_{j},l}(z)=\mathrm{e}^{\mathrm{i}\tau_{j}lz}$ for $z\in S$ for a subset $S$ of $\mathbb{T}$.
Then, for $z\in S$, $f$ in Eq. (6) is represented as

$$ $\displaystyle\sum_{l_{1},\ldots,l_{L}=-(n-1)}^{n-1}\sum_{m_{1},\ldots,m_{L}=-( n-1)}^{n-1}\sum_{i=1}^{N}\tilde{d}_{i,l_{1}}^{1}\cdots\tilde{d}_{i,l_{L}}^{L}{ d}_{i,l_{1}}^{1}\cdots{d}_{i,l_{L}}^{L}\mathrm{e}^{\mathrm{i}(l_{1}+\cdots+l_{ L}+\tau_{1}m_{1}+\cdots\tau_{L}m_{L})z}.$ $$

Let $V_{n,L}=\operatorname{Span}\{z\mapsto\mathrm{e}^{\mathrm{i}(l_{1}+\cdots+l_{L}
)z}e_{\tau_{1},m_{1}}(z)\cdots e_{\tau_{L},m_{L}}(z)\,\mid\,l_{1},\ldots,l_{L}
,m_{1},\ldots,m_{L}\in\{-(n-1),\ldots,n-1\}\}$.
If $\{\tau_{1},\ldots,\tau_{L}\}$ is linearly independent over $\mathbb{Z}$, then $V_{n,L}$ is described by $2n+1+(2n+1)^{L}$ oscillating functions.
In this sense, the representation power of the model $f$ grows exponentially with respect to the number of layers $L$.

###### Remark 18

The exponential growth of the representation power is also observed for neural networks (Hanin & Rolnick, ).
Deep learning with kernels has also been proposed (Laforgue et al., ; Hasimoto et al., ).
Whereas the growth is obtained by the composition for these existing frameworks, it is obtained by the product for our case.
Unlike the case of the existing frameworks, the representation power regarding $\mathcal{A}$ does not become high by the composition of functions.

###### Remark 19

The function $f$ is in the RKHM associated with the kernel $\prod_{j=1}^{L}k^{j}$.
Since the Rademacher complexity bound depends on the norm of the kernel, it can also grow exponentially with respect to $L$.
Thus, for the deep setting, in the same manner as Theorem 16, we still have the tradeoff between the representation power and the model complexity.
In this case, it is controlled by both $n$ and $L$.
The exponential growth of the Rademacher complexity bound (thus, the generalization bound) with respect to the number of layers is also observed for neural networks (Neyshabur et al., ; Bartlett et al., ; Golowich et al., ).
Investigating how we can take advantage of the deep setting in the sense of the generalization is future work.

###### Proposition 17

###### Remark 18

###### Remark 19

## 7 Numerical results

We show numerical results that illustrate the effects of the noncommutativity on the learning process.

### 7.1 Experiment with synthetic data

We first observed the behavior of the proposed kernels $k_{n}^{\operatorname{poly},q}$, $\hat{k}_{n}^{\operatorname{prod},q}$, and ${k}_{n}^{\operatorname{sep},q}$ with different values of $n$ and compared them to the commutative kernels $k^{\operatorname{poly},q}$, $k^{\operatorname{prod},q}$, and $k^{\operatorname{sep},q}$ (corresponding to $n=\infty$).
We considered a regression task with synthetic data.
For $i=1,\ldots,N$, we generated input training samples as
$x^{i}(z)=[\sin(0.01iz)+0.01\xi_{z,i},\cos(0.01iz)+0.01\eta_{z,i}]$.
We set the target function $f$ as $f(x)(z)=3(\sin(\cos(\int_{z-\Delta}^{z+\Delta}x_{1}(t)\mathrm{d}t+\int_{z-
\Delta}^{z+\Delta}x_{2}(t)\mathrm{d}t)))$, where $\Delta=2\pi/30$, and generated training output samples $y^{i}(z)=f(x)(z)+0.001\xi_{z,i}$.
Here, $\xi_{z,i}$ and $\eta_{z,i}$ were sampled independently from the Gaussian distribution with mean 0 and standard deviation 1.
We set the sample size $N$ as 1000.
For the kernel ${k}_{n}^{\operatorname{poly},q}$, we set $q=1$ and $\alpha_{1}=1$.
Note that ${k}^{\operatorname{poly},q}$ is the linear kernel in this case.
For the kernel $\hat{k}_{n}^{\operatorname{prod},q}$, we set $q=1$, $\tilde{k}_{1,1}(x,y)=\tilde{k}_{2,1}(x,y)=2\pi\mathrm{e}^{-|x-y|^{2}}$.
We set $\beta_{n}=1$ for $n<\infty$ and $\beta_{\infty}=0$.
For the kernel $k_{n}^{\operatorname{sep},q}$, we set $\tilde{k}(x,y)=\mathrm{e}^{-0.1\cdot 2\pi^{2}(\|x_{1}-y_{1}\|_{L^{2}(\mathbb{T
})}^{2}+\|x_{2}-y_{2}\|_{L^{2}(\mathbb{T})}^{2})}$, $q=2$, and $a_{1}(z)=a_{2}(z)=2\pi\mathrm{e}^{\sin z}$.
We estimated $f$ using kernel ridge regression. We applied the cross-validation grid search to find an optimal regularization parameter $\lambda$.
Figure 2 (a-c) illustrates the test error.
We can see that for ${k}_{n}^{\operatorname{poly},q}$, the test error is the smallest when $n=32$.
It becomes large if $n$ is larger or smaller than $32$.
This is because when $n=32$, the empirical error and the complexity in Eq. 3 are balanced, and the best possible expected error is obtained.
We can see that even for the simplest kernel ${k}_{n}^{\operatorname{poly},1}$, the proposed kernel ($n$ is finite) goes beyond the typical commutative kernel ($n=\infty$).
We have similar results for the other two kernels.
Note that $\hat{k}_{\infty}^{\operatorname{prod},q}(x,y)(z)=\hat{k}^{\operatorname{prod},
q}(x,y)(z)$ only depends on $x(z)$ and $y(z)$.
However, $f(x)(z)$ depends on $x(t)$ for $t\in[z-\Delta,z+\Delta]$.
Thus, the test error becomes large when $n=\infty$.
In addition, as discussed in Remark 15, $\hat{k}_{n}^{\operatorname{prod},q}$ may not be positive definite.
However, although we set $\beta_{n}$ as a small value, all the eigenvalues of the Gram matrix are positive in this case.
See Appendix E.1 for more details.

We also compared the performance and the computational time of RKHMs associated with the proposed kernels to a vvRKHS with the same setting as above.
For the vvRKHS, we used the nonseparable kernel $k(x,y)=\tilde{k}(x,y)[\mathrm{e}^{-|x_{i}-y_{j}|^{2}}]_{i,j}$, where we replaced $S_{n}(\prod_{j=1}^{q}R_{n}(a_{j})^{*}\prod_{j=1}^{q}R_{n}(a_{j}))$ with the nonseparable matrix $[\mathrm{e}^{-|x_{i}-y_{j}|^{2}}]_{i,j}$.
This nonseparable kernel is proposed by Lim et al. ().
Table 1 shows the result.
We can see that the RKHMs outperform the vvRKHS, and the computational time for the RKHMs are smaller than that for the vvRKHS.
Note that we have already confirmed the proposed kernels outperform the existing separable kernel $k_{\infty}^{\operatorname{sep},q}$ in the above experiment (See Figure 2 (c)).

Finally, we observed the behavior of the deep model.
We generated data in the same manner as above, but we set $N=300$.
We used the kernel ${k}_{n}^{\operatorname{prod},q}$ and set $L=1,2,3$, $\tau_{1}=\sqrt{2}$, $\tau_{2}=\sqrt{3}$, and $\tau_{3}=\sqrt{5}/2$.
We set $n$ so that the numbers of parameters are the same for all values of $L$.
We used the loss function $\|\sum_{i=1}^{N}|f(x_{i})-y_{i}|_{k}\|_{L^{2}(\mathbb{T})}+0.1\||f|_{k}\|_{L^{
2}(\mathbb{T})}$ for the deep model $f$ defined in Eq. (6).
Figure 2 (d) shows the result.
We can see that as the number of layers increases, we can obtain a higher performance model even with the same number of parameters.

Figure: (a) $k={k}_{n}^{\operatorname{poly},q}$
Refer to caption: extracted/5897533/rebuttal/poly_cv.png

**Table 1: Test error and CPU time of the regression task with RKHM and vvRKHS**
|  | Test Error | CPU Time (s) |
| --- | --- | --- |
| RKHM, $k=k_{n}^{\operatorname{prod},q}$ ($n=9$) | 0.0113$\pm$1.63$\times 10^{-5}$ | 149.3$\pm$2.392 |
| RKHM, $k=k_{n}^{\operatorname{sep},q}$ ($n=10$) | 0.0385$\pm$5.04388$\times 10^{-5}$ | 22.79$\pm$ 0.5742 |
| vvRKHS | 0.0774$\pm$7.86 $10^{-5}$ | 570.4$\pm$14.87 |

### 7.2 Experiment with MNIST

We consider an image recovering task with MNIST (LeCun et al., ).
For $i=1,\ldots,N$, we generated input training samples by setting all the $8\times 8$ pixels in the middle of the images as 0 0.
We set the output samples as the original images.
We flatten the 2-dimensional $28\times 28$ image to a vector in $\mathbb{R}^{784}$ and regard it as a discretized function on the space of pixels.
We tried to estimate a function that transforms an image with the missing part into the original image.
We applied kernel ridge regression with the regularization parameter $\lambda=0.01$.
We set the sample size $N$ as $200$, and used the kernel $k_{n}^{\operatorname{prod},q}$ with $q=1$ and $\tilde{k}_{1,1}(x,y)=\tilde{k}_{2,1}(x,y)=2\pi\mathrm{e}^{-0.1|x-y|^{2}}$.
We set $\beta_{n}=0.01$ for $n<\infty$ and $\beta_{\infty}=0$.
Figure 2 (e) shows the output images with different values of $n$.
When $n=\infty$, i.e., the commutative kernel, we cannot recover the missing part since each pixel of the output is determined only with the corresponding pixel of the input, and we cannot obtain information of other pixels to estimate what is written in the image.
When $n=70$, we can recover the image the clearest.

## 8 Conclusion and Limitation

In this paper, we proposed a new class of positive definite kernels for vector- or function-valued outputs based on the spectral truncation.
The proposed kernels with the framework of RKHMs resolve two shortcomings of the framework of vvRKHSs for vector- or function-valued outputs at the same time: computational cost and choice of kernels.
By considering function-valued positive definite kernels, not operator-valued ones, we can alleviate the computational cost.
At the same time, we can introduce noncommutativity into the learning process and can induce interactions along the data function domain.
We also showed that we can control the tradeoff between the representation power and the model complexity associated with the proposed kernels.
In addition, we proposed a deep approach to obtain models with higher representation powers.

In the current setting, we focus on the $C^{*}$-algebra of continuous functions on the torus.
Although this setting includes many important examples, e.g., periodic time-series data, continuous functions defined on a compact set in $\mathbb{R}$, finite-dimensional vectors, investigations for more general $C^{*}$-algebras allow us to apply the proposed kernel more general settings.
As we discuss in Appendix D, we can generalize this setting and define positive definite kernels for more general inputs and outputs.
However, theoretical investigations for these generalized settings and their computationally efficient implementations remain to be investigated in future work.

### Acknowledgements

The representer theorem stated in Appendix C is pointed out by Ms. Miho Mukohara.
We would like to thank her for the helpful discussion.
We would also like to thank Mr. Noboru Isobe for a constructive discussion.
Hachem Kadri is partially supported by grant ANR-19-CE23-0011 from the French National Research Agency.
Masahiro Ikeda is partially supported by grant JPMJCR1913 from JST CREST.

## Appendix

## Appendix A Proofs

We provide the proofs of theorems, propositions, and lemmas stated in the main text.

Theorem 8
For $x,y\in\mathcal{A}^{d}$ and $z\in\mathbb{T}$, $k_{n}^{\operatorname{poly},q}(x,y)(z)\to k^{\operatorname{poly},q}(x,y)(z)$, $k_{n}^{\operatorname{prod},q}(x,y)(z)\to k^{\operatorname{prod},q}(x,y)(z)$ as $n\to\infty$.
If $x$ and $y$ are differentiable, then $k_{n}^{\operatorname{sep},q}(x,y)(z)\to k^{\operatorname{sep},q}(x,y)(z)$.

Proof  We show $k_{n}^{\operatorname{poly},q}(x,y)(z)\to k^{\operatorname{poly},q}(x,y)(z)$.
The proofs for $k_{n}^{\operatorname{prod},q}(x,y)$ and $k_{n}^{\operatorname{sep},q}(x,y)$ are similar.
We have

$$ $\displaystyle k_{n}^{\operatorname{poly},q}(x,y)(z)=S_{n}\bigg{(}\sum_{i=1}^{d }\alpha_{i}(R_{n}(x_{i})^{*})^{q}R_{n}(y_{i})^{q}\bigg{)}(z)$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{d}\alpha_{i}\sum_{j,l=0}^{n-1}\sum_{r_{1} ,\ldots,r_{2q}=0}^{n-1}R_{n}(x_{i})^{*}_{j,r_{1}}\cdots R_{n}(x_{i})^{*}_{r_{q -1},r_{q}}R_{n}(y_{i})_{r_{q},r_{q+1}}\cdots R_{n}(y_{i})_{r_{2q-1},l}\mathrm{ e}^{\mathrm{i}(j-l)z}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{d}\alpha_{i}\sum_{j,l=0}^{n-1}\sum_{r_{1} ,\ldots,r_{2q-1}=0}^{n-1}\int_{\mathbb{T}}\cdots\int_{\mathbb{T}}\overline{x_{ i}(t_{1})}\cdots\overline{x_{i}(t_{q})}y_{i}(t_{q+1})\cdots y_{i}(t_{2q})$ $\displaystyle\qquad\cdot\mathrm{e}^{\mathrm{i}(r_{1}-j)t_{1}}\cdots\mathrm{e}^ {\mathrm{i}(r_{q}-r_{q-1})t_{q}}\mathrm{e}^{\mathrm{i}(r_{q+1}-r_{q})t_{q+1}} \cdots\mathrm{e}^{\mathrm{i}(l-r_{2q-1})t_{2q}}\mathrm{d}t_{1}\cdots\mathrm{d} t_{2q}\mathrm{e}^{\mathrm{i}(j-l)z}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{d}\alpha_{i}\sum_{j,l=0}^{n-1}\sum_{r_{1} ,\ldots,r_{2q-1}=0}^{n-1}\int_{\mathbb{T}}\cdots\int_{\mathbb{T}}\overline{x_{ i}(t_{1})}\cdots\overline{x_{i}(t_{q})}y_{i}(t_{q+1})\cdots y_{i}(t_{2q})$ $\displaystyle\qquad\cdot\mathrm{e}^{\mathrm{i}(r_{1}-j)(t_{1}-z)}\cdots\mathrm {e}^{\mathrm{i}(r_{q}-r_{q-1})(t_{q}-z)}\mathrm{e}^{\mathrm{i}(r_{q+1}-r_{q})( t_{q+1}-z)}\cdots\mathrm{e}^{\mathrm{i}(l-r_{2q-1})(t_{2q}-z)}\mathrm{d}t_{1} \cdots\mathrm{d}t_{2q}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{d}\alpha_{i}\sum_{m=0}^{n-1}\bigg{(}\sum_ {j,l,r_{1},\ldots,r_{2q-1}=0}^{m}-\sum_{j,l,r_{1},\ldots,r_{2q-1}=0}^{m-1} \bigg{)}\int_{\mathbb{T}}\cdots\int_{\mathbb{T}}\overline{x_{i}(t_{1})}\cdots \overline{x_{i}(t_{q})}y_{i}(t_{q+1})\cdots y_{i}(t_{2q})$ $\displaystyle\qquad\cdot\mathrm{e}^{\mathrm{i}(r_{1}-j)(t_{1}-z)}\cdots\mathrm {e}^{\mathrm{i}(r_{q}-r_{q-1})(t_{q}-z)}\mathrm{e}^{\mathrm{i}(r_{q+1}-r_{q})( t_{q+1}-z)}\cdots\mathrm{e}^{\mathrm{i}(l-r_{2q-1})(t_{2q}-z)}\mathrm{d}t_{1} \cdots\mathrm{d}t_{2q}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{d}\alpha_{i}\sum_{m=0}^{n-1}\sum_{\begin{ subarray}{c}j\lor l\lor r_{1}\lor\ldots\lor r_{2q-1}=m\\ 0\leq j,l,r_{1},\ldots,r_{2q-1}\leq m\end{subarray}}\int_{\mathbb{T}}\cdots \int_{\mathbb{T}}\overline{x_{i}(t_{1})}\cdots\overline{x_{i}(t_{q})}y_{i}(t_{ q+1})\cdots y_{i}(t_{2q})$ $\displaystyle\qquad\cdot\mathrm{e}^{\mathrm{i}(r_{1}-j)(t_{1}-z)}\cdots\mathrm {e}^{\mathrm{i}(r_{q}-r_{q-1})(t_{q}-z)}\mathrm{e}^{\mathrm{i}(r_{q+1}-r_{q})( t_{q+1}-z)}\cdots\mathrm{e}^{\mathrm{i}(l-r_{2q-1})(t_{2q}-z)}\mathrm{d}t_{1} \cdots\mathrm{d}t_{2q}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{d}\alpha_{i}\sum_{j=0}^{n-1}\sum_{r\in jP \bigcap\mathbb{Z}^{2q}}\int_{\mathbb{T}}\cdots\int_{\mathbb{T}}\overline{x_{i} (t_{1})}\cdots\overline{x_{i}(t_{q})}y_{i}(t_{q+1})\cdots y_{i}(t_{2q})$ $\displaystyle\qquad\cdot\mathrm{e}^{\mathrm{i}r_{1}(z-t_{1})}\cdots\mathrm{e}^ {\mathrm{i}r_{q}(z-t_{q})}\mathrm{e}^{\mathrm{i}r_{q+1}(z-t_{q+1})}\cdots \mathrm{e}^{\mathrm{i}r_{2q}(z-t_{2q})}\mathrm{d}t_{1}\cdots\mathrm{d}t_{2q}$ $\displaystyle=\sum_{i=1}^{d}\alpha_{i}g_{i}\ast F_{n}^{2q,P}(z),$ $$

where the sum $\sum_{j,l,r_{1},\ldots,r_{2q-1}=0}^{-1}$ is set as 0 0, $g_{i}(t)=\overline{x_{i}(t_{1})}\cdots\overline{x_{i}(t_{q})}y_{i}(t_{q+1})
\cdots y_{i}(t_{2q})$ for $t=[t_{1},\ldots,t_{2q}]\in\mathbb{T}^{2q}$, and $P=\{r=[r_{1},\ldots,r_{2q}]\in\mathbb{R}^{2q}\,\mid\,|\sum_{i=l}^{m}r_{i}|\leq
1
,\ l\leq m\}$.
In addition, we set $j=r_{0}$ and $j=r_{q}$.
The second to the last equality is derived by Lemma 9 below.
Since $P$ is a convex polyhedron, $g_{i}\ast F_{n}^{2q,P}(z)\to g_{i}(z)$ as $n\to\infty$ by Lemma 10.
For $k_{n}^{\operatorname{sep},q}$, we additionally use the fact $\lim_{n\to\infty}\tilde{k}(S_{n}(R_{n}(x)),S_{n}(R_{n}(y)))=\tilde{k}(\lim_{n
\to\infty}S_{n}(R_{n}(x)),\lim_{n\to\infty}S_{n}(R_{n}(y)))$, which follows from the continuity of $\tilde{k}$, and the fact $S_{n}(R_{n}(x))\to x$ uniformly as $n\to\infty$ if $x$ and $y$ are differentiable (van Suijlekom, , Lemma 10).
$\Box$

Lemma 9
For $m\in\mathbb{N}$ and $j=0,\ldots 2q$, let $Q_{j}^{m}=\{r^{\prime}=[r_{1}^{\prime},\ldots,r_{2q}^{\prime}]\in\mathbb{R}^{2
q}\,\mid\,r_{i}^{\prime}=r_{i}-r_{i-1}\ (i=1,\ldots,2q),\ 0\leq r_{i}\leq m\ (
i=0,\ldots,2q),\ r_{j}=m\}$ and $P=\{r=[r_{1},\ldots,r_{2q}]\in\mathbb{R}^{2q}\,\mid\,|\sum_{i=l}^{k}r_{i}|\leq
1
,\ l\leq k\}$.
Then, we have $mP=\bigcup_{j=0}^{2q}Q_{j}^{m}$.

Proof  Let $r^{\prime}\in Q_{j}^{m}$.
For $i>j$, we have $r_{i}=r_{i}^{\prime}+r_{i-1}=r_{i}^{\prime}+(r_{i-1}^{\prime}+r_{i-2})=\cdots=
r_{i}^{\prime}+\cdots+r_{j+1}^{\prime}+m$, and for $i<j$, we have $-r_{i}=r_{i+1}^{\prime}-r_{i+1}=r_{i+1}^{\prime}+(r_{i+2}^{\prime}-r_{i+2})=
\cdots=r_{i+1}^{\prime}+\cdots+r_{j}^{\prime}-m$.
Therefore, we have

$$ $\displaystyle\bigcup_{j=0}^{2q}Q_{j}^{m}$ $\displaystyle=\bigcup_{j=0}^{2q}\bigg{\{}r\in\mathbb{R}^{2q}\,\bigg{|}\,r_{i}= \sum_{l=j+1}^{i}r_{l}^{\prime}+m\ (j<i\leq 2q),\ r_{i}=-\sum_{l=i+1}^{j}r_{l}^ {\prime}+m\ (0\leq i<j),$ $\displaystyle\qquad\qquad 0\leq r_{i}\leq m\ (i=0,\ldots,j-1,j+1,\ldots 2q)\}$ $\displaystyle=\bigcup_{j=0}^{2q}\bigg{\{}r^{\prime}\in\mathbb{R}^{2q}\,\bigg{| }\,-m\leq\sum_{l=j+1}^{i}r_{l}^{\prime}\leq 0\ (j<i\leq 2q),\ 0\leq\sum_{l=i+1 }^{j}r_{l}^{\prime}\leq m\ (0\leq i<j)\bigg{\}}$ $\displaystyle=\bigg{\{}r\in\mathbb{R}^{2q}\,\bigg{|}\,\bigg{|}\sum_{i=l}^{k}r_ {i}\bigg{|}\leq 1,\ l\leq k\bigg{\}},$ $$

which completes the proof of the lemma.
$\Box$

Proposition 12
The kernels $k_{n}^{\operatorname{poly},q}$ and $k_{n}^{\operatorname{sep},q}$ are positive definite.

Proof  Let $x_{1},\ldots,x_{N}\in\mathcal{A}^{d}$ and $d_{1},\ldots,d_{N}\in\mathcal{A}$.
Then, we have

$$ $\displaystyle\bigg{(}\sum_{j,l=1}^{N}d_{j}^{*}k_{n}^{\operatorname{poly},q}(x_ {j},x_{l})d_{l}\bigg{)}(z)$ $\displaystyle=\sum_{j,l=1}^{N}\overline{d_{j}(z)}\sum_{j^{\prime},l^{\prime}=1 }^{n}\sum_{i=1}^{d}\alpha_{i}\sum_{m=1}^{n}\big{(}(R_{n}(x_{i,j})^{*})^{q}\big {)}_{j^{\prime},m}\big{(}R_{n}(x_{i,l})^{q}\big{)}_{m,l^{\prime}}\mathrm{e}^{ \mathrm{i}(j^{\prime}-l^{\prime})z}d_{l}(z)$ $\displaystyle=\sum_{i=1}^{d}\alpha_{i}\sum_{m=1}^{n}\bigg{|}\sum_{j=1}^{N}\sum _{j^{\prime}=1}^{n}d_{j}(z)\big{(}(R_{n}(x_{i,j}))^{q}\big{)}_{m,j^{\prime}} \mathrm{e}^{-\mathrm{i}j^{\prime}z}\bigg{|}^{2}\geq 0$ $$

for $z\in\mathbb{T}$.
In addition, let $\tilde{x}_{n,j}=S_{n}(R_{n}(x_{j}))$. Then, we have

$$ $\displaystyle\bigg{(}\sum_{j,l=1}^{N}d_{j}^{*}k_{n}^{\operatorname{sep},q}(x_{ j},x_{l})d_{l}\bigg{)}(z)$ $\displaystyle=\sum_{j,l=1}^{N}\overline{d_{j}(z)}\tilde{k}(\tilde{x}_{n,j}, \tilde{x}_{n,l})d_{l}(z)\sum_{j^{\prime},l^{\prime}=1}^{n}\sum_{m_{1},\ldots,m _{2q-1}=1}^{n}$ $\displaystyle\big{(}(R_{n}(a)^{*})\big{)}_{j^{\prime},m_{1}}\big{(}(R_{n}(a)^{ *})\big{)}_{m_{1},m_{2}}\cdots\big{(}(R_{n}(a)^{*})\big{)}_{m_{q-1},m_{q}}\big {(}R_{n}(a)\big{)}_{m_{q},m_{q+1}}\cdots\big{(}R_{n}(a)\big{)}_{m_{2q-1},l^{ \prime}}\mathrm{e}^{\mathrm{i}(j^{\prime}-l^{\prime})z}$ $\displaystyle=\sum_{j,l=1}^{N}\overline{d_{j}(z)}\tilde{k}(\tilde{x}_{n,j}, \tilde{x}_{n,l})d_{l}(z)$ $\displaystyle\qquad\sum_{m_{q}=1}^{n}\bigg{|}\sum_{j^{\prime}=1}^{n}\sum_{m_{1 },\ldots,m_{q-1}=1}^{n}\big{(}R_{n}(a)\big{)}_{m_{q},m_{1}}\cdots\big{(}R_{n}( a)\big{)}_{m_{q-2},m_{q-1}}\big{(}R_{n}(a)\big{)}_{m_{q-1},j^{\prime}}\mathrm{ e}^{-\mathrm{i}j^{\prime}z}\bigg{|}^{2}$ $\displaystyle\geq 0.$ $$

Thus, $k_{n}^{\operatorname{poly},q}$ and $k_{n}^{\operatorname{sep},q}$ are positive definite.
$\Box$

Proposition 13
Let $\beta_{n}\geq-\min_{z\in\mathbb{T}^{q}}F_{n}^{2q,P}(z)$.
Then, $\hat{k}_{n}^{\operatorname{prod},q}$ defined below is positive definite.

$$ $\displaystyle\hat{k}_{n}^{\operatorname{prod},q}(x,y)=k_{n}^{\operatorname{ prod},q}(x,y)+\beta_{n}\int_{\mathbb{T}^{2q}}\prod_{j=1}^{q}\overline{\tilde{k }_{1,j}(x(t_{j}),y(t_{j}))}\tilde{k}_{2,j}(x(t_{q+j}),y(t_{q+j}))\mathrm{d}t.$ $$

Proof  Let $x_{1},\ldots,x_{N}\in\mathcal{A}^{d}$ and $d_{1},\ldots,d_{N}\in\mathcal{A}$.
Then, we have

$$ $\displaystyle\bigg{(}\sum_{j,l=1}^{N}d_{j}^{*}\hat{k}_{n}^{\operatorname{prod} ,q}(x_{j},x_{l})d_{l}\bigg{)}(z)$ $\displaystyle=\sum_{m,l=1}^{N}\int_{\mathbb{T}^{2q}}\overline{d_{m}(z)}\bigg{( }\prod_{j=1}^{q}\overline{\tilde{k}_{1,j}(x_{m}(t_{j}),x_{l}(t_{j}))}\tilde{k} _{2,j}(x_{m}(t_{q+j}),x_{l}(t_{q+j}))\bigg{)}d_{l}(z)F_{n}^{2q,P}(z\mathbf{1}- t)\mathrm{d}t$ $\displaystyle\qquad+\beta_{n}\sum_{m,l=1}^{N}\int_{\mathbb{T}^{2q}}\overline{d _{m}(z)}\bigg{(}\prod_{j=1}^{q}\overline{\tilde{k}_{1,j}(x_{m}(t_{j}),x_{l}(t_ {j}))}\tilde{k}_{2,j}(x_{m}(t_{q+j}),x_{l}(t_{q+j}))\bigg{)}d_{l}(z)\mathrm{d}t$ $\displaystyle=\sum_{m,l=1}^{N}\int_{\mathbb{T}^{2q}}\overline{d_{m}(z)}\bigg{( }\prod_{j=1}^{q}\overline{\tilde{k}_{1,j}(x_{m}(t_{j}),x_{l}(t_{j}))}\tilde{k} _{2,j}(x_{m}(t_{q+j}),x_{l}(t_{q+j}))\bigg{)}d_{l}(z)(F_{n}^{2q,P}(z\mathbf{1} -t)+\beta_{n})\mathrm{d}t$ $\displaystyle\geq 0$ $$

for $z\in\mathbb{T}$.
The last inequality is derived since the map $([x_{1},\ldots,x_{2q}],[y_{1},\ldots,y_{2q}])\mapsto\prod_{j=1}^{q}\overline{
\tilde{k}_{1,j}(x_{2j-1},y_{2j-1})}\tilde{k}_{2,j}(x_{2j},y_{2j})$ is positive definite and $F_{n}^{2q,P}(z\mathbf{1}-t)+\beta_{n}\geq 0$.
$\Box$

Lemma 14
We have $|F_{n}^{q,P}(z)|\leq n^{q}$.

Proof  The number of terms in $F_{n}^{q,P}$ is equal to the number of terms in $\sum_{m,l=0}^{n-1}(T_{1}\cdots T_{2q})_{m,l}$, where $T_{1},\ldots,T_{2q}$ are Toeplitz matrices.
Thus, we have

$$ $\displaystyle|F_{n}^{q,P}(z)|\leq\frac{1}{n}n^{q+1}=n^{q}.$ $$

$\Box$

Let $\Omega$ be a probability space with a probability measure $\mu$.
Let $X_{1},\ldots,X_{N}$ and $Y_{1},\ldots,Y_{N}$ be samples from a distributions of $\mathcal{A}_{0}^{d}$-valued random variable $X$ and $\mathcal{A}_{1}$-valued random variable $Y$ on $\Omega$, respectively (i.e., for $z\in\mathbb{T}$, $X_{i}(z)$ is a sample from the distribution of $X(z)$).
Here, $\mathcal{A}_{0}$ and $\mathcal{A}_{1}$ are subsets of $\mathcal{A}$.

Theorem 16
Assume $k_{n}^{\operatorname{poly},q}$, $k_{n}^{\operatorname{prod},q}$, and $k_{n}^{\operatorname{sep}q}$ are real-valued.
Let $D(k_{n}^{\operatorname{poly},q},x)=\sum_{j=1}^{d}\alpha_{j}\|R_{n}(x_{j})\|^{2
q}_{\operatorname{op}}$, $D(\hat{k}_{n}^{\operatorname{prod},q},x)=\prod_{j=1}^{q}(\|R_{n}(\tilde{k}_{1,
j}(x,x))\|_{\operatorname{op}}\|R_{n}(\tilde{k}_{2,j}(x,x))\|_{\operatorname{
op}})+\beta_{n}C$, and $D(k_{n}^{\operatorname{sep},q},x)=\tilde{k}(x,x)\prod_{j=1}^{q}\|R_{n}(a_{j})
\|_{\operatorname{op}}^{2}$ for $x\in\mathcal{A}_{0}^{d}$, where $\|\cdot\|_{\operatorname{op}}$ is the operator norm and $C=\prod_{j=1}^{q}\int_{\mathbb{T}}\tilde{k}_{1,j}(x(t),x(t))\mathrm{d}t\int_{
\mathbb{T}}\tilde{k}_{2,j}(x(t),x(t))\mathrm{d}t$.
Assume $\beta_{n}\leq\beta_{n+1}$ for $\hat{k}_{n}^{\operatorname{prod},q}$.
For $k_{n}=k_{n}^{\operatorname{poly},q},\hat{k}_{n}^{\operatorname{prod},q},k_{n}^
{\operatorname{sep},q}$ and
for any $\delta\in(0,1)$, with probability at least $1-\delta$, we have

$$ $\displaystyle\mathrm{E}[g(f(X),Y)]\leq_{\mathcal{A}}\frac{1}{N}\sum_{i=1}^{N}g (f(X_{i}),Y_{i})+2L\frac{B}{N}\bigg{(}\sum_{i=1}^{N}D(k_{n},X_{i})\bigg{)}^{1/ 2}1_{\mathcal{A}}+3\sqrt{\frac{\log 1/\delta}{N}}1_{\mathcal{A}}$ $$

for any $f\in\mathcal{F}$.
In addition, we have $D(k_{n},x)\leq D(k_{n+1},x)$.

To show Theorem 16, we use the $\mathcal{A}$-valued Rademacher complexity defined by Hashimoto et al. ().
Let $\sigma_{1},\ldots,\sigma_{N}$
be i.i.d. Rademacher variables, which take their values on $\{-1,1\}$.
For a real-valued function class $\mathcal{F}$ and $\mathbf{x}=[x_{1},\ldots,x_{N}]\in(\mathcal{A}^{d})^{N}$, the empirical Rademacher complexity $\hat{R}_{N}(\mathbf{x},\mathcal{F})$ is defined by
$\hat{R}_{N}(\mathbf{x},\mathcal{F})=\mathrm{E}[\sup_{f\in\mathcal{F}}\sum_{i=1
}^{N}f(x_{i})\sigma_{i}]/N$.
Here, $\mathrm{E}$ is the integration on $\Omega$ with respect to $\mu$.
Similar to the case of the standard Rademacher complexity, an $\mathcal{A}$-valued version of the Rademacher complexity is defined as
$\hat{R}_{\mathcal{A},N}(\mathbf{x},\mathcal{F})=\mathrm{E}[\sup^{\mathcal{A}}_
{f\in\mathcal{F}}\sum_{i=1}^{N}|f(x_{i})^{*}\sigma_{i}|_{\mathcal{A}}]/N$ for an $\mathcal{A}$-valued function class $\mathcal{F}$.
Here, $|a|_{\mathcal{A}}=(a^{*}a)^{1/2}$ for $a\in\mathcal{A}$, $\sup^{\mathcal{A}}$ is the supremum in the sense of the order in $\mathcal{A}$ (see Definition 3), and the integral $\mathrm{E}$ means the Bochner integral in this case.

Indeed, in our case, the $\mathcal{A}$-valued Rademacher complexity is represented by the standard Rademacher complexity, and the argument is reduced to evaluate the standard Rademacher complexity.
In the following, we denote by $\mathcal{A}_{+}$ the subset of $\mathcal{A}$ composed of all positive elements in $\mathcal{A}$.

###### Proposition 20

Let $\mathcal{F}$ be an $\mathcal{A}$-valued function class.
Assume for any $x\in\mathcal{A}_{0}^{d}$ and $z\in\mathbb{T}$, $f(x)(z)\in\mathbb{R}$.
Then, we have $\hat{R}_{N}(\mathbf{x},\mathcal{F}(z))=\hat{R}_{\mathcal{A},N}(\mathbf{x},
\mathcal{F})(z)$, where $\mathcal{F}(z)=\{x\mapsto(f(x))(z)\,\mid\,f\in\mathcal{F}\}$.

Proof  We first show $(\sup^{\mathcal{A}}_{a\in\mathcal{S}}a)(z)=\sup_{a\in\mathcal{S}}a(z)$ for $\mathcal{S}\subseteq\mathcal{A}_{+}$ for any $z\in\mathbb{T}$.
Let $a\in\mathcal{S}$.
Since $a(z)\leq\sup_{a\in\mathcal{S}}a(z)$ for any $z\in\mathbb{T}$, we have $a\leq_{\mathcal{A}}b$, where $b\in\mathcal{A}$ is defined as $b(z)=\sup_{a\in\mathcal{S}}a(z)$.
Thus, $b$ is an upper bound of $\mathcal{S}$, and we have $\sup^{\mathcal{A}}_{a\in\mathcal{S}}a\leq_{\mathcal{A}}b$, which means $(\sup^{\mathcal{A}}_{a\in\mathcal{S}}a)(z)\leq\sup_{a\in\mathcal{S}}a(z)$ for any $z\in\mathbb{T}$.
Conversely, since $a\leq_{\mathcal{A}}\sup^{\mathcal{A}}_{a\in\mathcal{S}}a$ for $a\in\mathcal{S}$, we have $a(z)\leq(\sup^{\mathcal{A}}_{a\in\mathcal{S}}a)(z)$ for any $z\in\mathbb{T}$.
Thus, we have $\sup_{a\in\mathcal{S}}a(z)\leq(\sup^{\mathcal{A}}_{a\in\mathcal{S}}a)(z)$.

Therefore, we have

$$ $\displaystyle\hat{R}_{\mathcal{A},N}(\mathbf{x},\mathcal{F})(z)$ $\displaystyle=\frac{1}{N}\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\!^{\mathcal{ A}}\bigg{|}\sum_{i=1}^{N}f(x_{i})^{*}\sigma_{i}\bigg{|}_{\mathcal{A}}\bigg{]}( z)=\frac{1}{N}\mathrm{E}\bigg{[}\bigg{(}\sup_{f\in\mathcal{F}}\!^{\mathcal{A}} \bigg{|}\sum_{i=1}^{N}f(x_{i})^{*}\sigma_{i}\bigg{|}_{\mathcal{A}}\bigg{)}(z) \bigg{]}$ $\displaystyle=\frac{1}{N}\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}(z)}\bigg{|} \sum_{i=1}^{N}\overline{f(x_{i})}\sigma_{i}\bigg{|}\bigg{]}=\frac{1}{N}\mathrm {E}\bigg{[}\sup_{f\in\mathcal{F}(z)}\bigg{|}\sum_{i=1}^{N}f(x_{i})\sigma_{i} \bigg{|}\bigg{]}=\hat{R}_{N}(\mathbf{x},\mathcal{F}(z)),$ $$

where the third equality is given by the identity $|a|_{\mathcal{A}}(z)=|a(z)|$, and the forth equality is satisfied since $\sigma_{i}$ is real-valued.
$\Box$

We obtain the following lemma directly by Lemma 4.2 in Mohri et al. ().

###### Lemma 21

Let $\mathcal{F}$ be an $\mathcal{A}$-valued function class.
Let $g:\mathbb{R}\times\mathbb{R}\to\mathbb{R}_{+}$ be an error function. Assume there exists $L>0$ such that for $y\in\mathcal{A}_{1}$ and $z\in\mathbb{T}$, $x\mapsto g(x,y(z))$ is $L$-Lipschitz continuous.
Assume also for any $x\in\mathcal{A}_{0}^{d}$ and $z\in\mathbb{T}$, $f(x)(z)\in\mathbb{R}$.
Then, we have

$$ $\displaystyle\frac{1}{N}\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\sum_{i=1}^{N} g(f(x_{i})(z),y_{i}(z))\sigma_{i}\bigg{]}=\frac{1}{N}\mathrm{E}\bigg{[}\sup_{f \in\mathcal{F}(z)}\sum_{i=1}^{N}g(f(x_{i}),y_{i}(z))\sigma_{i}\bigg{]}\leq L \hat{R}_{N}(\mathbf{x},\mathcal{F}(z)).$ $$

We apply the following lemma to obtain the inequality (3).

###### Lemma 22

Let $\mathcal{F}$ be an $\mathcal{A}$-valued function class.
Let $g$ be the same map defined in Lemma 21.
For any $f\in\mathcal{F}$ and any $\delta\in(0,1)$, with probability at least $1-\delta$, we have

$$ $\displaystyle\mathrm{E}[g(f(X),Y)](z)\leq\frac{1}{N}\sum_{i=1}^{N}g(f(X_{i}),Y _{i})(z)+\frac{2}{N}\mathrm{E}_{\sigma_{i}}\bigg{[}\sup_{f\in\mathcal{F}}\sum_ {i=1}^{N}g(f(X_{i})(z),Y_{i}(z))\sigma_{i}\bigg{]}+3\sqrt{\frac{\log 1/\delta} {N}}.$ $$

Here, $\mathrm{E}_{\sigma_{i}}[\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}g(f(X_{i})(z),Y_{i
}(z))\sigma_{i}]=\int_{\Omega}\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}g(f(X_{i})(z
),Y_{i}(z))\sigma_{i}(\omega)\mathrm{d}\mu(\omega)$.

Proof  With probability at least $1-\delta$, we have

$$ $\displaystyle\mathrm{E}[g(f(X),Y)](z)=\mathrm{E}[g(f(X)(z),Y(z))]$ $\displaystyle\quad\leq\frac{1}{N}\sum_{i=1}^{N}g(f(X_{i})(z),Y_{i}(z))+\frac{2 }{N}\mathrm{E}_{\sigma_{i}}\bigg{[}\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}g(f(X_{ i})(z),Y_{i}(z))\sigma_{i}\bigg{]}+3\sqrt{\frac{\log 1/\delta}{N}}$ $\displaystyle\quad=\frac{1}{N}\sum_{i=1}^{N}g(f(X_{i}),Y_{i})(z)+\frac{2}{N} \mathrm{E}_{\sigma_{i}}\bigg{[}\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}g(f(X_{i})( z),Y_{i}(z))\sigma_{i}\bigg{]}+3\sqrt{\frac{\log 1/\delta}{N}}.$ $$

The inequality follows by Theorem 3.1 in Mohri et al. ().
$\Box$

According to Hashimoto et al. (), the $\mathcal{A}$-valued Rademacher complexity for the RKHM associated with an $\mathcal{A}$-valued kernel $k$ is upperbounded by $\|k(x_{i},x_{i})\|_{\mathcal{A}}$ as follows.

###### Lemma 23

Let $B>0$ and $\mathcal{F}=\{f\in\mathcal{M}_{k}\,\mid\,\|f\|_{k}\leq B\}$.
Then, we have

$$ $\displaystyle\hat{R}_{\mathcal{A},N}(\mathbf{x},\mathcal{F})\leq_{\mathcal{A}} \frac{B}{N}\bigg{(}\sum_{i=1}^{N}\|k(x_{i},x_{i})\|_{\mathcal{A}}\bigg{)}^{1/2 }1_{\mathcal{A}}.$ $$

Combining these results with the following lemma completes the proof of Theorem 16.

###### Lemma 24

Let $k_{n}$ be $k_{n}^{\operatorname{poly},q}$, $\hat{k}_{n}^{\operatorname{prod},q}$, or $k_{n}^{\operatorname{sep},q}$ defined in Section 3.
Then, for $x\in\mathcal{A}_{0}^{d}$, $D(k_{n},x)\leq D(k_{n+1},x)$.

Proof  We evaluate $\|k_{n}(x,x)\|_{\mathcal{A}}$.
For $k_{n}^{\operatorname{poly},q}$, we have

$$ $\displaystyle\|k_{n}^{\operatorname{poly},q}(x,x)\|$ $\displaystyle=\bigg{\|}S_{n}\bigg{(}\sum_{i=1}^{d}\alpha_{i}(R_{n}(x_{i})^{*}) ^{q}R_{n}(x_{i})^{q}\bigg{)}\bigg{\|}_{\mathcal{A}}\leq\bigg{\|}\sum_{i=1}^{d} \alpha_{i}(R_{n}(x_{i})^{*})^{q}R_{n}(x_{i})^{q}\bigg{\|}_{\operatorname{op}}$ $\displaystyle\leq\sum_{i=1}^{d}\alpha_{i}\|R_{n}(x_{i})\|^{2q}_{\operatorname{ op}}.$ $$

The first inequality is derived by the following inequalities for $A\in\mathbb{C}^{n\times n}$:

$$ $\displaystyle|S_{n}(A)(z)|$ $\displaystyle=\bigg{|}\frac{1}{n}\sum_{j,l=0}^{n-1}A_{j,l}\mathrm{e}^{\mathrm{ i}(j-l)z}\bigg{|}$ $\displaystyle=\bigg{|}\operatorname{tr}\bigg{(}\frac{1}{n}\mathbf{1} \operatorname{diag}(\mathrm{e}^{0},\ldots,\mathrm{e}^{\mathrm{i}(n-1)})A \operatorname{diag}(\mathrm{e}^{0z},\ldots,\mathrm{e}^{\mathrm{i}(n-1)z})\bigg {)}\bigg{|}$ $\displaystyle\leq\frac{1}{n}\|\mathbf{1}\|_{1}\|\operatorname{diag}(\mathrm{e} ^{0},\ldots,\mathrm{e}^{\mathrm{i}(n-1)})A\operatorname{diag}(\mathrm{e}^{0z}, \ldots,\mathrm{e}^{\mathrm{i}(n-1)z})\|_{\operatorname{op}}\leq\|A\|_{ \operatorname{op}}$ $$

for any $z\in\mathbb{T}$.
Here, $\operatorname{tr}(A)$ is the trace of a matrix $A$, $\operatorname{diag}(a_{1},\ldots,a_{n})$ for $a_{1},\ldots,a_{n}\in\mathbb{C}$ is the diagonal matrix whose diagonal elements are $a_{1},\ldots,a_{n}$, $\mathbf{1}\in\mathbb{C}^{n\times n}$ is the matrix whose elements are all $1$, and $\|A\|_{1}$ for $A\in\mathbb{C}^{n\times n}$ is the trace norm defined as $\|A\|_{1}=\operatorname{tr}((A^{*}A)^{1/2})$.
We used the inequality $|\operatorname{tr}(AB)|\leq\|A\|_{1}\|B\|_{\operatorname{op}}$ for $A,B\in\mathbb{C}^{n\times n}$ (Conway, , Chapter IX, Section 2).

In addition, there exists $v\in\mathbb{C}^{n\times n}$ such that $\|R_{n}(x)\|_{\operatorname{op}}=\|R_{n}(x)v\|$ and $\|v\|=1$.
Thus, we have

$$ $\displaystyle\|R_{n}(x)\|_{\operatorname{op}}$ $\displaystyle=\|R_{n}(x)v\|=\|Q_{n}^{*}M_{x}Q_{n}v\|=\bigg{\|}Q_{n}^{*}M_{x}Q_ {n+1}\begin{bmatrix}v\\ 0\end{bmatrix}\bigg{\|}\leq\bigg{\|}Q_{n+1}^{*}M_{x}Q_{n+1}\begin{bmatrix}v\\ 0\end{bmatrix}\bigg{\|}$ $\displaystyle\leq\|Q_{n+1}^{*}M_{x}Q_{n+1}\|_{\operatorname{op}}=\|R_{n+1}(x) \|_{\operatorname{op}},$ $$

where $Q_{n}=[e_{1},\ldots,e_{n}]$ and $e_{j}(z)=\mathrm{e}^{\mathrm{i}jz}$ is the Fourier function.
$\Box$

###### Proposition 20

###### Lemma 21

###### Lemma 22

###### Lemma 23

###### Lemma 24

## Appendix B Details of Remark 11

To understand the relationship between $q$ and the interactions, we observe the convergence shown in Lemma 10 from the perspective of $q$.
The following lemma is by Brandlini and Travaglini Brandolini & Travaglini ().

###### Lemma 25

Let $H_{n}^{q,P}(t)=n^{q}\int_{0}^{1}\int_{\mathbb{R}^{q}}\chi_{jP}(r)\mathrm{e}^{
\mathrm{i}nr\cdot t}\mathrm{d}r\mathrm{d}j$ for $t\in\mathbb{T}^{q}$, where $\chi_{S}$ is the characteristic function with respect to a set $S$.
Then, we have $F_{n}^{q,P}(t)=\sum_{m\in\mathbb{Z}^{q}}H_{n}^{q,P}(t+2\pi m)$.

Proof  Let $u_{j,t}(r)=\chi_{jP}(r)\mathrm{e}^{\mathrm{i}r\cdot t}$.
Then, we have

$$ $\displaystyle F_{n}^{q,P}(t)$ $\displaystyle=\frac{1}{n}\sum_{j=1}^{n-1}\sum_{r\in jP\bigcap\mathbb{Z}^{q}} \mathrm{e}^{\mathrm{i}r\cdot t}=\frac{1}{n}\int_{0}^{n}\sum_{r\in\mathbb{Z}^{q }}\chi_{jP}(r)\mathrm{e}^{\mathrm{i}r\cdot t}\mathrm{d}j=\frac{1}{n}\int_{0}^{ n}\sum_{r\in\mathbb{Z}^{q}}u_{j,t}(r)\mathrm{d}j$ $\displaystyle=\frac{1}{n}\int_{0}^{n}\sum_{m\in\mathbb{Z}^{q}}\widehat{u_{j,t} }(m)\mathrm{d}j=\sum_{m\in\mathbb{Z}^{q}}\frac{1}{n}\int_{0}^{n}\int_{\mathbb{ R}^{q}}\chi_{jP}(r)\mathrm{e}^{\mathrm{i}r\cdot t}\mathrm{e}^{2\pi\mathrm{i}r \cdot m}\mathrm{d}r\mathrm{d}j$ $\displaystyle=\sum_{m\in\mathbb{Z}^{q}}\int_{0}^{1}\int_{\mathbb{R}^{q}}\chi_{ jnP}(r)\mathrm{e}^{\mathrm{i}r\cdot t}\mathrm{e}^{2\pi\mathrm{i}r\cdot m} \mathrm{d}r\mathrm{d}j=\sum_{m\in\mathbb{Z}^{q}}\int_{0}^{1}\int_{\mathbb{R}^{ q}}\chi_{jP}\bigg{(}\frac{r}{n}\bigg{)}\mathrm{e}^{\mathrm{i}r\cdot t}\mathrm{ e}^{2\pi\mathrm{i}r\cdot m}\mathrm{d}r\mathrm{d}j$ $\displaystyle=n^{q}\sum_{m\in\mathbb{Z}^{q}}\int_{0}^{1}\int_{\mathbb{R}^{q}} \chi_{jP}(r)\mathrm{e}^{\mathrm{i}nr\cdot t}\mathrm{e}^{2\pi\mathrm{i}nr\cdot m }\mathrm{d}r\mathrm{d}j,$ $$

where $\hat{\cdot}$ is the Fourier transform, and the forth equality is by the Poisson summation formula.
$\Box$

To understand the convergence, we split $F_{n}^{q,P}(t)=\sum_{m\in\mathbb{Z}^{q}}H_{n}^{q,P}(t+2\pi m)$ into two parts: $H_{n}^{q,P}(t)$ and $\tilde{H}_{n}^{q,P}(t):=\sum_{m\neq 0}H_{n}^{q,P}(t+2\pi m)$.
In the convergence discussed in Lemma 10, the convolution $g\ast{H}_{n}^{q,P}(z)$ goes to $g(z)$.
On the other hand, $g\ast\tilde{H}_{n}^{q,P}(z)$ goes to 0 0 (Brandolini & Travaglini, , Theorem 1).
Regarding the convergence of $g\ast{H}_{n}^{q,P}(z)$ we can evaluate it as follows, especially for $q=2$.

###### Lemma 26

For $z\in\mathbb{T}$, we have

$$ $\displaystyle\lim_{n\to\infty}g\ast H_{n}^{q,P}(z)-g(z)=\int_{0}^{1}\lim_{n\to \infty}\bigg{(}\int_{t\in\mathbb{T}^{q}}\int_{jnP}\mathrm{e}^{\mathrm{i}r\cdot (z-t)}g(t)\mathrm{d}r\mathrm{d}t-g(z)\bigg{)}\mathrm{d}j.$ $$

Moreover, let $h^{P}_{s}(z)=\int_{t\in\mathbb{T}^{q}}\int_{sP}\mathrm{e}^{\mathrm{i}r\cdot(z-
t)}g(t)\mathrm{d}r\mathrm{d}t-g(z)$.
Let $q=2$, $Q=\{(r_{1},-r_{2})\,\mid\,(r_{1},r_{2})\in P\}$, $P_{1}^{\prime}=[-1,1]$, and $P_{2}=\{(r_{1},r_{2})\,\mid\,|r_{1}|\leq 1,\ |r_{2}|\leq 1,\ |r_{1}+r_{2}|\leq
1
,\ |r_{1}-r_{2}|\leq 1\}$.
Let $g(z)=\overline{x_{1}(z_{1})}\overline{x_{2}(z_{2})}y_{1}(z_{3})y_{4}(z_{4})$ for $z=[z_{1},z_{2},z_{3},z_{4}]$.
Then, for $z\in\mathbb{T}^{2}$, there exists $C(z)\geq 0$ such that we have

$$ $\displaystyle\frac{1}{2}|h^{P}_{jn}(z)+h^{Q}_{jn}(z)|\leq\frac{1}{2}C(z)\sum_{ j=1}^{2}$ $\displaystyle\bigg{|}\int_{t\in\mathbb{T}}\int_{jnP_{1}^{\prime}}\mathrm{e}^{ \mathrm{i}r(z_{1}-t)}x_{j}(t_{j})\mathrm{d}r\mathrm{d}t-x_{j}(z_{j})\bigg{|}$ $\displaystyle+\frac{1}{2}\bigg{|}\int_{\mathbb{T}^{2}}\int_{jnP_{2}}\mathrm{e} ^{\mathrm{i}r\cdot(z-t)}g(t)\mathrm{d}r\mathrm{d}t_{1}-g(z)\bigg{|}.$ (7) $$

Proof  We have

$$ $\displaystyle n^{q}\int_{t\in\mathbb{T}^{q}}\int_{0}^{1}\int_{jP}\mathrm{e}^{ \mathrm{i}nr\cdot(z-t)}g(t)\mathrm{d}r\mathrm{d}j\mathrm{d}t-g(z)=\int_{0}^{1} \int_{t\in\mathbb{T}^{q}}\int_{jnP}\mathrm{e}^{\mathrm{i}r\cdot(z-t)}g(t) \mathrm{d}r\mathrm{d}t-g(z)\mathrm{d}j.$ $$

Let ${h}^{P}_{s}(z)=\int_{t\in\mathbb{T}}\int_{sP}\mathrm{e}^{\mathrm{i}r\cdot(z-t)
}g(t)\mathrm{d}r\mathrm{d}t-g(z)$.
Then, $h^{P}_{0}(z)=0$, and since $\lim_{s\to\infty}h^{P}_{s}(z)=0$, there exists $D(z)>0$ such that $|h^{P}_{s}(z)|\leq D(z)$ for any $s>0$.
Thus, $|h^{P}_{jn}(z)|\leq D(z)$ for any $n\in\mathbb{N}$ and $0<j\leq 1$.
Thus, by the bounded convergence theorem,
we have

$$ $\displaystyle\lim_{n\to\infty}\int_{0}^{1}\int_{t\in\mathbb{T}^{q}}\int_{jnP} \mathrm{e}^{\mathrm{i}r\cdot(z-t)}g(t)\mathrm{d}r\mathrm{d}t-g(z)\mathrm{d}j= \int_{0}^{1}\lim_{n\to\infty}\int_{t\in\mathbb{T}^{q}}\int_{jnP}\mathrm{e}^{ \mathrm{i}r\cdot(z-t)}g(t)\mathrm{d}r\mathrm{d}t-g(z)\mathrm{d}j.$ $$

In addition, let $P_{1}=[-1,1]^{2}$ and $P_{2}=\{(r_{1},r_{2})\,\mid\,|r_{1}|\leq 1,\ |r_{2}|\leq 1,\ |r_{1}+r_{2}|\leq
1
,\ |r_{1}-r_{2}|\leq 1\}$.
Then, we have

$$ $\displaystyle h^{P}_{jn}(z)+h^{Q}_{jn}(z)=h^{P_{1}}_{jn}(z)+h^{P_{2}}_{jn}(z).$ $$

For $h^{P_{1}}_{jn}(z)$, we have

$$ $\displaystyle|h^{P_{1}}_{jn}(z)|$ $\displaystyle=\bigg{|}\int_{\mathbb{T}}\int_{-jn}^{jn}\mathrm{e}^{\mathrm{i}r( z_{1}-t)}x_{1}(t)\mathrm{d}r\mathrm{d}t\int_{\mathbb{T}}\int_{-jn}^{jn}\mathrm {e}^{\mathrm{i}r(z_{2}-t)}x_{2}(t)\mathrm{d}r\mathrm{d}t-g(z)\bigg{|}$ $\displaystyle\leq\bigg{|}\int_{\mathbb{T}}\int_{-jn}^{jn}\mathrm{e}^{\mathrm{i }r(z_{1}-t)}x_{1}(t)\mathrm{d}r\mathrm{d}t\bigg{(}\int_{\mathbb{T}}\int_{-jn}^ {jn}\mathrm{e}^{\mathrm{i}r(z_{2}-t)}x_{2}(t)\mathrm{d}r\mathrm{d}t-x_{2}(z_{2 })\bigg{)}\bigg{|}$ $\displaystyle\quad+\bigg{|}x_{2}(z_{2})\bigg{(}\int_{\mathbb{T}}\int_{-jn}^{jn }\mathrm{e}^{\mathrm{i}r(z_{1}-t)}x_{1}(t)\mathrm{d}r\mathrm{d}t-x_{1}(z_{1}) \bigg{)}\bigg{|}.$ $$

In the same manner as $h_{s}^{P}(z)$, there exists $\tilde{C}(z)>0$ such that $|\int_{\mathbb{T}}\int_{-jn}^{jn}\mathrm{e}^{\mathrm{i}r(z_{1}-t)}x_{1}(t)
\mathrm{d}r\mathrm{d}t|\leq\tilde{C}(z)$.
By setting $C(z)=\max\{\tilde{C}(z),|x_{2}(z_{2})|\}$, we obtain the result.
$\Box$

The left hand side is the average of $h_{jn}^{P}(z)$ and $h_{jn}^{Q}(z)$, where $P$ and $Q$ are symmetric with respect to the second coordinate $r_{2}$.
The first term in the right hand side of Eq. (7) is described by the convergence of $h_{jn}^{[-1,1]}(z)$, which corresponds to the one-dimensional ($(q-1)$-dimensional) Fejér kernel.
Since we have an additional term $1/2|\int_{\mathbb{T}^{2}}\int_{jnP_{2}}\mathrm{e}^{\mathrm{i}r\cdot(z-t)}g(t)
\mathrm{d}r\mathrm{d}t-g(z)|$, if $C(z)>1$, the convergence of $h^{P}_{jn}(z)$ is expected to be slower than its one-dimensional counterpart $h^{[-1,1]}_{jn}(z)$.
Based on this observation, we expect that the convergence in Theorem 8 becomes slower as $q$ becomes larger, and the interaction along $z\in\mathbb{T}$ becomes larger.

###### Lemma 25

###### Lemma 26

## Appendix C Representer theorem for RKHMs over general C ∗ superscript 𝐶 C^{*} italic_C start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT -algebras

Hashimoto et al. (Hashimoto et al., , Proposition 4.5) showed an approximate representer theorem for RKHMs over von Neumann-algebras.
Since $C(\mathbb{T})$ is not a von Neumann-algebra, we generalize the theorem to that for general $C^{*}$-algebras as follows.

###### Proposition 27

Let $x_{1},\ldots,x_{N}\in\mathcal{A}^{d}$.
Let $g:\mathcal{A}^{N}\to\mathcal{A}_{+}$ be a continuous map, let $h:\mathcal{A}_{+}\to\mathcal{A}_{+}$ satisfy $h(c)\leq_{\mathcal{A}}h(d)$ for $c,d\in\mathcal{A}_{+}$ with $c\leq_{\mathcal{A}}d$.
Let $L(f)=g(f(x_{1}),\ldots,f(x_{N}))+h(|f|_{k})$ for $f\in\mathcal{M}_{k}$.
If there exists a solution $f_{0}$ of the minimization problem $\min_{f\in\mathcal{M}_{k}}L(f)$, then for any $\epsilon>0$, there exists $\tilde{f}$ that admits the representation of $\tilde{f}=\sum_{i=1}^{N}\phi(x_{i})c_{i}$ and $\|L(\tilde{f})-L(f_{0})\|\leq\epsilon$.

Proof  For $f_{1},f_{2}\in\mathcal{M}_{k}$, let $\theta_{f_{1},f_{2}}:\mathcal{M}_{k}\to\mathcal{M}_{k}$ defined as $\theta_{f_{1},f_{2}}(v)=f_{1}\left\langle f_{2},v\right\rangle_{k}$ for $v\in\mathcal{M}_{k}$.
Let $\mathcal{N}_{k}$ be the submodule generated algebraically by $\{\phi(x_{1}),\ldots,\phi(x_{N})\}$, let $\mathcal{B}_{0}={\operatorname{Span}\{\theta_{f_{1},f_{2}}\,\mid\,f_{1},f_{2}
\in\mathcal{N}_{k}\}}$, and let $\mathcal{B}=\overline{\mathcal{B}_{0}}$.
In addition, let $\mathcal{L}(\mathcal{M}_{k})$ be the (unital) $C^{*}$-algebra of adjointable $\mathcal{A}$-linear operators on $\mathcal{M}_{k}$ (see (Lance, , p8)).
Since $\mathcal{B}$ is a $C^{*}$-subalgebra of $\mathcal{L}(\mathcal{M}_{k})$ (Note $\theta_{f_{1},f_{2}}\theta_{f_{3},f_{4}}=\theta_{f_{1},f_{4}\left\langle f_{3}
,f_{2}\right\rangle}$ and $\theta_{f_{1},f_{2}}^{*}=\theta_{f_{2},f_{1}}$), $\mathcal{B}_{0}$ has a net $\{b_{i}\}_{i}$ such that $0\leq_{\mathcal{L}(\mathcal{M}_{k})}b_{i}\leq_{\mathcal{L}(\mathcal{M}_{k})}1$ and $\lim_{i}\theta_{f_{1},f_{2}}b_{i}=\lim_{i}b_{i}\theta_{f_{1},f_{2}}=\theta_{f_
{1},f_{2}}$ for any $f_{1},f_{2}\in\mathcal{N}_{k}$ (Davidson, , Theorem I.4.8).
For each $v\in\mathcal{N}_{k}$, we have

$$ $\displaystyle\|v-b_{i}v\|_{k}^{2}$ $\displaystyle=\|\left\langle(1-b_{i})v,(1-b_{i})v\right\rangle_{k}\|_{\mathcal {A}}=\|\theta_{(1-b_{i})v,(1-b_{i})v}\|_{\mathcal{L}(\mathcal{M}_{k})}$ $\displaystyle=\|(1-b_{i})\theta_{v,v}(1-b_{i})^{*}\|_{\mathcal{L}(\mathcal{M}_ {k})}=\|(1-b_{i})\theta_{v,v}(1-b_{i})\|_{\mathcal{L}(\mathcal{M}_{k})}.$ $$

Thus, we have $\lim_{i}b_{i}v=v$.
Since $g$ is continuous, we have

$$ $\displaystyle\lim_{i}g(\left\langle\phi_{k}(x_{1}),b_{i}f_{0}\right\rangle_{k} ,\ldots,\left\langle\phi_{k}(x_{N}),b_{i}f_{0}\right\rangle_{k})=\lim_{i}g( \left\langle b_{i}^{*}\phi_{k}(x_{1}),f_{0}\right\rangle_{k},\ldots,\left \langle b_{i}^{*}\phi_{k}(x_{N}),f_{0}\right\rangle_{k})$ $\displaystyle=\lim_{i}g(\left\langle b_{i}\phi_{k}(x_{1}),f_{0}\right\rangle_{ k},\ldots,\left\langle b_{i}\phi_{k}(x_{N}),f_{0}\right\rangle_{k})=g(\left \langle\phi_{k}(x_{1}),f_{0}\right\rangle_{k},\ldots,\left\langle\phi_{k}(x_{N }),f_{0}\right\rangle_{k}).$ $$

Therefore, for $\epsilon>0$, there exists $i$ such that

$$ $\displaystyle\|g((b_{i}f_{0})(x_{1}),\ldots,(b_{i}f_{0})(x_{N}))-g(f_{0}(x_{1} ),\ldots,f_{0}(x_{N}))\|_{\mathcal{A}}\leq\epsilon.$ $$

Since $b_{i}\geq_{\mathcal{L}(\mathcal{M}_{k})}0$, there exists $c\geq_{\mathcal{L}(\mathcal{M}_{k})}0$ such that $b_{i}=c^{2}$.
Thus, $b_{i}-b_{i}^{2}=c^{2}-c^{4}=c(1-c^{2})c=c^{*}(1-b_{i})c\geq_{\mathcal{L}(
\mathcal{M}_{k})}0$.
Thus, $0\leq_{\mathcal{L}(\mathcal{M}_{k})}b_{i}^{2}\leq_{\mathcal{L}(\mathcal{M}_{k}
)}b_{i}\leq_{\mathcal{L}(\mathcal{M}_{k})}1$, and we have $|b_{i}f_{0}|_{k}^{2}=\left\langle f_{0},b_{i}^{2}f_{0}\right\rangle_{k}\leq_{
\mathcal{A}}\left\langle f_{0},f_{0}\right\rangle_{k}=|f_{0}|_{k}$.
As a result, we obtain

$$ $\displaystyle 0$ $\displaystyle\leq_{\mathcal{A}}L(b_{i}f_{0})-L(f_{0})$ $\displaystyle=g((b_{i}f_{0})(x_{1}),\ldots,(b_{i}f_{0})(x_{N}))+h(|b_{i}f_{0}| _{k})-g(f_{0}(x_{1}),\ldots,f_{0}(x_{N}))-h(|f_{0}|_{k})$ $\displaystyle\leq_{\mathcal{A}}g((b_{i}f_{0})(x_{1}),\ldots,(b_{i}f_{0})(x_{N} ))-g(f_{0}(x_{1}),\ldots,f_{0}(x_{N})).$ $$

Since $b_{i}f_{0}\in\mathcal{N}_{k}$, setting $\tilde{f}=b_{i}f_{0}$ completes the proof of the proposition.
$\Box$

###### Proposition 27

## Appendix D Generalization to Other C ∗ superscript 𝐶 C^{*} italic_C start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT -algebras

Setting $R_{n}$ and $S_{n}$ for more general $C^{*}$-algebras has been investigated.
Using these results and replacing $R_{n}$ and $S_{n}$ in Definition 6, we can define positive definite kernels for the $\mathcal{A}^{d}$-valued inputs and $\mathcal{A}$-valued output for a more general $C^{*}$-algebra $\mathcal{A}$.

#### Continuous functions on high-dimensional torus (Leimbach & van Suijlekom, 2024 )

For $\mathcal{A}=C(\mathbb{T}^{m})$, let $e_{j}(z)=\mathrm{e}^{\mathrm{i}j\cdot z}$ for $j\in\mathbb{Z}^{m}$ and $B_{n}=\{j\in\mathbb{Z}^{m}\,\mid\,\|j\|\leq n\}$, and consider the space $\operatorname{Span}\{e_{j}\,\mid\,j\in B_{n}\}$.
Here, $\|\cdot\|$ is the Euclidean norm.
We consider generalized matrices whose elements are indexed by $\mathbb{Z}^{m}$, and set
$R_{n}(x)=(\int_{\mathbb{T}^{m}}x(t)\mathrm{e}^{-\mathrm{i}(j-l)\cdot t}\mathrm
{d}t)_{j,l\in B_{n}}$ and $S_{n}(A)(z)=(1/|B_{n}|)\sum_{j,l\in B_{n}}A_{j,l}\mathrm{e}^{\mathrm{i}(j-l)z}$.

#### Continuous functions on the sphere (Rieffel, 2004 )

For $\mathcal{A}=C(S^{2})$, let $\rho_{n}$ be the $n$-dimensional irreducible group representation of $SU(2)$ (special unitary group of degree 2) and let $V_{n}$ be the representation space.
Let $P\in\mathcal{B}(V_{n})$ be a projection, where $\mathcal{B}(V_{n})$ is the space of bounded linear operators on $V_{n}$.
We set $R_{n}(x)=n\int_{SU(2)}x(g)\rho_{n}(g)^{*}P\rho_{n}(g)\mathrm{d}g$ and $S_{n}(A)(g)=\operatorname{tr}(A\rho_{n}(g)^{*}P\rho_{n}(g))$.

## Appendix E Experimental Details and Additional Results

We provide experimental details below.
All the experiments in this paper were executed with Python 3.9 on an Intel(R) Core(TM) i9-10885H
2.4GHz processor with the Windows 10 operating system.

Figure: Figure 3: Eigenvalues of the Gram matrix $\mathbf{G}(0)$ indexed as the descending order for the regression task. (Average value of results of five different runs. The error bar represents the standard deviation.)
Refer to caption: extracted/5897533/eig.png

### E.1 Experiment with synthetic data

We estimated $f$ using kernel ridge regression with the regularization parameter $\lambda=0.01$.
We generated 1000 input test samples in the same manner as the input training samples, and evaluated the test error $1/N\sum_{i=1}^{N}\|\hat{f}(\tilde{x}^{i})-\tilde{y}^{i}\|_{L^{2}(\mathbb{T})}$, where $\hat{f}$ is the estimation of $f$ and $\tilde{x}^{i}$ and $\tilde{y}^{i}$ are input and output test samples, respectively.
For $x^{i}$, $y^{i}$, $\tilde{x}^{i}$, and $a$, we discretized each function with 30 equally spaced points on $\mathbb{T}$.
In addition, to investigate the positive definiteness of $\hat{k}_{n}^{\operatorname{prod},q}$ discussed in Remark 15, we computed the eigenvalues of the Gram matrix $\mathbf{G}(0)$ at 0.
Figure 3 shows the result.
The index $i$ is determined in the descendent order with respect to the value of $\lambda_{i}$.
Thus, we can see that although we set $\beta_{n}$ as a small value, all the eigenvalues of $\mathbf{G}(0)$ are positive in this case.

We also show additional results regarding the deep approach in Figure 4.
The result is the average $\pm$ the standard deviation of three independent runs.
We set different values of $n$ with the same deep setting considered in Subsection 7.1.

Figure: Figure 4: Test error of the regression task with deep approach with different $n$ and $L$.
Refer to caption: extracted/5897533/deep_20.png

### E.2 Experiment with MNIST

We generated 200 input test samples in the same manner as the input training samples, and evaluated the test error $1/N\sum_{i=1}^{N}\|\hat{f}(\tilde{x}^{i})-\tilde{y}^{i}\|_{L^{2}(\mathbb{T})}$, where $\hat{f}$ is the estimated map that maps the image with the missing part to its original image, and $\tilde{x}^{i}$ and $\tilde{y}^{i}$ are input and output test samples, respectively.
Figure 5 (a) shows the test error.
We can see that the test error becomes the smallest when $n=70$, but it becomes large when $n$ is smaller or larger than $70$.
In addition, to investigate the positive definiteness of $\hat{k}_{n}^{\operatorname{prod},q}$, we computed the eigenvalues of the Gram matrix $\mathbf{G}(0)$ at 0.
Figure 5 (b) shows the result.
The index $i$ is determined in the descendent order with respect to the value of $\lambda_{i}$.
Thus, we can see that although we set $\beta_{n}$ as a small value, all the eigenvalues of $\mathbf{G}(0)$ are positive in this case.

Figure: Figure 5: (a) Test error of the image recovering task with different values of $n$ and the kernel $k=\hat{k}_{n}^{\operatorname{prod},q}$. (Box plot of results of five independent runs with different training and test data.) (b) Eigenvalues of the Gram matrix $\mathbf{G}(0)$ indexed as the descending order for the image recovering task. (Average value of results of five different runs. The error bar represents the standard deviation.)
Refer to caption: extracted/5897533/mnist.png

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 3
presentation: 3
questions: Overall I would be happy to increase the score of the paper (around 4) if answers are brought during the rebuttal.

- Please clarify the motivation and express the pros and cons with previous competing methods
- Give at least one example to make the reader understand the issue with commutativity and the benefit of non commutativity
- Identify as much as possible the family of problems that could in principle be tackled by this method
- Complete the toy experiments with a comparison with other function-valued regression methods 
for the existing experiments, are the same curves observed when dealing with a very large data regime ?

Nearly all my questions have been answered in a satisfying way.
soundness: 3
strengths: This paper is following an original path in the kernel theory, exploring new schemes of kernels with values in a C* algebra. The work is certainly promising and of great interest for the kernel community. based on solid mathematical work, it opens a new way to tackle vector-valued or function-valued regression.
- Of special interest on the case of input and outputs that can be considered as functional (or vectors that can be seen as values of functions like images), the spectral truncation kernel allows for a drastically reduced computation cost in Kernel Ridge Regression while offering a great expressivity. 
- It can be declined with various choices of ground kernels and its positive definiteness is studied
- Products of (function-valued)-functions based on those kernels provide a deep architecture.
summary: This paper explores the recent subfield of positive definite kernels with values in a C*-algebra and RKHM (the correponding "RKHS" theory) . The whole work is motivated by going beyond the separable kernel widely used in vector-valued RKHS based on operator-valued kernels and benefit from with a better compute time when applying kernel “ridge” regression. The main interest of working with a C*-algebra is that it comes with a norm, a product and an involution, unifying operators and functions. In particular, the paper focuses on the C*-algebra of continuous functions and the case where inputs as well are elements of this C* algebra.  The paper is illustrated with the example of continuous functions on the 1D torus.  The authors propose a novel function-valued kernel, spectral truncation kernel, relying on the approximation of the multiplication operator with respect to x (defined in L2(T)) by leveraging a truncated spectral decomposition. The dimension of the truncated basis encodes a trade-off between the representation power and the model complexity. The resulting kernel also benefits from the noncommutativity of the approximated product and can be shown to converge. Applied on Kernel Ridge Regression in RKHM, this new kernel leads to a reduction of the complexity in time. It also comes with a generalization bound which is a direct instantiation of the result proven by Hashimoto et al. (2023). A deep architecture based on product (and not composition) of different kernel-based functions in RKHM is also presented. Experimental results study the behaviour of the approach with respect to the truncation parameter on  a toy dataset. An additional result on an inpainted image recovery problem built on MNIST data is also briefly presented.
weaknesses: Even though very interesting the paper suffers from different flaws: some concern the presentation and can be considered as relatively minor, while the others are more fundamental.
Weaknesses in the content:
*The motivation of the paper remains unclear: if the authors wish to go beyond the separable kernel in the general case of vector-valued functions, they should briefly discuss the limitations (which indeed exist) of the different operator-valued kernels such as the transformable kernels, the separable kernels or combination of them.  If the motivation is to use RKHM theory in the case of function-valued functions then it is of paramount importance to highlight what cannot be done with operator-valued kernels devoted to functions with outputs in Hilbert spaces of functions. 
*Once a family of kernels is defined, in machine learning, we are interested on the ability of the machine learning algorithms to indeed take benefit from this kernel and provide a good solution to the ML task. So what is missing in this paper, is a discussion and an empirical study to determine when using those kernels are interesting compared to previous methods: does the complexity of the model make the algorithm more greedy in training data. I do not think that the actual generalization error bound really help to tell us that in precise terms.
My advice is thus to complete the paper with comparison with other (operator-valued) kernels and vv-RKHS. this has to be done  in the case of the current toy dataset but also in known functional regression data sets.
* Applicability and relevance of the methodology: a central question that is still not enough answered at the end of the paper is the following: on which family of problems, these spectral truncation kernels are relevant ?
For instance,  the use of function-valued kernels for inputs and outputs which are vectors should be discussed. I think it is important here to clarify this: images are by definition a discretisation of continuous maps (intensity of pixel in finite resomution) and then they can be seen as a set of values of a function taken on different observation points. There is a great interest at considering the functions as continuous functions.
 I do not think it is always meaningful for a vector to be encoded as a function of its coordinate index: can you comment on that ? 
* Finally I do think that the paper would have sufficient content if it was restricted to function-valued functions. However, if images are tken as examples, then more convincing and complete comparison on image completion should be givne with more involved problems than weakly inpainted images. For the results given, do not say vv-RKHS comparions in the table say clearly the name of the matrix-valued kernel you used and try other kernels including more general operator-valued kernels for function-valued functions.

Weaknesses in the presentation of the paper.
The paper is in general not self content,  too much straightforward in its statements and very not enough precise in the presentation. It seems to me that an important work of re-writing is necessary, even though it is quite obvious that some efforst ahve been made here.
To give a few suggestions:
- rewrite the introduction with clear motivations and do not enter into partial details that cannot be understood at this stage (n < infty, n infty..)

- line 154 we jump into a comment about C(T) but previsously functions on the real torus were just an example. Now X = A ?
please say it !Moreover we cannot understand the sentence "however, by approximating ... by a Toeplitz matrix..;", we do not know yet that Toeplitz matrix will be involved here 


- before line 174, say a word about the works of Van Suijlekom and explain the role of the Fejer function. The reader has to consult this apper to undertstand the construction. It is important in what follows when talking about convergence.

- in general, do not give proposition under the form of the sole formula but write a sentence introducing the property and a comment on what the proposition brings.
- generalization bound : clearly state as in the appendix that this result comes directly from previous literature (Maurer, 2016... Hasimoto et al. 2023)
-  It is crucial to introduce m when describing the observations at line 364.
- experiments : 
what do you want to bring in terms of emprirical evidence: please present the experiments as an answer to the questions/motivation of the beginning of the paper

* after rebuttal: the paper has gained significant improvements and I am  increasing my score consequently.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: See weaknesses
soundness: 3
strengths: The paper introduces an approach to kernel design by leveraging the mathematical framework of C*-algebras and RKHM, offering a potentially powerful way to model complex data relationships. The theoretical analysis of generalization bounds provides valuable insights into the trade-off between representation power and model complexity, guided by the kernel's truncation parameter.
summary: This paper proposes a new class of C*-algebra-valued positive definite kernels called spectral truncation kernels for vvRKHS. The noncommutativity, controlled by a truncation parameter n, allows for capturing interactions along the data function domain. The paper argues this enables a balance between representation power and model complexity, potentially leading to improved performance. A generalization bound is derived, highlighting the role of n in this tradeoff.
weaknesses: 1. While the authors claim a computational advantage over vector-valued RKHSs (vvRKHSs) due to the linear dependency on output dimension m compared to cubic dependency in vvRKHSs, this advantage is not clearly demonstrated. The computational cost analysis lacks a direct comparison with vvRKHSs employing appropriate approximation techniques. For instance, the use of Nyström methods or random Fourier features could significantly reduce the computational burden of vvRKHSs, potentially negating the claimed advantage of spectral truncation kernels.

2. The deep model extension, while promising, lacks theoretical grounding. The analysis of representation power growth is based on a very specific construction and doesn't provide general insights into the behavior of deep networks with spectral truncation kernels. 

3. The experimental results, while suggestive, are not compelling enough to validate the claimed advantages. The experiments are limited to synthetic data and a simplified MNIST task. More complex, real-world datasets with function-valued outputs are needed to assess the practical performance and demonstrate a clear advantage over existing methods.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: See Weakness.
soundness: 2
strengths: The authors have introduced the basic properties of the proposed kernels and also investigated the generalization error. The presentation is clear.
summary: This paper proposes a new class of positive definite kernels based on the spectral truncation. Detailed properties and examples have been discussed, and numerical results on both synthetic data and the MNIST dataset are presented.
weaknesses: Though the theoretical results are promising, two main questions remain unaddressed:
1. How can practical learning designs benefit from the new algebraic structures?
2. How can the development facilitate the kernel choices in practice? Section 6 seems to have some discussions on deep models, but a general development shall be data/task-dependent.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. In line 156, $z \in \mathbb{T}$ be the Fourier function. Why $z$ is a function? Based on the **Example 2.2**, $\mathbb{T}$ is a set, and the elements of $\mathbb{T}$ are real numbers. This puzzled me.
2. One of the main contributions of this paper is that the authors generalize typical kernels by introducing the noncommutativity of the products appearing in the kernels and showing their advantages. This is because $\mathcal{R}_n (x)$ and $\mathcal{R}_n (y)$, based on the spectral truncation, is noncommutative. However, the benefits of introducing noncommutativity in terms of convergence and generalization were not found. The effect of the noncommutativity is just illustrated in the experiment part. Or am I missing some details?
3. **Theory 3.4** gives the theoretical result of the convergence of proposed kernels. Does this mean that the proposed $k_n^{poly,q}(x, y)(z)$, $k_n^{prod,q}(x, y)(z)$, and $k_n^{seq,q}(x, y)(z)$  can approximate $k^{poly,q}(x, y)(z)$, $k^{prod,q}(x, y)(z)$, and $k^{seq,q}(x, y)(z)$, respectively? So is there any theoretical guidance for the selection of $n$, that is, how much $n$ can be well approximated?
4. From **Theory 4.1**, we can observe that the generalization bound is related to the trace of the kernel. How is this different from the previous theoretical results?
5. $n$ is the number of orthogonal bases. Therefore, the complexity of the model is larger if $n$ is larger, and the representation power of the model is better. This phenomenon also occurs in the general learning process or kernel function approach strategies. How is this different from them?
6. To obtain $c(z)$, computing $(G(z)+\lambda I)^{-1}y(z)$. Poor scalability.
7. Some definitions are in the complex number domain, while some are in the real number domain. It is confusing for me. When to do it in the complex number domain and when to do it in the real number domain. It can include a pseudo-code to show the details.
soundness: 3
strengths: 1. This paper is well written and organized.
2. Theoretical analysis is detailed, enabling the proposed method to have solid theoretical support.
3. The authors consider the deep spectral truncation kernel, sharing the advantage of both deep model and spectral truncation kernel, to improve the representation power.
summary: In this paper, authors propose a set of positive definite spectral truncation kernels, which is a class of the $C^*$-Algebra-valued kernel. The definitions of the proposed kernels involve several concepts, including $C^*$-Algebra, function-valued kernel, spectral truncation, and the torus. The authors provide a theoretical analysis of the convergence and generalization.  In addition, the authors introduce a noncommutativity and further illustrate its effectiveness with numerical results.
weaknesses: Please see the **Questions** section.

Meta-review: This paper utilizes the tool of C-algebra to develop new methods of kernel machines, receiving certain recognition from the reviewers. However, the current paper suffers from obvious weaknesses that prevent me from recommending acceptance. To me specific, the experimental setup, consisting of a synthetic dataset and a simple dataset called MINIST, is too weak to be convincing.

Decision: Reject