The Moore–Aronszajn Construction

Why a Kernel Determines a Function Space

A positive definite kernel assigns an inner product to every finite collection of its sections. But those finite combinations need not yet form a Hilbert space: different combinations can represent the same function, and even a well-defined inner-product space may be incomplete. The Moore–Aronszajn construction resolves both issues. It removes directions that have zero length, then completes what remains without losing the kernel’s evaluation structure.

The result is important because it makes the connection between a kernel and its associated function space precise. Starting from the kernel alone, the construction produces a Hilbert space of functions in which evaluation at any input is represented by the corresponding kernel section.

From Kernel Sections to an Inner-Product Space

Let $\mathcal X$ be a nonempty set. Throughout, a real-valued kernel is a function $k:\mathcal X\times\mathcal X\to\mathbb R$. We use the following convention for positive definiteness.

Definition: The kernel $k$ is positive definite if it is symmetric and, for every integer $m\geq 1$, every $x_1,\ldots,x_m\in\mathcal X$, and every $a_1,\ldots,a_m\in\mathbb R$, $$ \sum_{i=1}^{m}\sum_{j=1}^{m}a_i a_j k(x_i,x_j)\geq 0. $$ The inequality is not required to be strict. Thus a nonzero coefficient vector can have quadratic form zero.

For each $x\in\mathcal X$, the kernel section at $x$ is the function $k_x:\mathcal X\to\mathbb R$ defined by $k_x(z)=k(x,z)$. Begin with all finite formal linear combinations of symbols $e_x$, one for each $x\in\mathcal X$. Give this vector space the symmetric bilinear form

\left\langle \sum_{i=1}^{m}a_i e_{x_i},\, \sum_{j=1}^{r}b_j e_{y_j}\right\rangle_0 = \sum_{i=1}^{m}\sum_{j=1}^{r}a_i b_j k(x_i,y_j).

Positive definiteness says that $\langle u,u\rangle_0\geq 0$, but it does not guarantee that $\langle u,u\rangle_0=0$ only for $u=0$. The construction therefore has two essential steps: first quotient out all zero-length vectors, then take the Hilbert-space completion.

Worked Example: A Strictly Positive Two-Point Kernel

Take $\mathcal X=\{a,b\}$ and set $k(a,a)=k(b,b)=1$, $k(a,b)=k(b,a)=1/2$. Its Gram matrix is $$ G=\begin{pmatrix}1&1/2\\1/2&1\end{pmatrix}. $$ The eigenvalues are $3/2$ and $1/2$, both positive, so the quadratic form is strictly positive for every nonzero coefficient vector.

For $u=2e_a-e_b$, its squared length is $$ \langle u,u\rangle_0=2^2+2(2)(-1)(1/2)+(-1)^2=4-2+1=3. $$ The corresponding function is $2k_a-k_b$. Its values are $2-(1/2)=3/2$ at $a$, and $1-1=0$ at $b$. In this example the finite span already has positive length for every nonzero vector, so no nontrivial quotient is needed.

Quotienting Zero-Length Combinations

Write $\|u\|_0^2=\langle u,u\rangle_0$, and let $N=\{u:\|u\|_0=0\}$. A semidefinite bilinear form satisfies the Cauchy–Schwarz inequality. In this setting it follows directly by applying nonnegativity to $\|u+t v\|_0^2$ for every real $t$: if $\|v\|_0^2>0$, the quadratic in $t$ cannot have positive discriminant, giving $|\langle u,v\rangle_0|^2\leq\|u\|_0^2\|v\|_0^2$. If $\|v\|_0^2=0$, nonnegativity of that same expression for all $t$ forces $\langle u,v\rangle_0=0$, which gives the inequality in that case as well.

Consequently every $n\in N$ is orthogonal to every vector. In particular, $N$ is a subspace: sums and scalar multiples of its elements remain orthogonal to every vector, and hence have zero squared length. The form therefore gives a genuine inner product on the quotient $V/N$, where two vectors are identified when their difference lies in $N$.

Result: The quotient inner product is $\langle [u],[v]\rangle=\langle u,v\rangle_0$, where $[u]$ denotes the equivalence class of $u$. It is well-defined because changing either representative adds a vector in $N$, which is orthogonal to every vector. It is positive definite because $\langle [u],[u]\rangle=0$ implies $u\in N$, hence $[u]=[0]$.

These quotient classes can be identified with actual functions, rather than left as formal symbols. Associate to $u=\sum_i a_i e_{x_i}$ the function $$ (Tu)(z)=\sum_i a_i k(x_i,z). $$ For every $z$, $(Tu)(z)=\langle u,e_z\rangle_0$. By the semidefinite Cauchy–Schwarz inequality, if $u\in N$, then $(Tu)(z)=0$ for every $z$. Conversely, if $Tu$ is identically zero, then $$ \|u\|_0^2=\left\langle u,\sum_i a_i e_{x_i}\right\rangle_0 =\sum_i a_i (Tu)(x_i)=0. $$ Thus the null vectors are exactly the combinations representing the zero function. The quotient identifies precisely those combinations that represent the same function.

Worked Example: Quotienting a Constant Kernel

Let $\mathcal X$ be any nonempty set and $k(x,y)=1$ for every pair $x,y$. For $u=\sum_i a_i e_{x_i}$, write $s=\sum_i a_i$. Then $$ \|u\|_0^2=\sum_{i,j}a_i a_j=\left(\sum_i a_i\right)^2=s^2. $$ The function represented by $u$ has value $s$ at every input.

Different formal combinations with the same coefficient sum therefore represent the same constant function. In particular, any combination whose coefficients sum to zero has squared length zero and belongs to $N$. After quotienting, a class is determined just by the number $s$; the inner product of classes with sums $s$ and $t$ is $st$. This one-dimensional space is already complete, and its functions are the constant functions with norm $|s|$.

Worked Example: A Section That Is Identically Zero

Take $\mathcal X=\{0,1\}$ and $k(x,y)=xy$. This is positive definite because for any coefficients $a_i$ and inputs $x_i$, $$ \sum_{i,j}a_i a_j x_i x_j=\left(\sum_i a_i x_i\right)^2\geq 0. $$ The section $k_0$ is zero at both inputs, while $k_1$ takes values $0$ at $0$ and $1$ at $1$.

For $u=a_0e_0+a_1e_1$, the squared length is $a_1^2$, and the represented function takes values $0$ and $a_1$ at $0$ and $1$, respectively. The coefficient $a_0$ contributes neither length nor function value, so quotienting removes it. The resulting space consists of functions $f(0)=0,\ f(1)=a_1$, with norm $|a_1|$. This example shows why a positive definite kernel can have a section of zero length.

Completion and the Reproducing Property

The quotient $V/N$ has an inner product, but it need not be complete. Its completion can be constructed from Cauchy sequences: identify two Cauchy sequences if the norm of their difference tends to zero, define addition and scalar multiplication term by term, and define the inner product as the limit of inner products of sequence terms. The Cauchy–Schwarz inequality ensures these limits exist and do not depend on the chosen representatives. The resulting space is a Hilbert space containing $V/N$ as a dense subspace. Denote this completion by $\mathcal H_k$.

To regard elements of the completion as functions, first note that evaluation is bounded on the quotient. For a finite combination $u$, $$ |(Tu)(x)|=|\langle u,e_x\rangle_0| \leq \|u\|_0\|e_x\|_0 =\|u\|_0\sqrt{k(x,x)}. $$ This bound also holds for its quotient class. Thus if a sequence of quotient elements converges in norm, its values at each fixed $x$ form a Cauchy sequence of real numbers. Define the function associated with a completion element $h$ by taking these pointwise limits. The bound guarantees that this definition does not depend on the approximating sequence.

The extended evaluation bound is $|h(x)|\leq\|h\|_{\mathcal H_k}\sqrt{k(x,x)}$. Moreover, evaluation is represented by the section $k_x$, which is already an element of the quotient space and hence of its completion. Passing to the limit from finite combinations gives $$ \langle h,k_x\rangle_{\mathcal H_k}=h(x). $$ The association with functions is injective: if $h(x)=0$ for every $x$, then $h$ is orthogonal to every section and therefore to their finite span. That span is dense in the completion, so $h$ is orthogonal to itself and must be zero.

Theorem (Moore–Aronszajn): Every real-valued positive definite kernel on a set $\mathcal X$ is the reproducing kernel of a Hilbert space of functions on $\mathcal X$. The space is unique as a function space with its inner product: any two such spaces have the same functions and the same inner products.

Proof of the Moore–Aronszajn Theorem

Existence. The quotient-and-completion construction above gives a Hilbert space of functions. For each $x$, the section $k_x$ belongs to it, and the identity $\langle h,k_x\rangle_{\mathcal H_k}=h(x)$ holds for every $h\in\mathcal H_k$. Taking $h=k_y$ gives $$ \langle k_y,k_x\rangle_{\mathcal H_k}=k_y(x)=k(y,x). $$ By symmetry this is also $k(x,y)$, so $k$ is the reproducing kernel of the constructed space.

Uniqueness. Suppose $\mathcal H$ is any other Hilbert space of functions on $\mathcal X$ with reproducing kernel $k$. Its finite span of sections has the same inner products as the formal span, since the reproducing property gives $$ \left\langle \sum_i a_i k_{x_i},\sum_j b_j k_{y_j}\right\rangle_{\mathcal H} =\sum_{i,j}a_i b_j k(x_i,y_j). $$ Therefore sending each finite combination in $\mathcal H$ to the corresponding quotient class in $\mathcal H_k$ preserves inner products. It is well-defined even if a combination has multiple representations, because a difference of two such representations has squared norm zero in both spaces.

The finite span of sections is dense in $\mathcal H$. Indeed, if $g\in\mathcal H$ is orthogonal to every section, then $g(x)=\langle g,k_x\rangle_{\mathcal H}=0$ for every $x$, so $g$ is the zero function. The orthogonal complement of the span is therefore $\{0\}$, which implies its closure is all of $\mathcal H$. Since the map on the finite span preserves norms, it extends by limits to an isometry from $\mathcal H$ into $\mathcal H_k$. Its range is closed because $\mathcal H$ is complete, and it contains the dense finite span in $\mathcal H_k$; hence it is onto. Finally, for every $g\in\mathcal H$ and $x\in\mathcal X$, the extension preserves evaluation: $$ (Ug)(x)=\langle Ug,k_x\rangle_{\mathcal H_k} =\langle g,k_x\rangle_{\mathcal H}=g(x). $$ Thus the isometry identifies the same functions with the same inner products. $\square$

Common Pitfall and Why the Construction Matters

A common mistake is to assume that positive definiteness makes every nonzero formal combination have positive squared length. The definition only guarantees a nonnegative quadratic form. For the constant kernel, for example, $e_a-e_b$ is a nonzero formal combination but has squared length zero. Treating the original form as an inner product would therefore be invalid. The correction is to quotient by all zero-length combinations before completing.

The completion is also not a licence to add arbitrary functions. It adds limits in the norm determined by the kernel, and the bounded evaluation inequality ensures those limits have well-defined pointwise values. The construction thus provides a function space whose geometry is fixed by $k$, not by an additional choice. This is the foundation for using kernel sections and RKHS norms in later kernel methods.

Check Your Understanding

Use the definitions and construction to answer the following questions.

Why does a positive definite kernel lead first to a semidefinite form rather than necessarily to an inner product?
For the constant kernel, which formal combinations belong to the zero-norm subspace?
How does the inequality $|(Tu)(x)|\leq \|u\|_0\sqrt{k(x,x)}$ help define functions for elements of the completion?
Why does orthogonality to every kernel section imply that a function in an RKHS is zero?
In the kernel $k(x,y)=xy$ on $\{0,1\}$, which part of $a_0e_0+a_1e_1$ remains after quotienting, and what function does it represent?