Reproducing kernel Hilbert space explained

In functional analysis (a branch of mathematics), a reproducing kernel Hilbert space (RKHS) is a Hilbert space of functions in which point evaluation is a continuous linear functional. Roughly speaking, this means that if two functions

f

and

g

in the RKHS are close in norm, i.e.,

\|f-g\|

is small, then

f

and

g

are also pointwise close, i.e.,

|f(x)-g(x)|

is small for all

x

. The converse does not need to be true. Informally, this can be shown by looking at the supremum norm: the sequence of functions

\sin2n(x)

converges pointwise, but does not converge uniformly i.e. does not converge with respect to the supremum norm. (This is not a counterexample because the supremum norm does not arise from any inner product due to not satisfying the parallelogram law.)

It is not entirely straightforward to construct a Hilbert space of functions which is not an RKHS.[1] Some examples, however, have been found.[2] [3]

L2 spaces are not Hilbert spaces of functions (and hence not RKHSs), but rather Hilbert spaces of equivalence classes of functions (for example, the functions

f

and

g

defined by

f(x)=0

and

g(x)=1Q

are equivalent in L2). However, there are RKHSs in which the norm is an L2-norm, such as the space of band-limited functions (see the example below).

An RKHS is associated with a kernel that reproduces every function in the space in the sense that for every

x

in the set on which the functions are defined, "evaluation at

x

" can be performed by taking an inner product with a function determined by the kernel. Such a reproducing kernel exists if and only if every evaluation functional is continuous.

The reproducing kernel was first introduced in the 1907 work of Stanisław Zaremba concerning boundary value problems for harmonic and biharmonic functions. James Mercer simultaneously examined functions which satisfy the reproducing property in the theory of integral equations. The idea of the reproducing kernel remained untouched for nearly twenty years until it appeared in the dissertations of Gábor Szegő, Stefan Bergman, and Salomon Bochner. The subject was eventually systematically developed in the early 1950s by Nachman Aronszajn and Stefan Bergman.[4]

These spaces have wide applications, including complex analysis, harmonic analysis, and quantum mechanics. Reproducing kernel Hilbert spaces are particularly important in the field of statistical learning theory because of the celebrated representer theorem which states that every function in an RKHS that minimises an empirical risk functional can be written as a linear combination of the kernel function evaluated at the training points. This is a practically useful result as it effectively simplifies the empirical risk minimization problem from an infinite dimensional to a finite dimensional optimization problem.

For ease of understanding, we provide the framework for real-valued Hilbert spaces. The theory can be easily extended to spaces of complex-valued functions and hence include the many important examples of reproducing kernel Hilbert spaces that are spaces of analytic functions.[5]

Definition

Let

X

be an arbitrary set and

H

a Hilbert space of real-valued functions on

X

, equipped with pointwise addition and pointwise scalar multiplication. The evaluation functional over the Hilbert space of functions

H

is a linear functional that evaluates each function at a point

x

,

Lx:f\mapstof(x)\forallf\inH.

We say that H is a reproducing kernel Hilbert space if, for all

x

in

X

,

Lx

is continuous at every

f

in

H

or, equivalently, if

Lx

is a bounded operator on

H

, i.e. there exists some

Mx>0

such that

Although

Mx<infty

is assumed for all

x\inX

, it might still be the case that \sup_x M_x = \infty.

While property is the weakest condition that ensures both the existence of an inner product and the evaluation of every function in

H

at every point in the domain, it does not lend itself to easy application in practice. A more intuitive definition of the RKHS can be obtained by observing that this property guarantees that the evaluation functional can be represented by taking the inner product of

f

with a function

Kx

in

H

. This function is the so-called reproducing kernel for the Hilbert space

H

from which the RKHS takes its name. More formally, the Riesz representation theorem implies that for all

x

in

X

there exists a unique element

Kx

of

H

with the reproducing property,

Since

Kx

is itself a function defined on

X

with values in the field

R

(or

C

in the case of complex Hilbert spaces) and as

Kx

is in

H

we have that

Kx(y)=Ly(Kx)=\langleKx,Ky\rangleH,

where

Ky\inH

is the element in

H

associated to

Ly

.

This allows us to define the reproducing kernel of

H

as a function

K:X x X\toR

(or

C

in the complex case) by

K(x,y)=\langleKx,Ky\rangleH.

From this definition it is easy to see that

K:X x X\toR

(or

C

in the complex case) is both symmetric (resp. conjugate symmetric) and positive definite, i.e.
n
\sum
i,j=1

cicjK(xi,xj)= \sum

n
i=1

ci\left\langle

K
xi

,

n
\sum
j=1

cj

K
xj

\right\rangleH=\left\langle

n
\sum
i=1

ci

K
xi

,

n
\sum
j=1

cj

K
xj

\right\rangleH

nc
= \left\|\sum
iK
xi
2
\right\|
H

\ge0

for every

n\inN,x1,...,xn\inX,andc1,...,cn\inR.

[6] The Moore–Aronszajn theorem (see below) is a sort of converse to this: if a function

K

satisfies these conditions then there is a Hilbert space of functions on

X

for which it is a reproducing kernel.

Example

The space of bandlimited continuous functions

H

is a RKHS, as we now show. Formally, fix some cutoff frequency

0<a<infty

and define the Hilbert space

H=\{f\inC(R)\mid\operatorname{supp}(F)\subset[-a,a]\}

where

C(R)

is the set of continuous square integrable functions, and F(\omega) = \int_^\infty f(t) e^ \, dt is the Fourier transform of

f

. As the inner product of this Hilbert space, we use

\langlef,

g\rangle
L2

=

infty
\int
-infty

f(x)\overline{g(x)}dx.

From the Fourier inversion theorem, we have

f(x)=

1
2\pi
a
\int
-a

F(\omega)eixd\omega.

It then follows by the Cauchy–Schwarz inequality and Plancherel's theorem that, for all

x

,

|f(x)|\le

1
2\pi

\sqrt{

a
2a\int
-a

|F(\omega)|2d\omega}=

\sqrt{2a
}{2\pi}\sqrt{\int
infty
-infty

|F(\omega)|2d\omega}=\sqrt{

a
\pi
} \|f\|_.

This inequality shows that the evaluation functional is bounded, proving that

H

is indeed a RKHS.

The kernel function

Kx

in this case is given by

Kx(y)=

a
\pi

\operatorname{sinc}\left(

a
\pi

(y-x)\right)=

\sin(a(y-x))
\pi(y-x)

.

The Fourier transform of

Kx(y)

defined above is given by
infty
\int
-infty
-i\omegay
K
x(y)e

dy=\begin{cases} e-i&if\omega\in[-a,a],\\ 0&rm{otherwise}, \end{cases}

which is a consequence of the time-shifting property of the Fourier transform. Consequently, using Plancherel's theorem, we have

\langlef,Kx\rangle

L2

=

infty
\int
-infty

f(y)\overline{Kx(y)}dy=

1
2\pi
a
\int
-a

F(\omega)ei\omegad\omega=f(x).

Thus we obtain the reproducing property of the kernel.

Kx

in this case is the "bandlimited version" of the Dirac delta function, and that

Kx(y)

converges to

\delta(y-x)

in the weak sense as the cutoff frequency

a

tends to infinity.

Moore–Aronszajn theorem

We have seen how a reproducing kernel Hilbert space defines a reproducing kernel function that is both symmetric and positive definite. The Moore–Aronszajn theorem goes in the other direction; it states that every symmetric, positive definite kernel defines a unique reproducing kernel Hilbert space. The theorem first appeared in Aronszajn's Theory of Reproducing Kernels, although he attributes it to E. H. Moore.

Theorem. Suppose K is a symmetric, positive definite kernel on a set X. Then there is a unique Hilbert space of functions on X for which K is a reproducing kernel.

Proof. For all x in X, define Kx = K(x, ⋅). Let H0 be the linear span of . Define an inner product on H0 by

\left\langle

n
\sum
j=1

bj

K
yj

,

m
\sum
i=1

ai

K
xi

\right

\rangle
H0

=

m
\sum
i=1
n
\sum
j=1

{ai}bjK(yj,xi),

which implies

K(x,y)=\left\langleKx,Ky

\right\rangle
H0
.The symmetry of this inner product follows from the symmetry of K and the non-degeneracy follows from the fact that K is positive definite.

Let H be the completion of H0 with respect to this inner product. Then H consists of functions of the form

f(x)=

infty
\sum
i=1

ai

K
xi

(x)where\limn\supp\geq0

n+p
\left\|\sum
i=n

ai

K
xi
\right\|
H0

=0.

Now we can check the reproducing property :

\langlef,Kx\rangleH=

infty
\sum
i=1

ai\left\langle

K
xi

,Kx\right

\rangle
H0

=

infty
\sum
i=1

aiK(xi,x)=f(x).

To prove uniqueness, let G be another Hilbert space of functions for which K is a reproducing kernel. For every x and y in X, implies that

\langleKx,Ky\rangleH=K(x,y)=\langleKx,Ky\rangleG.

By linearity,

\langle,\rangleH=\langle,\rangleG

on the span of

\{Kx:x\inX\}

. Then

H\subsetG

because G is complete and contains H0 and hence contains its completion.

Now we need to prove that every element of G is in H. Let

f

be an element of G. Since H is a closed subspace of G, we can write

f=fH+

f
H\bot

where

fH\inH

and
f
H\bot

\inH\bot

. Now if

x\inX

then, since K is a reproducing kernel of G and H:

f(x)=\langleKx,f\rangleG=\langleKx,fH\rangleG+\langleKx,

f
H\bot

\rangleG=\langleKx,fH\rangleG=\langleKx,fH\rangleH=fH(x),

where we have used the fact that

Kx

belongs to H so that its inner product with
f
H\bot

in G is zero.This shows that

f=fH

in G and concludes the proof.

Integral operators and Mercer's theorem

We may characterize a symmetric positive definite kernel

K

via the integral operator using Mercer's theorem and obtain an additional view of the RKHS. Let

X

be a compact space equipped with a strictly positive finite Borel measure

\mu

and

K:X x X\to\R

a continuous, symmetric, and positive definite function. Define the integral operator

TK:L2(X)\toL2(X)

as

[TKf]()=\intXK(,t)f(t)d\mu(t)

where

L2(X)

is the space of square integrable functions with respect to

\mu

.

Mercer's theorem states that the spectral decomposition of the integral operator

TK

of

K

yields a series representation of

K

in terms of the eigenvalues and eigenfunctions of

TK

. This then implies that

K

is a reproducing kernel so that the corresponding RKHS can be defined in terms of these eigenvalues and eigenfunctions. We provide the details below.

Under these assumptions

TK

is a compact, continuous, self-adjoint, and positive operator. The spectral theorem for self-adjoint operators implies that there is an at most countable decreasing sequence

(\sigmai)i\geq0

such that \lim_\sigma_i = 0 and

TK\varphii(x)=\sigmai\varphii(x)

, where the

\{\varphii\}

form an orthonormal basis of

L2(X)

. By the positivity of

TK,\sigmai>0

for all

i.

One can also show that

TK

maps continuously into the space of continuous functions

C(X)

and therefore we may choose continuous functions as the eigenvectors, that is,

\varphii\inC(X)

for all

i.

Then by Mercer's theorem

K

may be written in terms of the eigenvalues and continuous eigenfunctions as

K(x,y)=

infty
\sum
j=1

\sigmaj\varphij(x)\varphij(y)

for all

x,y\inX

such that

\limn\supu,v\left|K(u,v)-

n
\sum
j=1

\sigmaj\varphij(u)\varphij(v)\right|=0.

This above series representation is referred to as a Mercer kernel or Mercer representation of

K

.

Furthermore, it can be shown that the RKHS

H

of

K

is given by

H=\left\{f\inL2(X)\vert

infty
\sum
i=1
\left\langlef,\varphii\right
2
\rangle
L2
\sigmai

<infty\right\}

where the inner product of

H

given by

\left\langlef,g\right\rangleH=

infty
\sum
i=1
\left\langlef,\varphii
\right\rangle
L2
\left\langleg,\varphii
\right\rangle
L2
\sigmai

.

This representation of the RKHS has application in probability and statistics, for example to the Karhunen-Loève representation for stochastic processes and kernel PCA.

Feature maps

A feature map is a map

\varphi\colonXF

, where

F

is a Hilbert space which we will call the feature space. The first sections presented the connection between bounded/continuous evaluation functions, positive definite functions, and integral operators and in this section we provide another representation of the RKHS in terms of feature maps.

Every feature map defines a kernel via

Clearly

K

is symmetric and positive definiteness follows from the properties of inner product in

F

. Conversely, every positive definite function and corresponding reproducing kernel Hilbert space has infinitely many associated feature maps such that holds.

For example, we can trivially take

F=H

and

\varphi(x)=Kx

for all

x\inX

. Then is satisfied by the reproducing property. Another classical example of a feature map relates to the previous section regarding integral operators by taking

F=\ell2

and

\varphi(x)=(\sqrt{\sigmai}\varphii(x))i

.

This connection between kernels and feature maps provides us with a new way to understand positive definite functions and hence reproducing kernels as inner products in

H

. Moreover, every feature map can naturally define a RKHS by means of the definition of a positive definite function.

Lastly, feature maps allow us to construct function spaces that reveal another perspective on the RKHS. Consider the linear space

H\varphi=\{f:X\toR\mid\existsw\inF,f(x)=\langlew,\varphi(x)\rangleF,\forallx\inX\}.

We can define a norm on

H\varphi

by

\|f\|\varphi=inf\{\|w\|F:w\inF,f(x)=\langlew,\varphi(x)\rangleF,\forallx\inX\}.

It can be shown that

H\varphi

is a RKHS with kernel defined by

K(x,y)=\langle\varphi(x),\varphi(y)\rangleF

. This representation implies that the elements of the RKHS are inner products of elements in the feature space and can accordingly be seen as hyperplanes. This view of the RKHS is related to the kernel trick in machine learning.[7]

Properties

Useful properties of RKHSs:

(Xi)

p
i=1
be a sequence of sets and

(Ki)

p
i=1
be a collection of corresponding positive definite functions on

(Xi)

p.
i=1
It then follows that

K((x1,\ldots,xp),(y1,\ldots,yp))=K1(x1,y1)Kp(xp,yp)

is a kernel on

X=X1 x ... x Xp.

X0\subsetX,

then the restriction of

K

to

X0 x X0

is also a reproducing kernel.

K

such that

K(x,x)=1

for all

x\inX

. Define a pseudo-metric on X as

dK(x,y)=\|Kx-Ky\|

2
H

=2(1-K(x,y))    \forallx\inX.

By the Cauchy–Schwarz inequality,

K(x,y)2\leK(x,x)K(y,y)=1    \forallx,y\inX.

This inequality allows us to view

K

as a measure of similarity between inputs. If

x,y\inX

are similar then

K(x,y)

will be closer to 1 while if

x,y\inX

are dissimilar then

K(x,y)

will be closer to 0.

\{Kx\midx\inX\}

coincides with

H

.[8]

Common examples

Bilinear kernels

K(x,y)=\langlex,y\rangle

The RKHS

H

corresponding to this kernel is the dual space, consisting of functions

f(x)=\langlex,\beta\rangle

satisfying
2=\|\beta\|
\|f\|
H

2

.

Polynomial kernels

K(x,y)=(\alpha\langlex,y\rangle+1)d,    \alpha\in\R,d\in\N

Radial basis function kernels

These are another common class of kernels which satisfy

K(x,y)=K(\|x-y\|)

. Some examples include:

K(x,y)=

-\|x-y\|2
2\sigma2
e

,    \sigma>0

K(x,y)=

-\|x-y\|
\sigma
e

,    \sigma>0

The squared norm of a function

f

in the RKHS

H

with this kernel is:[9] [10]
2=\int
\|f\|
R

(

1{\sigma}
f(x)

2+\sigmaf'(x)2)dx.

Bergman kernels

We also provide examples of Bergman kernels. Let X be finite and let H consist of all complex-valued functions on X. Then an element of H can be represented as an array of complex numbers. If the usual inner product is used, then Kx is the function whose value is 1 at x and 0 everywhere else, and

K(x,y)

can be thought of as an identity matrix since

K(x,y)=\begin{cases}1&x=y\ 0&xy\end{cases}

In this case, H is isomorphic to

\Complexn

.

The case of

X=D

(where

D

denotes the unit disc) is more sophisticated. Here the Bergman space

H2(D)

is the space of square-integrable holomorphic functions on

D

. It can be shown that the reproducing kernel for

H2(D)

is
K(x,y)=1
\pi
1
(1-x\overline{y

)2}.

Lastly, the space of band limited functions in

L2(\R)

with bandwidth

2a

is a RKHS with reproducing kernel
K(x,y)=\sina(x-y)
\pi(x-y)

.

Extension to vector-valued functions

In this section we extend the definition of the RKHS to spaces of vector-valued functions as this extension is particularly important in multi-task learning and manifold regularization. The main difference is that the reproducing kernel

\Gamma

is a symmetric function that is now a positive semi-definite matrix for every

x,y

in

X

. More formally, we define a vector-valued RKHS (vvRKHS) as a Hilbert space of functions

f:X\toRT

such that for all

c\inRT

and

x\inX

\Gammaxc(y)=\Gamma(x,y)c\inHfory\inX

and

\langlef,\Gammaxc\rangleH=f(x)\intercalc.

This second property parallels the reproducing property for the scalar-valued case. This definition can also be connected to integral operators, bounded evaluation functions, and feature maps as we saw for the scalar-valued RKHS. We can equivalently define the vvRKHS as a vector-valued Hilbert space with a bounded evaluation functional and show that this implies the existence of a unique reproducing kernel by the Riesz Representation theorem. Mercer's theorem can also be extended to address the vector-valued setting and we can therefore obtain a feature map view of the vvRKHS. Lastly, it can also be shown that the closure of the span of

\{\Gammaxc:x\inX,c\inRT\}

coincides with

H

, another property similar to the scalar-valued case.

We can gain intuition for the vvRKHS by taking a component-wise perspective on these spaces. In particular, we find that every vvRKHS is isometrically isomorphic to a scalar-valued RKHS on a particular input space. Let

Λ=\{1,...,T\}

. Consider the space

X x Λ

and the corresponding reproducing kernel

As noted above, the RKHS associated to this reproducing kernel is given by the closure of the span of

\{\gamma(x,t):x\inX,t\inΛ\}

where

\gamma(x,t)(y,s)=\gamma((x,t),(y,s))

for every set of pairs

The connection to the scalar-valued RKHS can then be made by the fact that every matrix-valued kernel can be identified with a kernel of the form of via

\Gamma(x,y)(t,s)=\gamma((x,t),(y,s)).

Moreover, every kernel with the form of defines a matrix-valued kernel with the above expression. Now letting the map

D:H\Gamma\toH\gamma

be defined as

(Df)(x,t)=\langlef(x),et

\rangle
RT

where

et

is the

tth

component of the canonical basis for

RT

, one can show that

D

is bijective and an isometry between

H\Gamma

and

H\gamma

.

While this view of the vvRKHS can be useful in multi-task learning, this isometry does not reduce the study of the vector-valued case to that of the scalar-valued case. In fact, this isometry procedure can make both the scalar-valued kernel and the input space too difficult to work with in practice as properties of the original kernels are often lost.[11] [12] [13]

An important class of matrix-valued reproducing kernels are separable kernels which can factorized as the product of a scalar valued kernel and a

T

-dimensional symmetric positive semi-definite matrix. In light of our previous discussion these kernels are of the form

\gamma((x,t),(y,s))=K(x,y)KT(t,s)

for all

x,y

in

X

and

t,s

in

T

. As the scalar-valued kernel encodes dependencies between the inputs, we can observe that the matrix-valued kernel encodes dependencies among both the inputs and the outputs.

We lastly remark that the above theory can be further extended to spaces of functions with values in function spaces but obtaining kernels for these spaces is a more difficult task.[14]

Connection between RKHSs and the ReLU function

The ReLU function is commonly defined as

f(x)=max\{0,x\}

and is a mainstay in the architecture of neural networks where it is used as an activation function. One can construct a ReLU-like nonlinear function using the theory of reproducing kernel Hilbert spaces. Below, we derive this construction and show how it implies the representation power of neural networks with ReLU activations.

We will work with the Hilbert space

1
l{H}=L
2(0)[0,

infty)

of absolutely continuous functions with

f(0)=0

and square integrable (i.e.

L2

) derivative. It has the inner product

\langlef,g\ranglel{H

} = \int_0^\infty f'(x)g'(x) \, dx .

To construct the reproducing kernel it suffices to consider a dense subspace, so let

f\inC1[0,infty)

and

f(0)=0

. The Fundamental Theorem of Calculus then gives

f(y)=

y
\int
0

f'(x)dx=

infty
\int
0

G(x,y)f'(x)dx=\langleKy,f\rangle

where

G(x,y)=\begin{cases}1,&x<y\\ 0,&otherwise \end{cases}

and

Ky'(x)=G(x,y),Ky(0)=0

i.e.

K(x,y)=Ky(x)=\int

x
0

G(z,y)dz= \begin{cases} x,&0\leqx<y\\ y,&otherwise. \end{cases}=min(x,y)

This implies

Ky=K(,y)

reproduces

f

.

Moreover the minimum function on

X x X=[0,infty) x [0,infty)

has the following representations with the ReLu function:

min(x,y)=x-\operatorname{ReLU}(x-y)=y-\operatorname{ReLU}(y-x).

Using this formulation, we can apply the representer theorem to the RKHS, letting one prove the optimality of using ReLU activations in neural network settings.

See also

References

Notes and References

  1. Alpay, D., and T. M. Mills. "A family of Hilbert spaces which are not reproducing kernel Hilbert spaces." J. Anal. Appl. 1.2 (2003): 107–111.
  2. Z. Pasternak-Winiarski, "On weights which admit reproducing kernel of Bergman type", International Journal of Mathematics and Mathematical Sciences, vol. 15, Issue 1, 1992.
  3. T. Ł. Żynda, "On weights which admit reproducing kernel of Szegő type", Journal of Contemporary Mathematical Analysis (Armenian Academy of Sciences), 55, 2020.
  4. Okutmustur
  5. Paulson
  6. Durrett
  7. Rosasco
  8. Rosasco
  9. Berlinet, Alain and Thomas, Christine. Reproducing kernel Hilbert spaces in Probability and Statistics, Kluwer Academic Publishers, 2004
  10. Thomas-Agnan C . Computing a family of reproducing kernels for statistical applications. Numerical Algorithms, 13, pp. 21-32 (1996)
  11. De Vito
  12. Zhang
  13. Alvarez
  14. Rosasco