# Learning in RKHM: a $C^{*}$-Algebraic Twist for Kernel Machines

Yuka Hashimoto1,2 Masahiro Ikeda2,3 Hachem Kadri4
1\. NTT Network Service Systems Laboratories, NTT Corporation, Tokyo, Japan
2\. Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan
3\. Keio University, Yokohama, Japan
4\. Aix-Marseille University, CNRS, LIS, Marseille, France

###### Abstract

Supervised learning in reproducing kernel Hilbert space (RKHS) and vector-
valued RKHS (vvRKHS) has been investigated for more than 30 years. In this
paper, we provide a new twist to this rich literature by generalizing
supervised learning in RKHS and vvRKHS to reproducing kernel Hilbert
$C^{*}$-module (RKHM), and show how to construct effective positive-definite
kernels by considering the perspective of $C^{*}$-algebra. Unlike the cases of
RKHS and vvRKHS, we can use $C^{*}$-algebras to enlarge representation spaces.
This enables us to construct RKHMs whose representation power goes beyond
RKHSs, vvRKHSs, and existing methods such as convolutional neural networks.
Our framework is suitable, for example, for effectively analyzing image data
by allowing the interaction of Fourier components.

##  1 INTRODUCTION

Supervised learning in reproducing kernel Hilbert space (RKHS) has been
actively investigated  since the early 1990s (Murphy, 2012; Christmann &
Steinwart, 2008; Shawe-Taylor & Cristianini, 2004; Schölkopf & Smola, 2002;
Boser et al., 1992).  The notion of reproducing kernels as dot products in
Hilbert spaces was first brought to the field of machine learning by Aizerman
et al. (1964), while the theoretical foundation of reproducing kernels and
their Hilbert spaces dates back to at least Aronszajn (1950). By virtue of the
representer theorem (Schölkopf et al., 2001), we can compute the solution of
an infinite-dimensional minimization problem  in RKHS with given finite
samples. In addition to the standard RKHSs, applying vector-valued RKHSs
(vvRKHSs) to supervised learning has also been proposed and used in analyzing
vector-valued data (Micchelli & Pontil, 2005; Álvarez et al., 2012; Kadri et
al., 2016; Minh et al., 2016; Brouard et al., 2016; Laforgue et al., 2020;
Huusari & Kadri, 2021). Generalization bounds of the supervised problems in
RKHS and vvRKHS are also derived (Mohri et al., 2018; Caponnetto & De Vito,
2007; Audiffren & Kadri, 2013; Huusari & Kadri, 2021).

Reproducing kernel Hilbert $C^{*}$-module (RKHM) is a generalization of RKHS
and vvRKHS by means of $C^{*}$-algebra. $C^{*}$-algebra is a generalization of
the space of complex values. It has a product and an involution structures.
Important examples are the $C^{*}$-algebra of bounded linear operators on a
Hilbert space and the $C^{*}$-algebra of continuous functions on a compact
space. RKHMs have been originally studied for pure operator algebraic and
mathematical physics problems (Manuilov & Troitsky, 2000; Heo, 2008;
Moslehian, 2022). Recently, applying RKHMs to data analysis has been proposed
by Hashimoto et al. (2021). They generalized the representer theorem in RKHS
to RKHM, which allows us to analyze structured data such as functional data
with $C^{*}$-algebras.

In this paper, we investigate supervised learning in RKHM. This provides a new
twist to the state-of-the-art kernel-based learning algorithms and the
development of a novel kind of reproducing kernels. An advantage of RKHM over
RKHS and vvRKHS is that we can enlarge the $C^{*}$-algebra characterizing the
RKHM to construct a representation space. This allows us to represent more
functions than the case of RKHS and make use of the product structure in the
$C^{*}$-algebra. Our main contributions are:

  * •

We define positive definite kernels from the perspective of $C^{*}$-algebra,
which are suitable  for learning in RKHM and adapted to analyze image data.

  * •

We derive a generalization bound of the supervised  learning problem in RKHM,
which generalizes existing results of RKHS and vvRKHS. We also show that the
computational complexity of our method can be reduced if parameters in the
$C^{*}$-algebra-valued positive definite kernels have specific structures.

  * •

We show that our framework generalizes existing methods based on convolution
operations.

Important applications of the supervised learning in RKHM are tasks whose
inputs and outputs are images. If the proposed kernels have specific
parameters, then the product structure is the convolution, which corresponds
to the pointwise product of Fourier components. By extending the
$C^{*}$-algebra to a larger one, we can enjoy more general operations than the
convolutions. This enables us to analyze image data effectively by making
interactions between Fourier components. Regarding the generalization bound,
we derive the same type of bound as those  obtained for RKHS and vvRKHS  via
Rademacher complexity theory. This is  to our knowledge, the first
generalization bound for RKHM  hypothesis classes. Concerning the connection
with existing methods, we show that using our framework, we can reconstruct
existing methods such as the convolutional neural network (LeCun et al., 1998)
and the convolutional kernel (Mairal et al., 2014) and further generalize
them. This fact implies that the representation power of our framework goes
beyond the existing methods.

The remainder of this paper is organized as follows: In Section 2, we review
mathematical notions related to this paper. We propose $C^{*}$-algebra-valued
positive definite kernels in Section 3 and investigate supervised learning in
RKHM in Section 4. Then, we show connections  with  existing  convolution-
based methods in Section 5. We confirm the advantage of our method numerically
in Section 6 and conclude the paper in Section 7. All technical proofs are in
Section B.

##  2 PRELIMINARIES

###  2.1 $C^{*}$-Algebra and Hilbert $C^{*}$-Module

$C^{*}$-algebra is a Banach space equipped with a product and  an involution
that satisfies the $C^{*}$ identity. See Section A for more details. An
example of $C^{*}$-algebra is group $C^{*}$-algebra (Kirillov, 1976). Let
$p\in\mathbb{N}$, and let $\mathbb{Z}/p\mathbb{Z}$ be the set of integers
modulo $p$.

######  Definition 2.1 (Group $C^{*}$-algebra on a finite cyclic group)

Let $\omega=\mathrm{e}^{2\pi\sqrt{-1}/p}$. The group $C^{*}$-algebra on
$\mathbb{Z}/p\mathbb{Z}$, which is denoted as $C^{*}(\mathbb{Z}/p\mathbb{Z})$,
is the set of maps from $\mathbb{Z}/p\mathbb{Z}$ to $\mathbb{C}$ equipped with
the following product, involution, and norm:

  * •

$(x\cdot y)(z)=\sum_{w\in\mathbb{Z}/p\mathbb{Z}}x(z-w)y(w)$ for
$z\in\mathbb{Z}/p\mathbb{Z}$,

  * •

$x^{*}(z)=\overline{x(-z)}$,

  * •

$\|x\|=\max_{n\in\\{0,\ldots,p-1\\}}|\sum_{z\in\mathbb{Z}/p\mathbb{Z}}x(z)\omega^{zn}|$.

Since the product is the convolution, group $C^{*}$-algebras offer a new way
to define positive definite kernels, which are effective in analyzing image
data as we  will see in Section 3. Elements in $C^{*}(\mathbb{Z}/p\mathbb{Z})$
are described by circulant matrices (Gray, 2006). Let
$Circ(p)=\\{x\in\mathbb{C}^{p\times p}\,\mid\,x\mbox{ is a circulant
matrix}\\}$. Moreover, we denote the circulant matrix whose first row is $v$
as $\operatorname{circ}(v)$. The discrete Fourier transform (DFT) matrix,
whose $(i,j)$-entry is $\omega^{(i-1)(j-1)}/\sqrt{p}$, is denoted as $F$.

###### Lemma 2.2

Any circulant matrix $x\in Circ(p)$ has an eigenvalue decomposition
$x=F\Lambda_{x}F^{*}$, where

$\Lambda_{x}=\operatorname{diag}\bigg{(}\sum_{z\in\mathbb{Z}/p\mathbb{Z}}x(z)\omega^{z\cdot
0},\ldots,\sum_{z\in\mathbb{Z}/p\mathbb{Z}}x(z)\omega^{z(p-1)}\bigg{)}.$

###### Lemma 2.3

The group $C^{*}$-algebra $C^{*}(\mathbb{Z}/p\mathbb{Z})$ is
$C^{*}$-isomorphic to $Circ(p)$.

We  now review important notions about $C^{*}$-algebra. We denote a
$C^{*}$-algebra by $\mathcal{A}$.

######  Definition 2.4 (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, and $a\lneq_{\mathcal{A}}b$
if $b-a$ is positive and not zero. We denote by $\mathcal{A}_{+}$ the subset
of $\mathcal{A}$ composed of all positive elements in $\mathcal{A}$.

######  Definition 2.5 (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}$.

Hilbert $C^{*}$-module is a generalization of Hilbert space. We can define an
$\mathcal{A}$-valued inner product and a (real nonnegative-valued) norm as a
natural generalization of the complex-valued inner product. See Section A for
further details. Then, we define Hilbert $C^{*}$-module as follows.

######  Definition 2.6 (Hilbert $C^{*}$-module)

Let $\mathcal{M}$ be a $C^{*}$-module over $\mathcal{A}$ equipped with an
$\mathcal{A}$-valued inner product. If $\mathcal{M}$ is complete with respect
to the norm induced by the $\mathcal{A}$-valued inner product, it is called a
Hilbert $C^{*}$-module over $\mathcal{A}$ or Hilbert $\mathcal{A}$-module.

###  2.2 Reproducing Kernel Hilbert $C^{*}$-Module

RKHM is a generalization of RKHS by means of $C^{*}$-algebra. Let
$\mathcal{X}$ be a non-empty set for data.

######  Definition 2.7 ($\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:

  * •

$k(x,y)=k(y,x)^{*}$ for $x,y\in\mathcal{X}$,

  * •

$\sum_{i,j=1}^{n}c_{i}^{*}k(x_{i},x_{j})c_{j}\geq_{\mathcal{A}}0$ 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$, which is defined as $\phi(x)=k(\cdot,x)$ for
$x\in\mathcal{X}$. We construct the following $C^{*}$-module composed of
$\mathcal{A}$-valued functions:

$\mathcal{M}_{k,0}:=\bigg{\\{}\sum_{i=1}^{n}\phi(x_{i})c_{i}\bigg{|}\
n\in\mathbb{N},\ c_{i}\in\mathcal{A},\ x_{i}\in\mathcal{X}\bigg{\\}}.$

Define an $\mathcal{A}$-valued map
$\left\langle\cdot,\cdot\right\rangle_{\mathcal{M}_{k}}:\mathcal{M}_{k,0}\times\mathcal{M}_{k,0}\to\mathcal{A}$
as

$\big{\langle}\sum_{i=1}^{n}\phi(x_{i})c_{i},\sum_{j=1}^{l}\phi(y_{j})b_{j}\big{\rangle}_{\mathcal{M}_{k}}:=\sum_{i=1}^{n}\sum_{j=1}^{l}c_{i}^{*}k(x_{i},y_{j})b_{j}.$

By the properties of $k$ in Definition 2.7,
$\left\langle\cdot,\cdot\right\rangle_{\mathcal{M}_{k}}$ is well-defined and
has the reproducing property

$\left\langle\phi(x),v\right\rangle_{\mathcal{M}_{k}}=v(x),$

for $v\in\mathcal{M}_{k,0}$ and $x\in\mathcal{X}$. Also, it is an
$\mathcal{A}$-valued inner product. The reproducing kernel Hilbert
$\mathcal{A}$-module (RKHM) associated with $k$ is defined as the completion
of $\mathcal{M}_{k,0}$. We denote by $\mathcal{M}_{k}$ the RKHM associated
with $k$. In the following, we denote the inner product, absolute value, and
norm in $\mathcal{M}_{k}$ by $\left\langle\cdot,\cdot\right\rangle_{k}$,
$|\cdot|_{k}$, and $\|\cdot\|_{k}$ , respectively. Hashimoto et al. (2021)
showed the representer theorem in RKHM.

######  Proposition 2.8 (Representer theorem)

Let $\mathcal{A}$ be a unital $C^{*}$-algebra. Let
$x_{1},\ldots,x_{n}\in\mathcal{X}$ and $y_{1},\ldots,y_{n}\in\mathcal{A}$. Let
$h:\mathcal{X}\times\mathcal{A}\times\mathcal{A}\to\mathcal{A}_{+}$ be an
error function and let $g:\mathcal{A}_{+}\to\mathcal{A}_{+}$ satisfy
$g(a)\lneq_{\mathcal{A}}g(b)$ for $a\lneq_{\mathcal{A}}b$. Assume the module
(algebraically) generated by $\\{\phi(x_{i})\\}_{i=1}^{n}$ is closed. Then,
any $u\in\mathcal{M}_{k}$ minimizing
$\sum_{i=1}^{n}h(x_{i},y_{i},u(x_{i}))+g(|u|_{\mathcal{M}_{k}})$ admits a
representation of the form $\sum_{i=1}^{n}\phi(x_{i})c_{i}$ for some
$c_{1},\ldots,c_{n}\in\mathcal{A}$.

##  3 $C^{*}$-ALGEBRA-VALUED POSITIVE DEFINITE KERNELS

To investigate the supervised learning problem in RKHM, we begin by
constructing suitable $C^{*}$-algebra-valued positive definite kernels. The
product structure used in these kernels will be shown to be effective in
analyzing image data. However, the proposed kernels are general, and their
application is not limited to image data.

Let $\mathcal{A}_{1}$ be a $C^{*}$-algebra. By the Gelfand–Naimark theorem
(see, for example, Murphy 1990), there exists a Hilbert space $\mathcal{H}$
such that $\mathcal{A}_{1}$ is a subalgebra of the $C^{*}$-algebra
$\mathcal{A}_{2}$ of bounded linear operators on $\mathcal{H}$. For image data
we can set $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ as follows.

###### Example 3.1

Let $p\in\mathbb{N}$, $\mathcal{A}_{1}=C^{*}(\mathbb{Z}/p\mathbb{Z})$, and
$\mathcal{A}_{2}=\mathbb{C}^{p\times p}$. Then, $\mathcal{A}_{1}$ is a
subalgebra of $\mathcal{A}_{2}$. Indeed, by Lemma 2.3, $\mathcal{A}_{1}\simeq
Circ(p)$. For example, in image processing, we represent filters by circulant
matrices (Chanda & Majumder, 2011). If we regard $\mathbb{Z}/p\mathbb{Z}$ as
the space of $p$ pixels, then elements in $C^{*}(\mathbb{Z}/p\mathbb{Z})$ can
be regarded as functions from pixels to intensities. Thus, we can also regard
grayscale and color images with $p$ pixels as elements in
$C^{*}(\mathbb{Z}/p\mathbb{Z})$ and $C^{*}(\mathbb{Z}/p\mathbb{Z})^{3}$,
respectively. Note that $\mathcal{A}_{2}$ is noncommutative, although
$\mathcal{A}_{1}$ is commutative.

We consider the case where the inputs are in $\mathcal{A}_{1}^{d}$ for
$d\in\mathbb{N}$ and define linear, polynomial, and Gaussian $C^{*}$-algebra-
valued positive definite kernels as follows. For example, we can consider the
case where inputs are $d$ images.

###### Definition 3.2

Let $\mathcal{X}\subseteq\mathcal{A}_{1}^{d}$ and
$x=[x_{1},\ldots,x_{d}]\in\mathcal{X}$.

  1. 1.

For $a_{i,1},a_{i,2}\in\mathcal{A}_{2}$, the linear kernel
$k:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{2}$ is defined as
$k(x,y)=\sum_{i=1}^{d}a_{i,1}^{*}x_{i}^{*}a_{i,2}^{*}a_{i,2}y_{i}a_{i,1}$.

  2. 2.

For $q\in\mathbb{N}$ and $a_{i,j}\in\mathcal{A}_{2}\ (i=1,\ldots d,j=1,\ldots
q+1)$, the polynomial kernel
$k:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{2}$ is defined as

$k(x,y)=\sum_{i=1}^{d}\bigg{(}\prod_{j=1}^{q}a_{i,j}^{*}x_{i}^{*}\bigg{)}a_{i,q+1}^{*}a_{i,q+1}\bigg{(}\prod_{j=1}^{q}y_{i}a_{i,q+1-j}\bigg{)}.$
disabledisabletodo: disableequation above exceeds the margin

  3. 3.

Let $\Omega$ be a measurable space and $\mu$ is an $\mathcal{A}_{2}$-valued
positive measure on $\Omega$.111 See Hashimoto et al. (2021, Appendix B) for a
rigorous definition. For $a_{i,1},a_{i,2}:\Omega\to\mathcal{A}_{2}$, the
Gaussian kernel $k:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{2}$ is defined
as

$\displaystyle k(x,y)=$
$\displaystyle\int_{\omega\in\Omega}\mathrm{e}^{-\sqrt{-1}\sum_{i=1}^{d}a_{i,1}(\omega)^{*}x_{i}^{*}a_{i,2}(\omega)^{*}}\mathrm{d}\mu(\omega)\mathrm{e}^{\sqrt{-1}\sum_{i=1}^{d}a_{i,2}(\omega)y_{i}a_{i,1}(\omega)}.$

Here, we assume the integral does not diverge.

###### Remark 3.3

We can construct new kernels by the composition of functions to the kernels
defined in Definition 3.2. For example, let
$\psi_{i,j}:\mathcal{A}_{1}\to\mathcal{A}_{2}$ for $i=1,\ldots d$ and
$j=1,\ldots,q+1$. Then, the map defined by replacing $x_{i}$ and $y_{i}$ in
the polynomial kernel by $\psi_{i,j}(x_{i})$ and $\psi_{i,j}(y_{i})$ is also
an $C^{*}$-algebra-valued positive definite kernel.

Figure 1: Representing samples in RKHM

If $\mathcal{A}_{1}=\mathcal{A}_{2}=\mathbb{C}$, then the above kernels are
reduced to the standard complex-valued positive definite kernels and the RKHMs
associated with them are reduced to RKHSs. In this case, if
$\mathcal{X}=\mathcal{A}^{d}$, the input space and the RKHS are both Hilbert
spaces (Hilbert $\mathbb{C}$-modules). On the other hand, for RKHMs, if we
choose $\mathcal{A}_{1}\subsetneq\mathcal{A}_{2}$, then the input space
$\mathcal{X}$ is a Hilbert $\mathcal{A}_{1}$-module, but the RKHM is a Hilbert
$\mathcal{A}_{2}$-module, not $\mathcal{A}_{1}$-module. Applying RKHMs, we can
construct higher dimensional spaces than input spaces but also enlarge the
$C^{*}$-algebras characterizing the RKHMs, which allows us to represent more
functions than RKHSs and make use of the product structure in
$\mathcal{A}_{2}$. Figure 1 schematically shows the representation of samples
in RKHM. We show an example related to image data below.

###### Example 3.4

If $\mathcal{A}_{1}=C^{*}(\mathbb{Z}/p\mathbb{Z})$,
$\mathcal{A}_{2}=\mathbb{C}^{p\times p}$
($\mathcal{A}_{1}\subsetneq\mathcal{A}_{2}$), and $a_{i,j}\in\mathcal{A}_{1}$,
then $a_{i,j}$ in Definition 3.2 behaves as convolutional filters. In fact, by
Definition 2.1, the multiplication of $a_{i,j}$ and $x_{i}$ is represented by
the convolution. The convolution of two functions corresponds to the
multiplication of each Fourier component of them. Thus, each Fourier component
of $x_{i}$ does not interact with other Fourier components. Choosing
$a_{i,j}\in\mathcal{A}_{2}$ outside $\mathcal{A}_{1}$ corresponds to the
multiplication of different Fourier components of two functions. Indeed, let
$x\in\mathcal{A}_{1}$. Then, by Lemma 2.3, $x$ is represented as a circulant
matrix and by Lemma 2.2, it is decomposed as $x=F\Lambda_{x}F^{*}$. In this
case, $\Lambda_{x}$ is the diagonal matrix whose $i$th diagonal is the $i$th
Fourier component (FC) of $x$. Thus, if $a_{i,j}\in\mathcal{A}_{1}$, then we
have $xa_{i,j}=F\Lambda_{x}\Lambda_{a_{i,j}}F^{*}$ and each Fourier component
of $x$ is multiplied by the same Fourier component of $a_{i,j}$. On the other
hand, if $a_{i,j}\in\mathcal{A}_{2}\setminus\mathcal{A}_{1}$, then
$\Lambda_{a_{i,j}}$ is not a diagonal matrix, and the elements of
$\Lambda_{x}\Lambda_{a_{i,j}}$ are composed of the weighted sum of different
Fourier components of $x$. Figure 3 summarizes this example.

#### Comparison with vvRKHS

From the perspective of vvRKHS, defining kernels as in Definition 3.2 is
difficult since for vvRKHS, the output space is a Hilbert space, and we do not
have product structures in it. Indeed, the inner product in a vvRKHS is
described by an action of an operator on a vector. We can regard the vector as
a rank-one operator whose range is the one-dimensional space spanned by the
vector. Thus, the action is regarded as the product of only two operators. On
the other hand, from the perspective of $C^{*}$-algebra, we can multiply more
than two elements in $C^{*}$-algebra, which allows us to define
$C^{*}$-algebra-valued kernels naturally in the same manner as complex-valued
kernels. See Figure 3 for a schematic explanation.

Figure 2: Product in $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ in Example 3.4

Figure 3: Comparison of RKHM with vvRKHS

##  4 SUPERVISED LEARNING IN RKHM

We investigate supervised learning in RKHM. We first formulate the problem and
derive a learning algorithm. Then, we characterize its generalization error
and investigate its computational complexity.

We do not assume $\mathcal{X}\subseteq\mathcal{A}_{1}^{d}$ in Subsections 4.1
and 4.2. The input space $\mathcal{X}$ can be an arbitrary nonempty set in
these sections. Thus, although we focus on the case of
$\mathcal{X}\subseteq\mathcal{A}_{1}^{d}$ in this paper, the supervised
learning in RKHM is applied to general problems whose output space is a
$C^{*}$-algebra $\mathcal{A}$.

###  4.1 Problem Setting

Let $x_{1},\ldots,x_{n}\in\mathcal{X}$ be input training samples and
$y_{1},\ldots,y_{n}\in\mathcal{A}$ be output training samples. Let
$k:\mathcal{X}\times\mathcal{X}\to\mathcal{A}$ be an $\mathcal{A}$-valued
positive definite kernel, and let $\phi$ and $\mathcal{M}_{k}$ be the feature
map and RKHM associated with $k$, respectively. We find a function
$f:\mathcal{X}\to\mathcal{A}$ in $\mathcal{M}_{k}$ that maps input data to
output data. For this purpose, we consider the following minimization problem:

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

where $\lambda\geq 0$ is the regularization parameter. By the representer
theorem (Proposition 2.8), we find a solution $f$ in the submodule generated
by $\\{\phi(x_{1}),\ldots,\phi(x_{n})\\}$. As the case of RKHS (Schölkopf et
al., 2001), representing $f$ as $\sum_{j=1}^{n}\phi(x_{j})c_{j}\
(c_{j}\in\mathcal{A})$, 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}),$
(2)

where $\mathbf{G}$ is the
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathcal{A}^{n\times
n}}$-valued Gram matrix whose $(i,j)$-entry is defined as
$k(x_{i},x_{j}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\in\mathcal{A}}$,
$\mathbf{c}=[c_{1},\ldots,c_{n}]^{T}$, $\mathbf{y}=[y_{1},\ldots,y_{n}]^{T}$,
and $|a|_{\mathcal{A}}=(a^{*}a)^{1/2}$ for $a\in\mathcal{A}$. If
$\mathbf{G}+\lambda I$ is invertible, the solution of Problem (2) is
$\mathbf{c}=(\mathbf{G}+\lambda I)^{-1}\mathbf{y}$.

###  4.2 Generalization Bound

We derive a generalization bound of the supervised problem in RKHM. We first
define an $\mathcal{A}$-valued Rademacher complexity. Let $(\Omega,P)$ be a
probability space. For a random variable (measurable map)
$g:\Omega\to\mathcal{A}$, we denote by $\mathrm{E}[g]$ the Bochner integral of
$g$, i.e., $\int_{\omega\in\Omega}g(\omega)\mathrm{d}P(\omega)$.

###### Definition 4.1

Let $\sigma_{1},\ldots,\sigma_{n}$ be i.i.d and mean zero $\mathcal{A}$-valued
random variables and let $x_{1},\ldots,x_{n}\in\mathcal{X}$ be given samples.
Let $\boldsymbol{\sigma}=\\{\sigma_{i}\\}_{i=1}^{n}$ and
$\mathbf{x}=\\{x_{i}\\}_{i=1}^{n}$. Let $\mathcal{F}$ be a class of functions
from $\mathcal{X}$ to $\mathcal{A}$. The $\mathcal{A}$-valued empirical
Rademacher complexity $\hat{R}(\mathcal{F},\boldsymbol{\sigma},\mathbf{x})$ is
defined as

$\hat{R}(\mathcal{F},\boldsymbol{\sigma},\mathbf{x})=\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})^{*}\sigma_{i}\bigg{|}_{\mathcal{A}}\bigg{]}.$

We derive an upper bound of the complexity of a function space related to the
RKHM $\mathcal{M}_{k}$. We assume $\mathcal{A}$ is the $C^{*}$-algebra of
bounded linear operators on a Hilbert space.

###### Proposition 4.2

Let $B>0$ and let $\mathcal{F}=\\{f\in\mathcal{M}_{k}\,\mid\,\|f\|_{k}\leq
B\\}$ and let
$C=\int_{\Omega}\|\sigma_{i}(\omega)\|_{\mathcal{A}}^{2}\mathrm{d}P(\omega)$.
Then, we have

$\hat{R}(\mathcal{F},\boldsymbol{\sigma},\mathbf{x})\leq_{{\mathcal{A}}}\frac{B\sqrt{C}}{n}\bigg{(}\sum_{i=1}^{n}\|k(x_{i},x_{i})\|_{\mathcal{A}}\bigg{)}^{1/2}I.$

To prove Proposition 4.2, we first show the following $\mathcal{A}$-valued
version of Jensen’s inequality.

###### Lemma 4.3

For a positive $\mathcal{A}$-valued random variable
$c:\Omega\to\mathcal{A}_{+}$, we have
$\mathrm{E}[c^{1/2}]\leq_{\mathcal{A}}\mathrm{E}[c]^{1/2}$.

In Example 3.4, we focused on the case of $\mathcal{A}=\mathbb{C}^{p\times
p}$, which is effective, for example, in analyzing image data. In the
following, we focus on that case and consider the trace of matrices. The trace
is an appropriate operation for evaluating matrices. It is linear and forms
the Hilbert–Schmidt inner product. Let $B>0$ and $E>0$. We put
$\mathcal{F}=\\{f\in\mathcal{M}_{k}\,\mid\,\|f\|_{k}\leq B,\
f(x)\in\mathbb{R}^{p\times p}\mbox{ for any }x\in\mathcal{X}\\}$,
${\mathcal{G}(\mathcal{F})}=\\{\mathcal{X}\times\mathcal{Y}\ni(x,y)\mapsto|f(x)-y|_{\mathcal{A}}^{2}\in\mathcal{A}\,\mid\,f\in\mathcal{F}\\}$,
and $\mathcal{Y}=\\{y\in\mathbb{R}^{p\times p}\,\mid\,\|y\|_{\mathcal{A}}\leq
E\\}$. Let $x_{1},\ldots,x_{n}\in\mathcal{X}$ and
$y_{1},\ldots,y_{n}\in\mathcal{Y}$. We assume there exists $D>0$ such that for
any $x\in\mathcal{X}$, $\|k(x,x)\|_{\mathcal{A}}\leq D$ and let
$L=2\sqrt{2}(B\sqrt{D}+E)$. Using the upper bound of the Rademacher
complexity, we derive the following generalization bound.

###### Proposition 4.4

Let $\operatorname{tr}(a)$ be the trace of $a\in\mathbb{C}^{p\times p}$. For
any $g\in\mathcal{G}(\mathcal{F})$, any random variable
$z:\Omega\to\mathcal{X}\times\mathcal{Y}$, and any $\delta\in(0,1)$, with
probability $\geq 1-\delta$, we obtain

$\displaystyle\operatorname{tr}\bigg{(}\mathrm{E}[g(z)]-\frac{1}{n}\sum_{i=1}^{n}g(x_{i},y_{i})\bigg{)}\leq
2\frac{LB\sqrt{D}p}{\sqrt{n}}+3\sqrt{2D}p\sqrt{\frac{\log(2/{\delta})}{n}}.$

Note that the same type of bounds is derived for RKHS (Mohri et al., 2018,
Theorem 3.3) and for vvRKHS (Huusari & Kadri, 2021, Corollary 16, Sindhwani et
al., 2013, Theorem 3.1, Sangnier et al., 2016, Theorem 4.1). Proposition 4.4
generalizes them to RKHM.

To show Proposition 4.4, we first evaluate the Rademacher complexity with
respect to the squared loss function $(x,y)\mapsto|f(x)-y|_{\mathcal{A}}^{2}$.
We use Theorem 3 of Maurer (2016) to obtain the following bound.

###### Lemma 4.5

Let $s_{1},\ldots,s_{n}$ be $\\{-1,1\\}$-valued Rademacher variables (i.e.
independent uniform random variables taking values in $\\{-1,1\\}$) and let
$\sigma_{1},\ldots,\sigma_{n}$ be i.i.d. $\mathcal{A}$-valued random variables
each of whose element is the Rademacher variable. Let
$\mathbf{s}=\\{s_{i}\\}_{i=1}^{n}$, and
$\mathbf{z}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$. Then, we have

$\displaystyle\operatorname{tr}\hat{R}(\mathcal{G}(\mathcal{F}),\mathbf{s},\mathbf{z})\leq{L}\operatorname{tr}\hat{R}(\mathcal{F},\boldsymbol{\sigma},\mathbf{x}).$

Next, we use Theorem 3.3 of Mohri et al. (2018) to derive an upper bound of
the generalization error.

###### Lemma 4.6

Let $z:\Omega\to\mathcal{X}\times\mathcal{Y}$ be a random variable and let
$g\in\mathcal{G}(\mathcal{F})$. Under the same notations and assumptions as
Proposition 4.5, for any $\delta\in(0,1)$, with probability $\geq 1-\delta$,
we have

$\displaystyle\operatorname{tr}\bigg{(}\mathrm{E}[g(z)]-\frac{1}{n}\sum_{i=1}^{n}g(x_{i},y_{i})\bigg{)}\leq
2\operatorname{tr}\hat{R}(\mathcal{G}(\mathcal{F}),\mathbf{s},\mathbf{z})+3\sqrt{2D}p\sqrt{\frac{\log({2}/{\delta})}{n}}.$

###  4.3 Computational Complexity

As mentioned at the beginning of this section, we need to compute
$(\mathbf{G}+\lambda I)^{-1}\mathbf{y}$ for a Gram matrix
$\mathbf{G}\in\mathcal{A}^{n\times n}$ and a vector $y\in\mathcal{A}^{n}$ for
solving the minimization problem (2). When $\mathcal{A}=\mathbb{C}^{p\times
p}$, we have $\mathcal{A}^{n\times n}=\mathbb{C}^{np\times np}$, and
$\mathbf{G}$ is huge if $n$, the number of samples, or $p$, the dimension of
$\mathcal{A}$, is large. If we construct the $np$ by $np$ matrix explicitly
and compute $(\mathbf{G}+\lambda I)^{-1}\mathbf{y}$ with a direct method such
as Gaussian elimination and back substitution (for example, see Trefethen &
Bau 1997), the computational complexity is $O(n^{3}p^{3})$. However, if
$\mathcal{X}=\mathcal{A}_{1}^{d}$, $\mathcal{A}_{1}\subsetneq\mathcal{A}_{2}$,
and parameters in the positive definite kernel have a specific structure, then
we can reduce the computational complexity. For example, applying the fast
Fourier transform, we can compute a multiplication of the DFT matrix $F$ and a
vector with $O(p\log p)$ (Van Loan, 1992). disabledisabletodo: disablenot
clear, maybe just remove ’and the following propositions are derived’ Let
$\mathcal{A}_{1}=C^{*}(\mathbb{Z}/p\mathbb{Z})$ and let
$\mathcal{A}_{2}=\mathbb{C}^{p\times p}$. Let $k$ be an $\mathcal{A}_{1}$ or
$\mathcal{A}_{2}$-valued positive definite kernel defined in Definition 3.2.

###### Proposition 4.7

For $a_{i,j}\in\mathcal{A}_{1}$, the computational complexity for computing
$(\mathbf{G}+\lambda I)^{-1}\mathbf{y}$ by direct methods for solving linear
systems of equations is $O(np^{2}\log p+n^{3}p)$.

We can use an iteration method for linear systems, such as the conjugate
gradient (CG) method (Hestenes & Stiefel, 1952) to reduce the complexity with
respect to $n$. Note that we need $O(np^{2}\log p)$ operations after all the
iterations.

###### Proposition 4.8

For $a_{i,j}\in\mathcal{A}_{1}$, the computational complexity for $1$
iteration step of CG method is $O(n^{2}p)$.

###### Proposition 4.9

Let $a_{i,j}\in\mathcal{A}_{2}$ whose number of nonzero elements is $O(p\log
p)$. Then, the computational complexity for $1$ iteration step of CG method is
$O(n^{2}p^{2}\log p)$.

###### Remark 4.10

If we do not use the structure of $\mathcal{A}_{1}$, then the computational
complexities in Propositions 4.7, 4.8, and 4.9 are $O(n^{3}p^{3})$,
$O(n^{2}p^{3})$, and $O(n^{2}p^{3})$, respectively.

In the case of RKHSs, techniques such as the random Fourier feature have been
proposed to alleviate the computational cost of kernel methods (Rahimi &
Recht, 2007). It could be interesting to inspect how to further reduce the
computational complexity of learning in RKHM using random feature
approximations for $C^{*}$-algebra-valued kernels; this is left for future
work.

##  5 CONNECTION WITH EXISTING METHODS

###  5.1 Connection with Convolutional Neural Network

Convolutional neural network (CNN) has been one of the most successful methods
for analyzing image data (LeCun et al., 1998; Li et al., 2021). We investigate
the connection of the supervised learning problem in RKHM with CNN. In this
subsection, we set
$\mathcal{X}\subseteq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathcal{A}_{1}}=C^{*}(\mathbb{Z}/p\mathbb{Z})$
and $\mathcal{A}_{2}=\mathbb{C}^{p\times p}$. Since the product in
$C^{*}(\mathbb{Z}/p\mathbb{Z})$ is characterized by the convolution, our
framework with a specific $\mathcal{A}_{1}$-valued positive definite kernel
enables us to reconstruct a similar model as the CNN.

We first provide an $\mathcal{A}_{1}$-valued positive definite kernel related
to the CNN.

###### Proposition 5.1

For $a_{1},\ldots,a_{L},b_{1},\ldots,b_{L}\in\mathcal{A}_{1}$ and
$\sigma_{1},\ldots,\sigma_{L}:\mathcal{A}_{1}\to\mathcal{A}_{1}$ each of which
has an expansion $\sigma_{j}(x)=\sum_{l=1}^{\infty}\alpha_{j,l}x^{l}$ with
$\alpha_{j,l}\geq 0$, let
$\hat{k}:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{1}$ be defined as

$\displaystyle\hat{k}(x,y)=$
$\displaystyle\sigma_{L}(b_{L}^{*}b_{L}+\sigma_{L-1}(b_{L-1}^{*}b_{L-1}+\cdots+\sigma_{2}(b_{2}^{*}b_{2}+\sigma_{1}(b_{1}^{*}b_{1}+x^{*}a_{1}^{*}a_{1}y)a_{2}^{*}a_{2})\cdots
a_{L-1}^{*}a_{L-1})a_{L}^{*}a_{L}).$ (3)

Then, $\hat{k}$ is an $\mathcal{A}_{1}$-valued positive definite kernel.

Using the positive definite kernel (3), the solution $f$ of the problem (2) is
written as

$\displaystyle f(x)=$
$\displaystyle\sum_{i=1}^{n}\sigma_{L}(b_{L}^{*}b_{L}+\sigma_{L-1}(b_{L-1}^{*}b_{L-1}+\cdots+\sigma_{2}(b_{2}^{*}b_{2}+\sigma_{1}(b_{1}^{*}b_{1}+x^{*}a_{1}^{*}a_{1}x_{i})a_{2}^{*}a_{2})\cdots
a_{L-1}^{*}a_{L-1})a_{L}^{*}a_{L})c_{i},$ (4)

for some $c_{i}\in\mathcal{A}_{1}$. We regard $a_{1}^{*}a_{1}x_{i}$ and
$a_{j}^{*}a_{j}$ for $j=2,\ldots,L$ as convolutional filters, $b_{j}^{*}b_{j}$
for $j=1,\ldots,L$ as biases, and $\sigma_{j}$ for $j=1,\ldots,L$ as
activation functions. Then, optimizing $a_{1},\ldots,a_{L},b_{1},\ldots,b_{L}$
simultaneously with $c_{i}$ corresponds to learning the CNN of the form (4).

The following proposition shows that the $C^{*}$-algebra-valued polynomial
kernel defined in Definition 3.2 is general enough to represent the
$\mathcal{A}_{1}$-valued positive definite kernel $\hat{k}$, related to the
CNN. Therefore, by applying $\mathcal{A}_{2}$-valued polynomial kernel, not
$\mathcal{A}_{1}$-valued polynomial kernel, we can go beyond the method with
the convolution.

###### Proposition 5.2

The $\mathcal{A}_{1}$-valued positive definite kernel $\hat{k}$ defined as Eq.
(3) is composed of the sum of $\mathcal{A}_{1}$-valued polynomial kernels.

###  5.2 Connection with Convolutional Kernel

For image data, a ($\mathbb{C}$-valued) positive definite kernel called
convolutional kernel is proposed to bridge a gap between kernel methods and
neural networks (Mairal et al., 2014; Mairal, 2016). In this subsection, we
construct two $C^{*}$-algebra-valued positive definite kernels that generalize
the convolutional kernel. Similar to the case of the CNN, we will first show
that we can reconstruct the convolutional kernel using a $C^{*}$-algebra-
valued positive definite kernel. Moreover, we will show that our framework
gives another generalization of the convolutional kernel. A generalization of
neural networks to $C^{*}$-algebra-valued networks is proposed (Hashimoto et
al., 2022). This generalization allows us to generalize the analysis of the
CNNs with kernel methods to that of $C^{*}$-algebra-valued CNNs.

Let $\Omega$ be a finite subset of $\mathbb{Z}^{m}$. For example, $\Omega$ is
the space of $m$-dimensional grids. Let
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\tilde{\mathcal{A}}_{1}}$
be the space of $\mathbb{C}$-valued maps on $\Omega$ and
$\mathcal{X}\subseteq\tilde{\mathcal{A}}_{1}$. The convolutional kernel is
defined as follows (Mairal et al., 2014, Definition 2).

###### Definition 5.3

Let $\beta,\sigma>0$. The convolutional kernel
$\tilde{k}:{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathcal{X}\times\mathcal{X}}\to\mathbb{C}$
is defined as

$\displaystyle\tilde{k}(x,y)=$
$\displaystyle\sum_{z,z^{\prime}\in\Omega}|x(z)|\,|y(z^{\prime})|\mathrm{e}^{-\frac{1}{2\beta^{2}}\|z-z^{\prime}\|^{2}}\mathrm{e}^{-\frac{1}{2\sigma^{2}}|\tilde{x}(z)-\tilde{y}(z^{\prime})|^{2}}.$
(5)

Here, $\|\cdot\|$ is the standard norm in $\mathbb{C}^{m}$. In addition, for
$x\in\mathcal{X}$, $\tilde{x}(z)=x(z)/|x(z)|$.

Let $\Omega=\\{z_{1},\ldots,z_{p}\\}$,
$\mathcal{A}_{1}=C^{*}(\mathbb{Z}/p\mathbb{Z})$, and
$\mathcal{A}_{2}=\mathbb{C}^{p\times p}$. We first construct an
$\mathcal{A}_{1}$-valued positive definite kernel, which reconstructs the
convolutional kernel (5).

###### Proposition 5.4

Define $\hat{k}:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{1}$ as

$\displaystyle\hat{k}(x,y)=\int_{\mathbb{R}}\int_{\mathbb{R}^{m}}c_{x}(\omega,\eta)^{*}c_{y}(\omega,\eta)\;\mathrm{d}\lambda_{\beta}(\omega)\mathrm{d}{\lambda}_{\sigma}(\eta),$
(6)

where
$\mathrm{d}\lambda_{\beta}(\omega)=\beta\mathrm{e}^{-\frac{\beta^{2}\omega^{2}}{2}}\mathrm{d}\omega$
for $\beta>0$ and

$\displaystyle c_{x}(\omega,\eta)=$
$\displaystyle\operatorname{circ}\Big{(}|x(z_{1})|\mathrm{e}^{\sqrt{-1}\omega\cdot
z_{1}}\mathrm{e}^{\sqrt{-1}\eta\cdot\tilde{x}(z_{1})},\cdots,|x(z_{p})|\mathrm{e}^{\sqrt{-1}\omega\cdot
z_{p}}\mathrm{e}^{\sqrt{-1}\eta\cdot\tilde{x}(z_{p})}\Big{)},$

for $x\in\mathcal{X}$, $\omega\in\mathbb{R}^{m}$, and $\eta\in\mathbb{R}$.
Then, $\hat{k}$ is an $\mathcal{A}_{1}$-valued positive definite kernel, and
for any $l=1,\ldots,p$, $\tilde{k}$ is written as

$\displaystyle\tilde{k}(x,y)=\frac{1}{p}\sum_{i,j=1}^{p}\hat{k}(x,y)_{i,j}=\sum_{j=1}^{p}\hat{k}(x,y)_{l,j},$

where $\hat{k}(x,y)_{i,j}$ is the $(i,j)$-entry of $\hat{k}(x,y)$.

###### Remark 5.5

Similar to Subsection 5.1, we can generalize $\hat{k}$ by replacing
$c_{x}(\cdot,\cdot)^{*}c_{y}(\cdot,\cdot)$ by an $\mathcal{A}_{2}$-valued
polynomial kernel with respect to $c_{x}(\cdot,\cdot)$ and
$c_{y}(\cdot,\cdot)$ in Eq. (6).

Instead of $\mathcal{A}_{1}$-valued, we can also construct an
$\tilde{\mathcal{A}}_{1}$-valued kernel, which reconstructs the convolutional
kernel (5).

###### Definition 5.6

Let $\beta,\sigma>0$. Define
$\check{k}:\mathcal{X}\times\mathcal{X}\to\tilde{\mathcal{A}}_{1}$ as

$\displaystyle\check{k}(x,y)(w)=\sum_{z,z^{\prime}\in\Omega}|x(\psi(z,w))|\,|y(\psi(z^{\prime},w))|\mathrm{e}^{\frac{-1}{2\beta^{2}}\|\psi(z,w)-\psi(z^{\prime},w)\|^{2}}\mathrm{e}^{\frac{-1}{2\sigma^{2}}|\tilde{x}(\psi(z,w))-\tilde{y}(\psi(z^{\prime},w))|^{2}}$
(7)

for $w\in\Omega$. Here, $\psi:\Omega\times\Omega\to\Omega$ is a map satisfying
$\psi(z,0)=z$ for any $z\in\Omega$.

The $\tilde{\mathcal{A}}_{1}$-valued map $\check{k}$ is a generalization of
the ($\mathbb{C}$-valued) convolutional kernel $\tilde{k}$ in the following
sense, which is directly derived from the definitions of $\check{k}$ and
$\tilde{k}$.

###### Proposition 5.7

For $\tilde{k}$ and $\check{k}$ defined as Eqs. (5) and (7), respectively, we
have $\check{k}(x,y)(0)=\tilde{k}(x,y)$.

We further generalize the $\tilde{\mathcal{A}}_{1}$-valued kernel $\check{k}$
to an $\mathcal{A}_{2}$-valued positive definite kernel.

###### Definition 5.8

Let $\beta,\sigma>0$ and $a_{i}\in\mathcal{A}_{2}$ for $i=1,2,3,4$. Let $\psi$
be the same map as that in Eq. (7). Let
$k:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{2}$ be defined as

$\displaystyle
k(x,y)=\int_{\mathbb{R}}\int_{\mathbb{R}^{m}}\sum_{z,z^{\prime}\in\Omega}a_{1}^{*}\mathbf{x}(z)a_{2}^{*}b(z,\omega)^{*}a_{3}^{*}\tilde{\mathbf{x}}(z,\eta)^{*}a_{4}^{*}a_{4}\tilde{\mathbf{y}}(z^{\prime},\eta)a_{3}b(z^{\prime},\omega)a_{2}\mathbf{y}(z^{\prime})a_{1}\;\mathrm{d}\lambda_{\beta}(\omega)\mathrm{d}\lambda_{\sigma}(\eta)$
(8)

for $x,y\in\mathcal{X}$. Here, for $x\in\mathcal{X}$,

$\displaystyle\mathbf{x}(z)=\operatorname{diag}(|x(\psi(z,z_{1})|,\ldots,|x(\psi(z,z_{p}))|)\in\mathcal{A}_{2},$
$\displaystyle\tilde{\mathbf{x}}(z,\omega)=\operatorname{diag}(\mathrm{e}^{-\sqrt{-1}\omega\cdot\tilde{x}(\psi(z,z_{1}))},\ldots,\mathrm{e}^{-\sqrt{-1}\omega\cdot\tilde{x}(\psi(z,z_{p}))})\in\mathcal{A}_{2},$
$\displaystyle
b(z,\omega)=\operatorname{diag}(\mathrm{e}^{-\sqrt{-1}\omega\cdot\psi(z,z_{1})},\ldots,\mathrm{e}^{-\sqrt{-1}\omega\cdot\psi(z,z_{p})})\in\mathcal{A}_{2}.$

###### Proposition 5.9

The $\mathcal{A}_{2}$-valued map $k$ defined as Eq. (8) is an
$\mathcal{A}_{2}$-valued positive definite kernel.

The following proposition shows $k$ is a generalization of $\check{k}$, which
means we finally generalize the ($\mathbb{C}$-valued) convolution kernel
$\tilde{k}$ to an $\mathcal{A}_{2}$-valued positive definite kernel. This
allows us to generalize the relationship between the CNNs and the
convolutional kernel to that of a $C^{*}$-algebra-valued version of the CNNs
and the $C^{*}$-algebra-valued convolutional kernel $k$.

###### Proposition 5.10

If $a_{i}=I$, then the $\mathcal{A}_{2}$-valued positive definite kernel $k$
defined as Eq. (8) is reduced to the $\mathcal{A}_{1}$-valued convolutional
kernel $\check{k}$ defined as Eq. (7).

|  | Mean error
---|---|---
vvRKHS, Gaussian ($\tilde{k}(x,y)=\mathrm{e}^{-c\|x-y\|^{2}}$) | $k=\tilde{k}I$ | $0.640\pm 0.122$
$k=\tilde{k}T$ | $0.603\pm 0.028$
Nonsep | $0.650\pm 0.051$
vvRKHS, Laplacian ($\tilde{k}(x,y)=\mathrm{e}^{-c\|x-y\|}$) | $k=\tilde{k}I$ | $0.538\pm 0.027$
$k=\tilde{k}T$ | $0.590\pm 0.021$
Nonsep | $0.650\pm 0.048$
vvRKHS, Polynomial ($\tilde{k}(x,y)=\sum_{i=1}^{3}(1-cx\cdot y)^{i}$) | $k=\tilde{k}I$ | $0.800\pm 0.032$
$k=\tilde{k}T$ | $0.539\pm 0.012$
Nonsep | $0.539\pm 0.012$
RKHM ($k(x,y)=\sum_{i=1}^{3}R_{x}^{*}(I-cQ_{x}^{*})^{i}(I-cQ_{y})^{i}R_{y}$) | $\mathbf{0.343\pm 0.022}$

$T=\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$, Nonsep:
$k(x_{1},x_{2})_{i,j}=\tilde{k}(x_{1,i},x_{2,j})$

Table 1: Comparison between an RKHM and vvRKHSs (Mean value $\pm$ standard
deviation of $5$ runs)

(a) Regularization parameter $\lambda$

(b) Number of samples $n$

Figure 4: Mean test error versus hyperparameters (Mean value $\pm$ standard
deviation of $5$ runs).

Original |
---|---
Input |
3-layer CNN |
RKHM $+$ 1-layer CNN |
Figure 5: Comparison between RKHM and CNN

(a) 2-layer models

(b) 3-layer models

Figure 6: Mean test error versus the number of epochs (Mean value $\pm$
standard deviation of $5$ runs).

##  6 NUMERICAL RESULTS

###  6.1 Experiments with Synthetic Data

We compared the performances of supervised learning in RKHMs and vvRKHSs. We
generated $n$ samples $x_{1},\ldots,x_{n}$ in $[0,1]^{2}$ each of whose
elements is independently drawn from the uniform distribution on $[0,1]$. For
a generated sample $x_{i}=[x_{i,1},x_{i,2}]$, we added noise
$\xi_{i}\in\mathbb{R}^{2}$, each of whose elements is independently drawn from
the Gaussian distribution with mean $0$ and standard deviation $0.1$. We
generated the corresponding output sample $y_{i}$ as
$y_{i}=[\sin(\tilde{x}_{i,1}+\tilde{x}_{i,2}),\sin(\tilde{x}_{i,1}+\tilde{x}_{i,2})+\sin(0.5(\tilde{x}_{i,1}+\tilde{x}_{i,2}))]\in\mathbb{R}^{2}$,
where $\tilde{x}_{i}=x_{i}+\xi_{i}$. We learned a function $f$ that maps
$x_{i}$ to $y_{i}$ in different RKHMs and vvRKHSs and different values of the
regularization parameter $\lambda$. To compare the performances, we generated
$100$ test input samples $\hat{x}_{1},\ldots,\hat{x}_{100}$ in $[0,1]^{2}$
each of whose elements is independently drawn from the uniform distribution on
$[0,1]$. We also generated $\hat{y}_{1},\ldots,\hat{y}_{100}$ given by
$\hat{y}_{i}=[\sin(\hat{x}_{i,1}+\hat{x}_{i,2}),\sin(\hat{x}_{i,1}+\hat{x}_{i,2})+\sin(0.5(\hat{x}_{i,1}+\hat{x}_{i,2}))]$.
We computed the mean error
$1/100\sum_{i=1}^{100}\|f(\hat{x}_{i})-\hat{y}_{i}\|$. The results for $n=30$
are illustrated in Table 1 and Figure 5. Regarding Table 1, we executed a
cross-validation grid search to find the best parameters $c$ and $\lambda$,
where $c$ is a parameter in the positive definite kernels and $\lambda$ is the
regularization parameter. Regarding Figure 5 (a), we set $c$ as the parameter
found by the cross-validation and computed the error for different values of
$\lambda$. We remark that the mean error for the RKHM becomes large as
$\lambda$ becomes large, but because of the scale of the vertical axis, we
cannot see the change clearly in the figure. We can see that RKHM outperforms
vvRKHSs. We also show the relationship between the mean error and the number
of samples in Figure 5 (b). We can see that the mean error becomes small as
the number of samples becomes large.

Regarding the learning in RKHMs, for $i=1,\ldots,n$, we transformed
$x_{i}\in[0,1]^{2}$ into $\operatorname{circ}(x_{i})\in Circ(2)$. Then, we set
$\mathcal{A}_{1}=Circ(2)$ and $\mathcal{A}_{2}=\mathbb{C}^{2\times 2}$. We
computed the solution of the minimization problem (2) and obtained a function
$\hat{f}\in\mathcal{M}_{k}$ that maps $\operatorname{circ}(x_{i})$ to
$\operatorname{circ}(y_{i})$. Since the output of the learned function
$\hat{f}$ takes its value on $\mathcal{A}_{2}$, we computed the mean value of
$(1,1)$ and $(2,2)$ entries of $\hat{f}(\hat{x}_{i})$ for obtaining the first
element of the output vector in $\mathbb{R}^{2}$ and that of $(1,2)$ and
$(2,1)$ entries for the second element. Regarding the $C^{*}$-algebra-valued
kernel for RKHM, we set
$k(x,y)=\sum_{i=1}^{3}R_{x}^{*}(I-cQ_{x}^{*})^{i}(I-cQ_{y})^{i}R_{y}$ for
$x\in\mathcal{A}_{1}$, where $x=Q_{x}R_{x}$ is the QR decomposition of $x$.

###  6.2 Experiments with MNIST

We compared our method with CNNs using MNIST (LeCun et al., 1998). For
$i=1,\ldots,20$, we generated training samples as follows: We added noise to
each pixel of an original image $y_{i}$ and generated a noisy image $x_{i}$.
The noise is drawn from the normal distribution with mean 0 and standard
deviation 0.01. Moreover, each digit (0–9) is contained in the training sample
set equally (i.e., the number of samples for each digit is 2). The image size
is $28\times 28$. We tried to find a function that maps a noisy image to its
original image using an RKHM and a CNN. We represent input and output images
$x_{i}$ and $y_{i}$ as the circulant matrices $\operatorname{circ}(x_{i})$ and
$\operatorname{circ}(y_{i})$ whose first rows are $x_{i}$ and $y_{i}$. Then,
we learned the function in the RKHM associated with a polynomial kernel
$k(x,y)=(a_{3}^{*}\sigma(xa_{1}+a_{2})^{*}+a_{4}^{*})(\sigma(ya_{1}+a_{2})a_{3}+a_{4})$,
where $\sigma(x)=(I-cQ_{x})R_{x}+(I-cQ_{x})^{3}R_{x}$. Since $k$ has 4
$\mathcal{A}_{2}$-valued parameters, disabledisabletodo: disable 4 parameters
in A1? if we say only 4 parameters, one can think that we have 4 scalars
parameters it corresponds to a generalization of 2-layer CNN with $28\times
28$ filters (see Subsection 5.1). Regarding the parameters $a_{i}$, we used a
gradient descent method and optimized them. We generated 100 noisy images for
test samples in the same manner as the training samples and computed the mean
error with respect to them. For comparison, we also trained a 2-layer CNN with
$28\times 28$ filters with the same training samples. The results are
illustrated in Figure 6 (a). We can see that the RKHM outperforms the CNN.
Moreover, we combined the RKHM with a 1-layer CNN with a $3\times 3$ filter,
whose inputs are the outputs of the function learned in the RKHM. We also
trained a 3-layer CNN with $3\times 3$ filters and a 2-layer CNN with
$28\times 28$ filters combined with a 1-layer CNN with a $3\times 3$ filter.
The results are illustrated in Figures 5 and 6 (b). We can see that by
replacing convolutional layers with an RKHM, we can achieve better
performance. RKHMs and convolutional layers with $28\times 28$ filters capture
global information of images. According to the results of the CNN with
$28\times 28$ filters and the RKHM in Figure 6 (b), we can see that the RKHM
can capture global information of the images more effectively. On the other
hand, convolutional layers with $3\times 3$ filters capture local information.
Since the 2-layer RKHM combined with a 1-layer CNN with a $3\times 3$ filter
outperforms a 3-layer CNN with $3\times 3$ filters, we conclude that the
combination of the RKHM and CNN captures the global and local information more
effectively. disabledisabletodo: disablereformulate the last sentence ’we
conclude …’. not clear

##  7 CONCLUSION

We investigated supervised learning in RKHM and provided a new twist and
insights for kernel methods. We constructed $C^{*}$-algebra-valued kernels
from the perspective of $C^{*}$-algebra, which is suitable, for example, for
analyzing image data. We investigated the generalization bound and
computational complexity for RKHM learning and showed the connection with
existing methods. RKHMs enable us to construct larger representation spaces
than the case of RKHSs and vvRKHSs, and generalize operations such as
convolution. This fact implies the representation power of RKHMs goes beyond
that of existing frameworks.

### Acknowledgements

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

## Notation

The typical notations in this paper are listed in Table A.

##  Appendix A $C^{*}$-algebra and Hilbert $C^{*}$-module

We provide definitions and a lemma related to $C^{*}$-algebra and Hilbert
$C^{*}$-module.

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

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

  1. 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. 2.

$\mathcal{A}$ is a normed space endowed with $\|\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. 3.

For $a\in\mathcal{A}$, $\|a^{*}a\|_{\mathcal{A}}=\|a\|_{\mathcal{A}}^{2}$
holds.

A $C^{*}$-algebra $\mathcal{A}$ is called unital if there exists
$a\in\mathcal{A}$ such that $ab=b=ba$ for any $b\in\mathcal{A}$. We denote $a$
by $1_{\mathcal{A}}$.

######  Definition A.2 ($C^{*}$-module)

Let $\mathcal{M}$ be an abelian group with an operation $+$. If $\mathcal{M}$
is equipped with a (right) $\mathcal{A}$-multiplication, then $\mathcal{M}$ is
called a (right) $C^{*}$-module over $\mathcal{A}$.

######  Definition A.3 ($\mathcal{A}$-valued inner product)

Let $\mathcal{M}$ be a $C^{*}$-module over $\mathcal{A}$. A
$\mathbb{C}$-linear map with respect to the second variable
$\left\langle\cdot,\cdot\right\rangle_{\mathcal{M}}:\mathcal{M}\times\mathcal{M}\to\mathcal{A}$
is called an $\mathcal{A}$-valued inner product if it satisfies the following
properties for $u,v,{w}\in\mathcal{M}$ and $a,b\in\mathcal{A}$:

  1. 1.

$\left\langle u,va+{w}b\right\rangle_{\mathcal{M}}=\left\langle
u,v\right\rangle_{\mathcal{M}}a+\left\langle
u,{w}\right\rangle_{\mathcal{M}}b$,

  2. 2.

$\left\langle v,u\right\rangle_{\mathcal{M}}=\left\langle
u,v\right\rangle_{\mathcal{M}}^{*}$,

  3. 3.

$\left\langle u,u\right\rangle_{\mathcal{M}}\geq_{\mathcal{A}}0$,

  4. 4.

If $\left\langle u,u\right\rangle_{\mathcal{M}}=0$, then $u=0$.

######  Definition A.4 ($\mathcal{A}$-valued absolute value and norm)

Let $\mathcal{M}$ be a $C^{*}$-module over $\mathcal{A}$. For
$u\in\mathcal{M}$, the $\mathcal{A}$-valued absolute value $|u|_{\mathcal{M}}$
on $\mathcal{M}$ is defined by the positive element $|u|_{\mathcal{M}}$ of
$\mathcal{A}$ such that $|u|_{\mathcal{M}}^{2}=\left\langle
u,u\right\rangle_{\mathcal{M}}$. The nonnegative real-valued norm
$\|\cdot\|_{\mathcal{M}}$ on $\mathcal{M}$ is defined by
$\|u\|_{\mathcal{M}}=\big{\|}|u|_{\mathcal{M}}\big{\|}_{\mathcal{A}}$.

Similar to the case of Hilbert spaces, the following Cauchy–Schwarz inequality
for $\mathcal{A}$-valued inner products is available (Lance, 1995, Proposition
1.1).

######  Lemma A.5 (Cauchy–Schwarz inequality)

Let $\mathcal{M}$ be a Hilbert $\mathcal{A}$-module. For $u,v\in\mathcal{M}$,
the following inequality holds:

$|\left\langle
u,v\right\rangle_{\mathcal{M}}|_{\mathcal{A}}^{2}\;\leq_{\mathcal{A}}\|u\|_{\mathcal{M}}^{2}\left\langle
v,v\right\rangle_{\mathcal{M}}.$

Table A: Notation table $\mathcal{A}$ |  A $C^{*}$-algebra
---|---
$\mathcal{A}_{+}$ |  The subset of $\mathcal{A}$ composed of all positive elements in $\mathcal{A}$
$\leq_{\mathcal{A}}$ |  For $a,b\in\mathcal{A}$, $a\leq_{\mathcal{A}}b$ means $b-a$ is positive
$\lneq_{\mathcal{A}}$ |  For $a,b\in\mathcal{A}$, $a\lneq_{\mathcal{A}}b$ means $b-a$ is positive and nonzero
$|\cdot|_{\mathcal{A}}$ |  The $\mathcal{A}$-valued absolute value in $\mathcal{A}$ defined as $|a|_{\mathcal{A}}=(a^{*}a)^{1/2}$ for $a\in\mathcal{A}$.
$\mathcal{X}$ |  An input space
$\mathcal{Y}$ |  An output space
$k$ |  An $\mathcal{A}$-valued positive definite kernel
$\phi$ |  The feature map endowed with $k$
$\mathcal{M}_{k}$ |  The RKHM associated with $k$
$\mathbf{G}$ |  The $\mathcal{A}$-valued Gram matrix defined as $\mathbf{G}_{i,j}=k(x_{i},x_{j})$ for given samples $x_{1},\ldots,x_{n}\in\mathcal{X}$
$F$ |  The discrete Fourier transform (DFT) matrix, whose $(i,j)$-entry is $\omega^{(i-1)(j-1)}/\sqrt{p}$

##  Appendix B Proofs

We provide the proofs of the propositions and lemmas in the main thesis.

Lemma 2.3 The group $C^{*}$-algebra $C^{*}(\mathbb{Z}/p\mathbb{Z})$ is
$C^{*}$-isomorphic to $Circ(p)$.

Proof  Let $f:C^{*}(\mathbb{Z}/p\mathbb{Z})\to Circ(p)$ be a map defined as
$f(x)=\operatorname{circ}(x(0),\ldots,x(p-1))$. Then, $f$ is linear and
invertible. In addition, we have

$\displaystyle f(x)f(y)$
$\displaystyle=\operatorname{circ}\bigg{(}\sum_{z\in\mathbb{Z}/p\mathbb{Z}}x(0-z)y(z),\ldots,\sum_{z\in\mathbb{Z}/p\mathbb{Z}}x(p-1-z)y(z)\bigg{)}$
$\displaystyle=\operatorname{circ}((x\cdot y)(0),\ldots,(x\cdot
y)(p-1))=f(x\cdot y),$ $\displaystyle f(x)^{*}$
$\displaystyle=\operatorname{circ}(\overline{x(0)},\overline{x(p-1)},\ldots,\overline{x(1)})=f(x^{*}),$
$\displaystyle\|f(x)\|$
$\displaystyle=\bigg{\|}F\operatorname{diag}\bigg{(}\sum_{z\in\mathbb{Z}/p\mathbb{Z}}x(z)\mathrm{e}^{2\pi\sqrt{-1}z\cdot
0/p},\ldots,\sum_{z\in\mathbb{Z}/p\mathbb{Z}}x(z)\mathrm{e}^{2\pi\sqrt{-1}z(p-1)/p}\bigg{)}F^{*}\bigg{\|}=\|x\|,$

where the last formula is derived by Lemma 2.2. Thus, $f$ is a
$C^{*}$-isomorphism. $\Box$

In the following, for a probability space $\Omega$ and a random variable
(measurable map) $g:\Omega\to\mathbb{C}$, the integral of $g$ is denoted by
$\mathrm{E}[g]$.

Lemma 4.3 For a positive $\mathcal{A}$-valued random variable
$c:\Omega\to\mathcal{A}_{+}$, we have
$\mathrm{E}[c^{1/2}]\leq_{\mathcal{A}}\mathrm{E}[c]^{1/2}$.

Proof  For any $\epsilon>0$, let $x_{0}=\mathrm{E}[c+\epsilon
1_{\mathcal{A}}]$, $a=1/2x_{0}^{-1/2}$, and $b=1/2x_{0}^{1/2}$. Then, we have
$ax_{0}+b=x_{0}^{1/2}$ and for any $x\in\mathcal{A}_{+}$, we have

$\displaystyle(ax+b)^{*}(ax+b)-x$
$\displaystyle=\frac{1}{4}xx_{0}^{-1}x+\frac{1}{4}x+\frac{1}{4}x+\frac{1}{4}x_{0}-x$
$\displaystyle=\bigg{(}\frac{1}{2}x_{0}^{-1/2}x-\frac{1}{2}x_{0}^{1/2}\bigg{)}^{*}\bigg{(}\frac{1}{2}x_{0}^{-1/2}x-\frac{1}{2}x_{0}^{1/2}\bigg{)}=(ax-b)^{*}(ax-b)\geq_{\mathcal{A}}0.$

Thus, we have
$ax+b=|ax+b|_{\mathcal{A}}\geq_{\mathcal{A}}|x^{1/2}|_{\mathcal{A}}=x^{1/2}$.
Therefore, we have

$\displaystyle\mathrm{E}\big{[}(c+\epsilon
1_{\mathcal{A}})^{1/2}\big{]}\leq_{\mathcal{A}}\mathrm{E}[a(c+\epsilon
1_{\mathcal{A}})+b]=ax_{0}+b=x_{0}^{1/2}=\mathrm{E}[(c+\epsilon
1_{\mathcal{A}})]^{1/2}.$

Since $\epsilon>0$ is arbitrary, we have
$\mathrm{E}[c^{1/2}]\leq_{\mathcal{A}}\mathrm{E}[c]^{1/2}$. $\Box$

Proposition 4.2 Let $B>0$ and let
$\mathcal{F}=\\{f\in\mathcal{M}_{k}\,\mid\,\|f\|_{k}\leq B\\}$ and let
$C=\int_{\Omega}\|\sigma_{i}(\omega)\|_{\mathcal{A}}^{2}\mathrm{d}P(\omega)$.
Then, we have

$\hat{R}(\mathcal{F},\boldsymbol{\sigma},\mathbf{x})\leq_{{\mathcal{A}}}\frac{B\sqrt{C}}{n}\bigg{(}\sum_{i=1}^{n}\|k(x_{i},x_{i})\|_{\mathcal{A}}\bigg{)}^{1/2}I.$

Proof  By Lemma 4.3, we have

$\displaystyle\hat{R}(\mathcal{F},\boldsymbol{\sigma},\mathbf{x})=\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})^{*}\sigma_{i}\bigg{|}_{\mathcal{A}}\bigg{]}=\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\bigg{\langle}f,\sum_{i=1}^{n}\phi(x_{i})\sigma_{i}\bigg{\rangle}_{k}\bigg{|}_{\mathcal{A}}\bigg{]}$
$\displaystyle\quad\leq\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\sum_{i=1}^{n}\phi(x_{i})\sigma_{i}\bigg{|}_{k}\|f\|_{k}\bigg{]}=\frac{1}{n}\mathrm{E}\bigg{[}\bigg{|}\sum_{i=1}^{n}\phi(x_{i})\sigma_{i}\bigg{|}_{k}B\bigg{]}=\frac{B}{n}\mathrm{E}\bigg{[}\bigg{(}\sum_{i,j=1}^{n}\sigma_{i}^{*}k(x_{i},x_{j})\sigma_{j}\bigg{)}^{1/2}\bigg{]}$
$\displaystyle\quad\leq\frac{B}{n}\mathrm{E}\bigg{[}\sum_{i,j=1}^{n}\sigma_{i}^{*}k(x_{i},x_{j})\sigma_{j}\bigg{]}^{1/2}=\frac{B}{n}\bigg{(}\sum_{i=1}^{n}\mathrm{E}[\sigma_{i}^{*}k(x_{i},x_{i})\sigma_{i}]\bigg{)}^{1/2}\leq\frac{B}{n}\bigg{(}\sum_{i=1}^{n}\mathrm{E}[\|\sigma_{i}^{*}k(x_{i},x_{i})\sigma_{i}\|_{\mathcal{A}}]\bigg{)}^{1/2}I$
$\displaystyle\quad\leq\frac{B}{n}\mathrm{E}\big{[}\|\sigma_{i}\|_{\mathcal{A}}^{2}\big{]}^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1/2}}\bigg{(}\sum_{i=1}^{n}\|k(x_{i},x_{i})\|_{\mathcal{A}}\bigg{)}^{1/2}I=\frac{B\sqrt{C}}{n}\bigg{(}\sum_{i=1}^{n}\|k(x_{i},x_{i})\|_{\mathcal{A}}\bigg{)}^{1/2}I,$

where the third inequality is derived by the Cauchy–Schwartz inequality (Lemma
A.5). $\Box$

In the following, we put $\mathcal{A}=\mathbb{C}^{p\times p}$. The following
lemmas are applied for the proofs of Lemmas 4.5 and 4.6.

###### Lemma B.1

Let $a,b\in\mathbb{R}^{p\times p}$ or $a,b\in\mathcal{A}_{+}$. If
$a\leq_{\mathcal{A}}b$, then $\operatorname{tr}(a)\leq\operatorname{tr}(b)$.

Proof  Since $b-a\in\mathcal{A}_{+}$, we have
$0\leq\operatorname{tr}(b-a)=\operatorname{tr}(b)-\operatorname{tr}(a)$.
$\Box$

###### Lemma B.2

Let $\mathcal{S}$ be a subset of $\mathcal{A}_{+}$. Then,
$\operatorname{tr}(\sup_{s\in\mathcal{S}}s)=\sup_{s\in\mathcal{S}}\operatorname{tr}(s)$.

Proof
($\operatorname{tr}(\sup_{s\in\mathcal{S}}s)\leq\sup_{s\in\mathcal{S}}\operatorname{tr}(s)$)
Let $a=\sup_{s\in\mathcal{S}}s$. Let $\epsilon>0$, and assume for any
$t\in\mathcal{S}$, we have $(1-\epsilon)a\geq_{\mathcal{A}}t$. Then,
$(1-\epsilon)a$ is an upper bound of $\mathcal{S}$ that satisfies
$(1-\epsilon)a\lneq_{\mathcal{A}}a$, which contradicts the fact that $a$ is
the supremum of $\mathcal{S}$. Thus, there exists $t\in\mathcal{S}$ such that
$(1-\epsilon)a\lneq_{\mathcal{A}}t$. Therefore, we have

$\displaystyle(1-\epsilon)\operatorname{tr}(a)\leq\operatorname{tr}(t)\leq\sup_{s\in\mathcal{S}}\operatorname{tr}(s).$

Since $\epsilon>0$ is arbitrary, we have
$\operatorname{tr}(a)\leq\sup_{s\in\mathcal{S}}\operatorname{tr}(s)$.

($\operatorname{tr}(\sup_{s\in\mathcal{S}}s)\geq\sup_{s\in\mathcal{S}}\operatorname{tr}(s)$)
Let $\epsilon>0$. Then, there exists $t\in\mathcal{S}$ such that

$\displaystyle(1-\epsilon)\sup_{s\in\mathcal{S}}\operatorname{tr}(s)\leq\operatorname{tr}(t)\leq\operatorname{tr}(\sup_{s\in\mathcal{S}}s).$

Since $\epsilon>0$ is arbitrary, we have
$\operatorname{tr}(\sup_{s\in\mathcal{S}}s)\geq\sup_{s\in\mathcal{S}}\operatorname{tr}(s)$.
$\Box$

###### Lemma B.3

Let $a\in\mathbb{R}^{p\times p}$. Then,
$\operatorname{tr}(a)\leq\operatorname{tr}(|a|_{\mathcal{A}})$.

Proof  Let $\lambda_{1},\ldots,\lambda_{p}$ be eigenvalues of $a$, and let
$\kappa_{1},\ldots,\kappa_{p}$ be singular values of $a$. Then, by Weyl’s
inequality, we have

$\displaystyle\operatorname{tr}(a)=\sum_{i=1}^{p}\lambda_{i}\leq\sum_{i=1}^{p}|\lambda_{i}|\leq\sum_{i=1}^{p}\kappa_{i}=\operatorname{tr}(|a|_{\mathcal{A}}).$

$\Box$

We now show Lemmas 4.5 and 4.6.

Lemma 4.5 Let $s_{1},\ldots,s_{n}$ be $\\{-1,1\\}$-valued Rademacher variables
(i.e. independent uniform random variables taking values in $\\{-1,1\\}$) and
let $\sigma_{1},\ldots,\sigma_{n}$ be i.i.d. $\mathcal{A}$-valued random
variables each of whose element is the Rademacher variable. Let
$\mathbf{s}=\\{s_{i}\\}_{i=1}^{n}$, and
$\mathbf{z}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$. Then, we have

$\displaystyle\operatorname{tr}\hat{R}(\mathcal{G}(\mathcal{F}),\mathbf{s},\mathbf{z})\leq{L}\operatorname{tr}\hat{R}(\mathcal{F},\boldsymbol{\sigma},\mathbf{x}).$

Proof  For $f_{1},f_{2}\in\mathcal{F}$, we have

$\displaystyle\operatorname{tr}(|f_{1}(x_{i})-y_{i}|_{\mathcal{A}}^{2})-\operatorname{tr}(|f_{2}(x_{i})-y_{i}|_{\mathcal{A}}^{2})$
$\displaystyle=\operatorname{tr}((f_{1}(x_{i})-y_{i}+f_{2}(x_{i})-y_{i})^{*}(f_{1}(x_{i})-y_{i}-f_{2}(x_{i})+y_{i}))$
$\displaystyle=\|f_{1}(x_{i})-y_{i}+f_{2}(x_{i})-y_{i}\|_{\mathcal{A}}\,\|f_{1}(x_{i})-y_{i}-f_{2}(x_{i})+y_{i}\|_{\mathrm{HS}},$

where the first equality holds since for $a_{1},a_{2}\in\mathbb{R}^{p\times
p}$, $\operatorname{tr}(a_{1}^{*}a_{2})=\operatorname{tr}(a_{2}^{*}a_{1})$ and
$\|\cdot\|_{\mathrm{HS}}$ is the Hilbert–Schmidt norm in $\mathbb{C}^{p\times
p}$. In addition, we have

$\displaystyle\|f_{1}(x_{i})-y_{i}+f_{2}(x_{i})-y_{i}\|_{\mathcal{A}}$
$\displaystyle\leq\|\left\langle\phi(x_{i}),f_{1}+f_{2}\right\rangle_{k}-2y_{i}\|_{\mathcal{A}}$
$\displaystyle=\|k(x_{i},x_{i})\|^{1/2}\|f_{1}+f_{2}\|_{k}+2\|y_{i}\|_{\mathcal{A}}=2(B\sqrt{D}+E)=\frac{L}{\sqrt{2}}.$

Thus, by setting $\psi_{i}(f)=\operatorname{tr}(|f(x_{i})-y_{i}|^{2})$,
$\phi_{i}(f)=L/\sqrt{2}f(x_{i})$, and $\|\cdot\|=\|\cdot\|_{\mathrm{HS}}$ in
Theorem 3 of Maurer (2016), we obtain

$\displaystyle\operatorname{tr}\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}s_{i}|f(x_{i})-y_{i}|_{\mathcal{A}}^{2}\bigg{]}$
$\displaystyle=\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}s_{i}\operatorname{tr}(|f(x_{i})-y_{i}|_{\mathcal{A}}^{2})\bigg{]}\leq\sqrt{2}\frac{L}{\sqrt{2}}\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\left\langle\sigma_{i},f(x_{i})\right\rangle_{\mathrm{HS}}\bigg{]}$
$\displaystyle\leq
L\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\operatorname{tr}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})^{*}\sigma_{i}\bigg{|}_{\mathcal{A}}\bigg{]}=L\operatorname{tr}\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})^{*}\sigma_{i}\bigg{|}_{\mathcal{A}}\bigg{]}.$

$\Box$

Lemma 4.6 Let $z:\Omega\to\mathcal{X}\times\mathcal{Y}$ be a random variable
and let $g\in\mathcal{G}(\mathcal{F})$. Under the same notations and
assumptions as Proposition 4.5, for any $\delta\in(0,1)$, with probability
$\geq 1-\delta$, we have

$\displaystyle\operatorname{tr}\bigg{(}\mathrm{E}[g(z)]-\frac{1}{n}\sum_{i=1}^{n}g(x_{i},y_{i})\bigg{)}\leq
2\operatorname{tr}\hat{R}(\mathcal{G}(\mathcal{F}),\mathbf{s},\mathbf{z})+3\sqrt{2D}p\sqrt{\frac{\log({2}/{\delta})}{n}}.$

Proof  For a random variable
$S=(z_{1},\ldots,z_{n}):\Omega\to(\mathcal{X}\times\mathcal{Y})^{n}$, let
$\Phi(S)=\operatorname{tr}(\sup_{g\in\mathcal{G}(\mathcal{F})}(\mathrm{E}[g(z)]-1/n\sum_{i=1}^{n}g(z_{i})))$.
For $i=1,\ldots,n$, let $S_{i}=(z_{1}^{\prime},\ldots,z_{n}^{\prime})$, where
$z_{j}=z_{j}^{\prime}$ for $j\neq i$ and $z_{i}\neq z_{i}^{\prime}$. Then, we
have

$\displaystyle\Phi(S)-\Phi(S_{i})$
$\displaystyle\leq\operatorname{tr}\bigg{(}\sup_{g\in\mathcal{G}(\mathcal{F})}\bigg{(}\mathrm{E}[g(z)]-\frac{1}{n}\sum_{j=1}^{n}g(z_{j})\bigg{)}-\sup_{g\in\mathcal{G}(\mathcal{F})}\bigg{(}\mathrm{E}[g(z)]-\frac{1}{n}\sum_{j=1}^{n}g(z_{j}^{\prime})\bigg{)}\bigg{)}$
$\displaystyle\leq\frac{1}{n}\operatorname{tr}\bigg{(}\sup_{g\in\mathcal{G}(\mathcal{F})}\bigg{(}\sum_{j=1}^{n}g(z_{j})-\sum_{j=1}^{n}g(z_{j}^{\prime})\bigg{)}\bigg{)}=\frac{1}{n}\operatorname{tr}\bigg{(}\sup_{g\in\mathcal{G}(\mathcal{F})}(g(z_{i})-g(z_{i}^{\prime}))\bigg{)}$
$\displaystyle\leq\frac{p}{n}\sup_{g\in\mathcal{G}(\mathcal{F})}\|g(z_{i})-g(z_{i}^{\prime})\|_{\mathcal{A}}\leq\frac{2\sqrt{D}p}{n}.$

By McDiarmid’s inequality, for any $\delta\in(0,1)$, with probability $\geq
1-\delta/2$, we have

$\Phi(S)-\mathrm{E}[\Phi(S)]\leq\sqrt{\frac{1}{2}\sum_{i=1}^{n}\bigg{(}\frac{2\sqrt{D}p}{n}\bigg{)}^{2}\log\frac{2}{\delta}}=\sqrt{2D}p\sqrt{\frac{\log\frac{2}{\delta}}{n}}$

Thus, for any $g\in\mathcal{G}(\mathcal{F})$, we have

$\displaystyle\operatorname{tr}\bigg{(}\mathrm{E}[g(z)]-\frac{1}{n}\sum_{i=1}^{n}g(z_{i})\bigg{)}\leq\Phi(S)\leq\mathrm{E}[\Phi(S)]+\sqrt{2D}p\sqrt{\frac{\log\frac{2}{\delta}}{n}}.$

For the remaining part, the proof is the same as that of Theorem 3.3 of Mohri
et al. (2018). Since

$\Phi(S)=\operatorname{tr}\bigg{(}\sup_{g\in\mathcal{G}(\mathcal{F})}\bigg{(}\mathrm{E}[g(z)]-\frac{1}{n}\sum_{i=1}^{n}g(z_{i})\bigg{)}\bigg{)}=\sup_{g\in\mathcal{G}(\mathcal{F})}\bigg{(}\mathrm{E}[\operatorname{tr}(g(z))]-\frac{1}{n}\sum_{i=1}^{n}\operatorname{tr}(g(z_{i}))\bigg{)},$

we replace $g$ in the proof of Theorem 3.3 in Mohri et al. (2018) by
$z\mapsto\operatorname{tr}(g(z))$ in our case and derive

$\displaystyle\operatorname{tr}\bigg{(}\mathrm{E}[g(z)]-\frac{1}{n}\sum_{i=1}^{n}g(x_{i},y_{i})\bigg{)}$
$\displaystyle\leq
2\mathrm{E}\bigg{[}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}s_{i}\operatorname{tr}|f(x_{i})-y_{i}|_{\mathcal{A}}^{2}\bigg{]}+3\sqrt{2D}p\sqrt{\frac{\log\frac{2}{\delta}}{n}}$
$\displaystyle\leq
2\operatorname{tr}\hat{R}(\mathcal{G}(\mathcal{F}),\mathbf{s},\mathbf{z})+3\sqrt{2D}p\sqrt{\frac{\log\frac{2}{\delta}}{n}}.$

$\Box$

Proposition 4.7 For $a_{i,j}\in\mathcal{A}_{1}$, the computational complexity
for computing $(\mathbf{G}+\lambda I)^{-1}\mathbf{y}$ by direct methods for
solving linear systems of equations is $O(np^{2}\log p+n^{3}p)$.

Proof  Since all the elements of $\mathbf{G}$ and $\mathbf{y}$ are in
$\mathcal{A}_{1}$, we have

$(\mathbf{G}+\lambda
I)^{-1}\mathbf{y}=(\mathbf{F}\boldsymbol{\Lambda}_{\mathbf{G}+\lambda
I}^{-1}\mathbf{F}^{*})\mathbf{F}\boldsymbol{\Lambda}_{\mathbf{y}}F^{*}=\mathbf{F}\boldsymbol{\Lambda}_{\mathbf{G}+\lambda
I}^{-1}\boldsymbol{\Lambda}_{\mathbf{y}}F^{*},$

where $\mathbf{F}$ is the $\mathbb{C}^{p\times p}$-valued $n\times n$ diagonal
matrix whose diagonal elements are all $F$. In addition,
$\boldsymbol{\Lambda}_{\mathbf{G}+\lambda I}$ is the $\mathcal{A}_{1}$-valued
$n\times n$ whose $(i,j)$-entry is $\Lambda_{k(x_{i},x_{j})}$, and
$\boldsymbol{\Lambda}_{\mathbf{y}}$ is the vector in $\mathcal{A}_{1}^{n}$
whose $i$th element is $\Lambda_{y_{i}}$. If we use the fast Fourier
transformation, then the computational complexity of computing $Fy$ for
$y\in\mathbb{C}^{p\times p}$ is $O(p^{2}\log p)$. Moreover, since the
computational complexity of multiplication $\Lambda_{x}\Lambda_{y}$ for
$x,y\in\mathcal{A}_{1}$ is $O(p)$, using Gaussian elimination and back
substitution, the computational complexity of computing
$\boldsymbol{\Lambda}_{\mathbf{G}+\lambda
I}^{-1}\boldsymbol{\Lambda}_{\mathbf{y}}$ is $O(n^{3}p)$. As a result, the
total computational complexity is $O(np^{2}\log p+n^{3}p)$. $\Box$

Proposition 4.9 Let $a_{i,j}\in\mathcal{A}_{2}$ whose number of nonzero
elements is $O(p\log p)$. Then, the computational complexity for $1$ iteration
step of CG method is $O(n^{2}p^{2}\log p)$.

Proof  The computational complexity for computing $1$ iteration step of CG
method is equal to that of computing $(\mathbf{G}+\lambda I)\mathbf{b}$ for
$\mathbf{b}\in\mathcal{A}_{2}^{n}$. For $b\in\mathcal{A}_{2}$, the
computational complexity of computing $k(x_{i},x_{j})b$ is $O(p^{2}\log p)$
since those of computing $a_{i,j}b$ and $x_{i}b$ are both $O(p^{2}\log p)$.
(For $x_{i}b$, we use fast Fourier transformation.) Therefore, the
computational complexity of computing $(\mathbf{G}+\lambda I)\mathbf{b}$ is
$O(n^{2}p^{2}\log p)$. $\Box$

Proposition 5.1 For $a_{1},\ldots,a_{L},b_{1},\ldots,b_{L}\in\mathcal{A}_{1}$
and $\sigma_{1},\ldots,\sigma_{L}:\mathcal{A}_{1}\to\mathcal{A}_{1}$ each of
which has an expansion $\sigma_{j}(x)=\sum_{l=1}^{\infty}\alpha_{j,l}x^{l}$
with $\alpha_{j,l}\geq 0$, let
$\hat{k}:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{1}$ be defined as

$\displaystyle\hat{k}(x,y)=$
$\displaystyle\sigma_{L}(b_{L}^{*}b_{L}+\sigma_{L-1}(b_{L-1}^{*}b_{L-1}+\cdots+\sigma_{2}(b_{2}^{*}b_{2}+\sigma_{1}(b_{1}^{*}b_{1}+x^{*}a_{1}^{*}a_{1}y)a_{2}^{*}a_{2})\cdots\times
a_{L-1}^{*}a_{L-1})a_{L}^{*}a_{L}).$ (3)

Then, $\hat{k}$ is an $\mathcal{A}_{1}$-valued positive definite kernel.

Proof  Let $l:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{1}$ be an
$\mathcal{A}_{1}$-valued positive definite kernel and
$\sigma:\mathcal{A}_{1}\to\mathcal{A}_{1}$ be a map that has an expansion
$\sigma(x)=\sum_{j=1}^{\infty}\alpha_{j}x^{j}$ with $\alpha_{j}\geq 0$. Then,
$\sigma\circ l$ is also an $\mathcal{A}_{1}$-valued positive definite kernel.
Indeed, for $d_{1},\ldots,d_{n}\in\mathcal{A}_{1}$ and
$x_{1},\ldots,x_{n}\in\mathcal{X}$, we have

$\displaystyle\sum_{i,j=1}^{n}d_{i}^{*}\sigma(l(x_{i},x_{j}))d_{j}=\sum_{i,j=1}^{n}\sum_{s=1}^{\infty}\alpha_{s}d_{i}^{*}l(x_{i},x_{j})^{s}d_{j}\geq_{\mathcal{A}_{1}}0.$

Since $(x,y)\mapsto b_{1}^{*}b_{1}+x^{*}a_{1}^{*}a_{1}y$ is an
$\mathcal{A}_{1}$-valued positive definite kernel,
$(x,y)\mapsto\sigma_{1}(b_{1}^{*}b_{1}+x^{*}a_{1}^{*}a_{1}y)$ is also an
$\mathcal{A}_{1}$-valued positive definite kernel. Moreover, since
$\sigma_{1}(b_{1}^{*}b_{1}+x^{*}a_{1}^{*}a_{1}y)$ and $b_{2}$ are in
$\mathcal{A}_{1}$, $(x,y)\mapsto
b_{2}^{*}b_{2}+\sigma_{1}(b_{1}^{*}b_{1}+x^{*}a_{1}^{*}a_{1}y)$ is also an
$\mathcal{A}_{1}$-valued positive definite kernel. We iteratively apply the
above result and obtain the positive definiteness of $\hat{k}$. $\Box$

Proposition 5.2 The $\mathcal{A}_{1}$-valued positive definite kernel
$\hat{k}$ defined as Eq. (3) is composed of the sum of
$\mathcal{A}_{1}$-valued polynomial kernels.

Proof  Since $(x,y)\mapsto b_{1}^{*}b_{1}+x^{*}a_{1}^{*}a_{1}y$ is an
$\mathcal{A}_{1}$-valued polynomial kernel and
$\sigma:\mathcal{A}_{1}\to\mathcal{A}_{1}$ is a map that has an expansion
$\sigma(x)=\sum_{j=1}^{\infty}\alpha_{j}x^{j}$, $\hat{k}$ is composed of the
sum of $\mathcal{A}_{1}$-valued polynomial kernels. $\Box$

Proposition 5.4 Define
$\hat{k}:\mathcal{X}\times\mathcal{X}\to\mathcal{A}_{1}$ as

$\displaystyle\hat{k}(x,y)=\int_{\mathbb{R}}\int_{\mathbb{R}^{m}}c_{x}(\omega,\eta)^{*}c_{y}(\omega,\eta)\;\mathrm{d}\lambda_{\beta}(\omega)\mathrm{d}{\lambda}_{\sigma}(\eta),$
(6)

where
$\mathrm{d}\lambda_{\beta}(\omega)=\beta\mathrm{e}^{-\frac{\beta^{2}\omega^{2}}{2}}\mathrm{d}\omega$
for $\beta>0$ and

$\displaystyle c_{x}(\omega,\eta)=$
$\displaystyle\operatorname{circ}\Big{(}|x(z_{1})|\mathrm{e}^{\sqrt{-1}\omega\cdot
z_{1}}\mathrm{e}^{\sqrt{-1}\eta\cdot\tilde{x}(z_{1})},\cdots,|x(z_{p})|\mathrm{e}^{\sqrt{-1}\omega\cdot
z_{p}}\mathrm{e}^{\sqrt{-1}\eta\cdot\tilde{x}(z_{p})}\Big{)},$

for $x\in\mathcal{X}$, $\omega\in\mathbb{R}^{m}$, and $\eta\in\mathbb{R}$.
Then, $\hat{k}$ is an $\mathcal{A}_{1}$-valued positive definite kernel, and
for any $l=1,\ldots,p$, $\tilde{k}$ is written as

$\displaystyle\tilde{k}(x,y)=\frac{1}{p}\sum_{i,j=1}^{p}\hat{k}(x,y)_{i,j}=\sum_{j=1}^{p}\hat{k}(x,y)_{l,j},$

where $\hat{k}(x,y)_{i,j}$ is the $(i,j)$-entry of $\hat{k}(x,y)$.

Proof  The positive definiteness of $\hat{k}$ is trivial. As for the
relationship between $\tilde{k}$ and $\hat{k}$, we have

$\displaystyle\hat{k}(x,y)_{i,j}$
$\displaystyle=\int_{\mathbb{R}}\int_{\mathbb{R}^{m}}\sum_{l=1}^{p}|x(z_{p-i+2+l})|\mathrm{e}^{-\sqrt{-1}\omega\cdot
z_{p-i+2+l}}\mathrm{e}^{-\sqrt{-1}\eta\cdot\tilde{x}(z_{p-i+2+l})}$
$\displaystyle\qquad\qquad\times|y(z_{p-j+2+l})|\mathrm{e}^{\sqrt{-1}\omega\cdot
z_{p-j+2+l}}\mathrm{e}^{\sqrt{-1}\eta\cdot\tilde{y}(z_{p-j+2+l})}\mathrm{d}\lambda_{\beta}(\omega)\mathrm{d}{\lambda}_{\sigma}(\eta)$
$\displaystyle=\sum_{l=1}^{p}|x(z_{p-i+2+l})|\;|y(z_{p-j+2+l})|\mathrm{e}^{-\frac{1}{2\sigma^{2}}|\tilde{x}(z_{p-i+2+l})-\tilde{y}(z_{p-j+2+l})|^{2}}\mathrm{e}^{-\frac{1}{2\beta^{2}}\|z_{p-i+2+l}-z_{p-j+2+l}\|^{2}}.$

Thus, we have

$\displaystyle\sum_{i=1}^{p}\hat{k}(x,y)_{i,j}$
$\displaystyle=\sum_{i,l=1}^{p}|x(z_{l+j-i})|\;|y(z_{l})|\mathrm{e}^{-\frac{1}{2\beta^{2}}|\tilde{x}(z_{l+j-i})-\tilde{y}(z_{l})|^{2}}\mathrm{e}^{-\frac{1}{2\sigma^{2}}\|z_{l+j-i}-z_{l}\|^{2}}=\tilde{k}(x,y).$

$\Box$

Proposition 5.9 The $\mathcal{A}_{2}$-valued map $k$ defined as Eq. (8) is an
$\mathcal{A}_{2}$-valued positive definite kernel.

Proof  For $n\in\mathbb{N}$, $c_{1},\ldots,c_{n}\in\mathcal{A}_{2}$, and
$x_{1},\ldots,x_{n}\in\mathcal{A}_{1}^{d}$, we have

$\displaystyle\sum_{i,j=1}^{n}c_{i}^{*}k(x_{i},x_{j})c_{j}$
$\displaystyle=\int_{\mathbb{R}}\int_{\mathbb{R}^{m}}\sum_{i=1}^{n}\sum_{z\in\Omega}c_{i}^{*}a_{1}^{*}\mathbf{x}_{i}(z)a_{2}^{*}b(z,\omega)^{*}a_{3}^{*}\tilde{\mathbf{x}}_{i}(z,\eta)^{*}a_{4}^{*}\sum_{j=1}^{n}\sum_{z^{\prime}\in\Omega}a_{4}\tilde{\mathbf{x}}_{j}(z^{\prime},\eta)a_{3}b(z^{\prime},\omega)a_{2}\mathbf{x}_{j}(z^{\prime})a_{1}c_{j}\;\mathrm{d}\lambda_{\beta}(\omega)\mathrm{d}\lambda_{\sigma}(\eta),$

which is positive semi-definite. $\Box$

## References

  * Aizerman et al. (1964) Aizerman, M. A., Braverman, E. M., and Rozonoer, L.  Theoretical foundations of the potential function method in pattern recognition learning.  _Automation and Remote Control_ , 25:821–837, 1964.
  * Álvarez et al. (2012) Álvarez, M. A., Rosasco, L., Lawrence, N. D., et al.  Kernels for vector-valued functions: A review.  _Foundations and Trends® in Machine Learning_ , 4(3):195–266, 2012.
  * Aronszajn (1950) Aronszajn, N.  Theory of reproducing kernels.  _Transactions of the American mathematical society_ , 68(3):337–404, 1950.
  * Audiffren & Kadri (2013) Audiffren, J. and Kadri, H.  Stability of multi-task kernel regression algorithms.  In _Proceedings of the 5th Asian Conference on Machine Learning (ACML)_ , pp. 1–16, 2013.
  * Boser et al. (1992) Boser, B. E., Guyon, I. M., and Vapnik, V. N.  A training algorithm for optimal margin classifiers.  In _Proceedings of the 5th annual workshop on Computational learning theory (COLT)_ , pp. 144–152, 1992.
  * Brouard et al. (2016) Brouard, C., Szafranski, M., and d’Alché Buc, F.  Input output kernel regression: Supervised and semi-supervised structured output prediction with operator-valued kernels.  _Journal of Machine Learning Research_ , 17:1–48, 2016\.
  * Caponnetto & De Vito (2007) Caponnetto, A. and De Vito, E.  Optimal rates for the regularized least-squares algorithm.  _Foundations of Computational Mathematics_ , 7(3):331–368, 2007.
  * Chanda & Majumder (2011) Chanda, B. and Majumder, D. D.  _Digital Image Processing and Analysis_.  PHI Learning, 2nd edition, 2011.
  * Christmann & Steinwart (2008) Christmann, A. and Steinwart, I.  _Support Vector Machines_.  Springer, 2008.
  * Gray (2006) Gray, R. M.  Toeplitz and circulant matrices: A review.  _Foundations and Trends in Communications and Information Theory_ , 2(3):155–239, 2006.
  * Hashimoto et al. (2021) Hashimoto, Y., Ishikawa, I., Ikeda, M., Komura, F., Katsura, T., and Kawahara, Y.  Reproducing kernel Hilbert $C^{*}$-module and kernel mean embeddings.  _Journal of Machine Learning Research_ , 22(267):1–56, 2021.
  * Hashimoto et al. (2022) Hashimoto, Y., Wang, Z., and Matsui, T.  $C^{*}$-algebra net: a new approach generalizing neural network parameters to $C^{*}$-algebra.  In _Proceedings of the 39th International Conference on Machine Learning (ICML)_ , 2022.
  * Heo (2008) Heo, J.  Reproducing kernel Hilbert $C^{*}$-modules and kernels associated with cocycles.  _Journal of Mathematical Physics_ , 49(10):103507, 2008.
  * Hestenes & Stiefel (1952) Hestenes, M. R. and Stiefel, E.  Methods of conjugate gradients for solving linear systems.  _Journal of Research of the National Bureau of Standards_ , 49:409–436, 1952.
  * Huusari & Kadri (2021) Huusari, R. and Kadri, H.  Entangled kernels - beyond separability.  _Journal of Machine Learning Research_ , 22(24):1–40, 2021.
  * Kadri et al. (2016) Kadri, H., Duflos, E., Preux, P., Canu, S., Rakotomamonjy, A., and Audiffren, J.  Operator-valued kernels for learning from functional response data.  _Journal of Machine Learning Research_ , 17(20):1–54, 2016.
  * Kirillov (1976) Kirillov, A. A.  _Elements of the Theory of Representations_.  Springer, 1976.
  * Laforgue et al. (2020) Laforgue, P., Lambert, A., Brogat-Motte, L., and d’Alché-Buc, F.  Duality in RKHSs with infinite dimensional outputs: Application to robust losses.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , 2020.
  * Lance (1995) Lance, E. C.  _Hilbert $C^{*}$-modules – a Toolkit for Operator Algebraists_.  London Mathematical Society Lecture Note Series, vol. 210. Cambridge University Press, 1995.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Li et al. (2021) Li, Z., Liu, F., Yang, W., Peng, S., and Zhou, J.  A survey of convolutional neural networks: Analysis, applications, and prospects.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2021\.
  * Mairal (2016) Mairal, J.  End-to-end kernel learning with supervised convolutional kernel networks.  In _Proceedings of the Advances in Neural Information Processing Systems 29 (NIPS)_ , 2016.
  * Mairal et al. (2014) Mairal, J., Koniusz, P., Harchaoui, Z., and Schmid, C.  Convolutional kernel networks.  In _Proceedings of the Advances in Neural Information Processing Systems 27 (NIPS)_ , 2014.
  * Manuilov & Troitsky (2000) Manuilov, V. M. and Troitsky, E. V.  Hilbert $C^{*}$ and $W^{*}$-modules and their morphisms.  _Journal of Mathematical Sciences_ , 98(2):137–201, 2000.
  * Maurer (2016) Maurer, A.  A vector-contraction inequality for rademacher complexities.  In _Proceedings of the 27th International Conference on Algorithmic Learning Theory (ALT)_ , 2016.
  * Micchelli & Pontil (2005) Micchelli, C. A. and Pontil, M.  On learning vector-valued functions.  _Neural Computation_ , 17(1):177–204, 2005.
  * Minh et al. (2016) Minh, H. Q., Bazzani, L., and Murino, V.  A unifying framework in vector-valued reproducing kernel Hilbert spaces for manifold regularization and co-regularized multi-view learning.  _Journal of Machine Learning Research_ , 17(25):1–72, 2016.
  * Mohri et al. (2018) Mohri, M., Rostamizadeh, A., and Talwalkar, A.  _Foundations of Machine Learning_.  MIT press, 2018.
  * Moslehian (2022) Moslehian, M. S.  Vector-valued reproducing kernel Hilbert $C^{*}$-modules.  _Complex Analysis and Operator Theory_ , 16(1):Paper No. 2, 2022.
  * Murphy (1990) Murphy, G. J.  _$C^{*}$ -Algebras and Operator Theory_.  Academic Press, 1990.
  * Murphy (2012) Murphy, K. P.  _Machine Learning: A Probabilistic Perspective_.  The MIT Press, 2012.
  * Rahimi & Recht (2007) Rahimi, A. and Recht, B.  Random features for large-scale kernel machines.  In _Proceedings of the Advances in Neural Information Processing Systems 20 (NIPS)_ , 2007.
  * Sangnier et al. (2016) Sangnier, M., Fercoq, O., and d'Alché-Buc, F.  Joint quantile regression in vector-valued RKHSs.  In _Proceedings of the Advances in Neural Information Processing Systems 29 (NIPS)_ , 2016.
  * Schölkopf & Smola (2002) Schölkopf, B. and Smola, A. J.  _Learning with kernels: support vector machines, regularization, optimization, and beyond_.  MIT press, 2002.
  * Schölkopf et al. (2001) Schölkopf, B., Herbrich, R., and Smola, A. J.  A generalized representer theorem.  In _Proceedings of the 14th Annual Conference on Computational Learning Theory (COLT)_ , 2001.
  * Shawe-Taylor & Cristianini (2004) Shawe-Taylor, J. and Cristianini, N.  _Kernel Methods for Pattern Analysis_.  Cambridge university press, 2004.
  * Sindhwani et al. (2013) Sindhwani, V., Minh, H. Q., and Lozano, A. C.  Scalable matrix-valued kernel learning for high-dimensional nonlinear multivariate regression and granger causality.  In _Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence (UAI)_ , 2013.
  * Trefethen & Bau (1997) Trefethen, L. N. and Bau, D.  _Numerical Linear Algebra_.  SIAM, 1997.
  * Van Loan (1992) Van Loan, C.  _Computational Frameworks for the Fast Fourier Transform_.  SIAM, 1992.