Compactness Hypothesis, Potential Functions, and Rectifying Linear Space in Machine Learning

Abstract

Emmanuel Braverman was one of the very few thinkers who, during his extremely short life, managed to inseminate several seemingly completely different areas of science. This paper overviews one of the knowledge areas he essentially affected in the sixties years of the last century, namely, the area of Machine Learning. Later, Vladimir Vapnik proposed a more engineering-oriented name of this knowledge area – Estimation of Dependencies Based on Empirical Data. We shall consider these titles as synonyms. The aim of the paper is to briefly trace the way how three notions introduced by Braverman formed the core of the contemporary Machine Learning doctrine. These notions are: (1) compactness hypothesis, (2) potential function, and (3) the rectifying linear space, in which the former two have resulted. There will be little new in this paper. Almost all the constructions we are going to speak about had been published by numerous scientists. The novelty is, perhaps, only in that all these issues will be systematically considered together as immediate consequences of Braveman’s basic principles.

Appendix. The Proofs of Theorems

Proof of Theorem 1.

Let $\upomega^{\prime } ,\upomega^{\prime \prime } ,\upomega^{\prime \prime \prime }$ be three arbitrary objects. Due to (10), $h \ge \mathop {\sup }\limits_{{\widetilde{\upomega}^{\prime } = \widetilde{\upomega}^{\prime \prime } = \widetilde{\upomega}^{\prime \prime \prime } \in\Omega }} \left\{ {\uprho(\widetilde{\upomega}^{\prime } ,\widetilde{\upomega}^{\prime \prime \prime } )\, - } \right.$ $- \,[\uprho(\widetilde{\upomega}^{\prime } ,\widetilde{\upomega}^{\prime \prime } ) +\uprho(\widetilde{\upomega}^{\prime \prime } ,\widetilde{\upomega}^{\prime \prime \prime } )\left. ] \right\} = 0$, thus, $r(\upalpha,\upbeta)$ is nonnegative $r(\upalpha,\upbeta) =\uprho(\upalpha,\upbeta) + h \ge 0$. Since $r(\upomega^{\prime } ,\upomega^{\prime \prime } ) =\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } ) + h$, we have $r(\upomega^{\prime } ,\upomega^{\prime \prime } ) + r(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) - r(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) = \left[ {\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } ) + h} \right] +$ $\left[ {\uprho(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) + h} \right] - \left[ {\uprho(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) + h} \right] =\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } ) +\uprho(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) -\uprho(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) + h$. Here, on the force of (10), $\uprho(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) +\uprho(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) -\uprho(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) \ge - h$, and $\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } ) +\uprho(\upomega^{\prime \prime } ,\upomega^{\prime \prime \prime } ) -\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } ) + h \ge$ $- h + \,h = 0$, whence it follows that $r(\upomega^{\prime } ,\upomega^{\prime \prime } ) + r(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) - r(\upomega^{\prime } ,\upomega^{\prime \prime \prime } ) \ge 0$. ■

Proof of Theorem 2.

Let $\left\{ {\upomega_{1} , \ldots ,\upomega_{M} } \right\} \subset\Omega$ be a finite collection of objects within a distance space, $\upphi =\upomega_{k}$ be chosen as the center, and ${\mathbf{K}}_{\upphi} = {\mathbf{K}}_{{\upomega_{k} }} = \left[ {K_{{\upomega_{k} }} (\upomega_{i} ,\upomega_{j} ),\;i,j = 1, \ldots ,M} \right]$ be the matrix formed by similarity function (11). Let, further, another object be assigned as a new center ${\upvarphi}^{{\prime}} =\upomega_{l}$ and ${\mathbf{K}}_{{\upphi^{\text{'}} }} = {\mathbf{K}}_{{\upomega_{l} }} = \left[ {K_{{\upomega_{l} }} (\upomega_{i} ,\upomega_{j} ),\;i,j = 1, \ldots ,M} \right]$ be another similarity matrix. In accordance with (14),

$$ K_{{\upphi^{\text{'}} }} (\upomega^{\text{'}} ,\upomega^{{\text{''}}} ) = K_{{\upomega_{l} }} (\upomega_{i} ,\upomega_{j} ) = K_{{\upomega_{k} }} (\upomega_{i} ,\upomega_{j} ) - K_{{\upomega_{k} }} (\upomega_{i} ,\upomega_{l} ) - K_{{\upomega_{k} }} (\upomega_{j} ,\upomega_{l} ) + K_{{\upomega_{k} }} (\upomega_{l} ,\upomega_{l} ). $$

Let notation ${\mathbf{E}}_{{\upomega_{k} \to\upomega_{l} }} (M \times M)$ stand for matrices in which all the elements are zeros except the $l$ th row of units $(a_{li} = 1,\;i = 1, \ldots ,M)$ and one additional unit element $a_{kl} = 1$:

$$ \begin{aligned} {\mathbf{E}}_{{\upomega_{k} \to\upomega_{l} }} = \left( {\begin{array}{*{20}c} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right)\begin{array}{*{20}c} 1 \\ \vdots \\ k \\ \vdots \\ l \\ \vdots \\ M \\ \end{array} \hfill \\ \, \begin{array}{*{20}c} {1\,} & \cdots & {k\,} & \cdots & {\,l} & { \cdots \,} & M \\ \end{array} \hfill \\ \end{aligned} $$

It is clear that the matrices ${\mathbf{S}}_{{\upomega_{k} \to\upomega_{l} }} = {\mathbf{I}} - {\mathbf{E}}_{{\upomega_{k} \to\upomega_{l} }}$ are nondegenerate.

Let us consider two quadratic forms ${\mathbf{x}}^{T} {\mathbf{K}}_{{\upomega_{k} }} {\mathbf{x}}$ and ${\mathbf{y}}^{T} {\mathbf{K}}_{{\upomega_{l} }} {\mathbf{y}}$, ${\mathbf{x}},{\mathbf{y}} \in {\mathbf{\mathbb{R}}}^{M}$. Here

$$ {\mathbf{y}}^{T} {\mathbf{K}}_{{\upomega_{l} }} {\mathbf{y}} = {\mathbf{y}}^{T} {\mathbf{S}}_{{\upomega_{k} \to\upomega_{l} }}^{T} {\mathbf{K}}_{{\upomega_{k} }} {\mathbf{S}}_{{\upomega_{k} \to\upomega_{l} }} {\mathbf{y}} = \left( {{\mathbf{S}}_{{\upomega_{k} \to\upomega_{l} }} {\mathbf{y}}} \right)^{T} {\mathbf{K}}_{{\upomega_{k} }} \left( {{\mathbf{S}}_{{\upomega_{k} \to\upomega_{l} }} {\mathbf{y}}} \right). $$

As we see, the quadratic forms coincide after the one-to-one substitution ${\mathbf{x}} = {\mathbf{S}}_{{\upomega_{k} \to\upomega_{l} }} {\mathbf{y}}$. In accordance with Sylvester’s law of inertia for quadratic forms, the numbers of positive, negative, and zero eigenvalues of matrices ${\mathbf{K}}_{{\upomega_{k} }}$ and ${\mathbf{K}}_{{\upomega_{l} }}$ coincide, so, their signatures coincide, too. ■

Proof of Theorem 3.

Proof is based on the following lemma [54, p. 74].

Lemma 3.1.

Function $K_{\upphi} (\upomega^{\prime } ,\upomega^{\prime \prime } ) = \tilde{K}(\upomega^{\prime } ,\upomega^{\prime \prime } ) - \tilde{K}(\upomega^{\prime } ,\upphi) - \tilde{K}(\upomega^{\prime \prime } ,\upphi) + \tilde{K}(\upphi,\upphi)$, $\upomega^{\prime } ,\upomega^{\prime \prime } ,$ $\upphi \in\Omega$, is kernel if and only if $\tilde{K}(\upvartheta^{\prime } ,\upvartheta^{\prime \prime } )$, $\upvartheta^{\prime } ,\upvartheta^{\prime \prime } \in\Omega$, is conditional kernel – matrix $\left[ {\tilde{K}(\upvartheta_{k} ,\upvartheta_{l} ),\,k,l = 1, \ldots ,M} \right]$ is conditionally positive definite (30) for any finite set $\{\upvartheta_{1} , \ldots ,\upvartheta_{M} \}$.

Proof of the Theorem.

In notations of this paper, the conditionally positive kernel is defined by the proto-Euclidean metric $\tilde{K}(\upvartheta^{\prime } ,\upvartheta^{\prime \prime } ) = -\uprho^{2} (\upvartheta^{\prime } ,\upvartheta^{\prime \prime } )$. The substitution of this equality in the assertion of Lemma 3.1 yields $K_{\upphi} (\upomega^{\prime } ,\upomega^{\prime \prime } ) = -\uprho^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } ) +\uprho^{2} (\upomega^{\prime } ,\upphi) +$ $\uprho^{2} (\upomega^{\prime \prime } ,\upphi) +\uprho^{2} (\upphi,\upphi)$. Since the last summand is zero, we have $K_{\upphi} (\upomega_{i} ,\upomega_{j} ) =$ $(1/2)\left[ {\uprho^{2} (\upomega_{i} ,\upphi) + } \right.\uprho^{2} (\upomega_{j} ,\upphi)\left. { -\uprho^{2} (\upomega_{i} ,\upomega_{j} )} \right]$. ■

Proof of Theorem 4.

In accordance with (88), we have in the case (89)

$$ \begin{aligned} & \mathop {\lim }\limits_{{\upalpha \to 0}}\uprho^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } |\upalpha) = \mathop {\lim }\limits_{{\upalpha \to 0}} \frac{{\left[ {1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)} \right] -\upalpha\left[ {1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)} \right]}}{\upalpha} = \\ & \mathop {\lim }\limits_{{\upalpha \to 0}} \left\{ {\frac{{1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)}}{\upalpha} - \left[ {1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)} \right]} \right\} = \mathop {\lim }\limits_{{\upalpha \to 0}} \frac{{1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)}}{\upalpha} - \\ & \mathop {\lim }\limits_{{\upalpha \to 0}} \left[ {1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)} \right] = \mathop {\lim }\limits_{{\upalpha \to 0}} \frac{{1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)}}{\upalpha} = \frac{0}{0}, \\ \end{aligned} $$

$$ \begin{aligned} & \mathop {\lim }\limits_{{\upalpha \to 0}}\uprho^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } |\upalpha) = \mathop {\lim }\limits_{{\upalpha \to 0}} {\kern 1pt} \frac{{({\partial }/{\partial }\,\upalpha)\left[ {1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)} \right]}}{{({\partial }/{\partial }\,\upalpha)\upalpha}} = \mathop {\lim }\limits_{{\upalpha \to 0}} \frac{{\partial }}{{{\partial }\,\upalpha}}\left[ {1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)} \right]{\kern 1pt} = \\ & - \mathop {\lim }\limits_{{\upalpha \to 0}} \frac{{\partial }}{{{\partial }\,\upalpha}}\exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right) = - {\kern 1pt} \mathop {\lim }\limits_{{\upalpha \to 0}} \left[ {\left( { -\uprho^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)\exp \left( { -\upalpha \uprho ^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)} \right] =\uprho^{2} (\upomega^{\prime } ,\upomega^{\prime \prime } ). \\ \end{aligned} $$

Equality (90) immediately follows from (88). ■

Proof of Theorem 5.

Let $\upomega_{1} ,\upomega_{2} ,\upomega_{3} \in\Omega$ be three objects, $\uprho_{12} =\uprho(\upomega_{1} ,\upomega_{2} )$, $\uprho_{23} =\uprho(\upomega_{2} ,\upomega_{3} )$, $\uprho_{13} =\uprho(\upomega_{1} ,\upomega_{3} )$, and let $\uprho_{12} \le\uprho_{23}$. Under notations (88) $\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } |\upalpha) =\uprho_{\upalpha} \left( {\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } )} \right)$ and $\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } ) =\uprho$, the function $\uprho_{\upalpha} (\uprho)$ is concave and increasing $({\partial }/{\partial }\,\uprho)\,\uprho_{\upalpha} (\uprho) > 0$. Thus, the following inequalities hold:

$$ \begin{aligned} &\uprho_{\upalpha} (\uprho_{12} +\uprho_{23} ) \le\uprho_{\upalpha} (\uprho_{23} ) + \left[ {({\partial }/{\partial }\,\uprho)\uprho_{\upalpha} (\uprho)} \right]_{{\,\uprho_{23} }}\uprho_{12} ,\;\;\left[ {({\partial }/{\partial }\,\uprho)\uprho_{\upalpha} (\uprho)} \right]_{{\,\uprho_{23} }} \le \left[ {({\partial }/{\partial }\,\uprho)\uprho_{\upalpha} (\uprho)} \right]_{{\,\uprho_{12} }} , \\ & \left[ {({\partial }/{\partial }\,\uprho)\uprho_{\upalpha} (\uprho)} \right]_{{\,\uprho_{12} }}\uprho_{12} \le\uprho_{\upalpha} (\uprho_{12} ). \\ \end{aligned} $$

Here all the derivatives are positive, so, $\uprho_{\upalpha} (\uprho_{12} +\uprho_{23} ) \le\uprho_{\upalpha} (\uprho_{12} ) +\uprho_{\upalpha} (\uprho_{23} )$. Since the original metric satisfied the triangle inequality $\uprho_{13} \le\uprho_{12} +\uprho_{23}$, we have $\uprho_{\upalpha} (\uprho_{13} )\, \le$ $\uprho_{\upalpha} (\uprho_{12} ) +\uprho_{\upalpha} (\uprho_{23} )$. ■

Proof of Theorem 6.

It is enough to prove that for any finite set of objects $\left\{ {\upomega_{1} , \ldots ,\upomega_{n} } \right\} \subset\Omega$ and any center $\upphi \subset\Omega$ the matrix

$$ {\mathbf{K}}_{\upphi} (\upalpha) = \frac{1}{2}\left[ {\uprho^{2} (\upomega_{i} ,\upphi|\upalpha) +\uprho^{2} (\upomega_{j} ,\upphi|\upalpha) -\uprho^{2} (\upomega_{i} ,\upomega_{j} |\upalpha),\;i,j = 1, \ldots ,n} \right] $$

is positive definite if matrix

$$ {\mathbf{K}}_{\upphi} = \frac{1}{2}\left[ {\uprho^{2} (\upomega_{i} ,\upphi) +\uprho^{2} (\upomega_{j} ,\upphi) -\uprho^{2} (\upomega_{i} ,\upomega_{j} ),\;i,j = 1, \ldots ,n} \right] $$

(103)

is positive definite.

In accordance with Lemma 3.1 (proof of Theorem 3), it is necessary and sufficient for positive definiteness of matrix (103) that matrix

$$ {\mathbf{B}}(\upalpha) = \left[ { -\uprho^{2} (\upomega_{i} ,\upomega_{j} |\upalpha),\;i,j = 1, \ldots ,n} \right] $$

would be conditionally positive definite.

At the same time, due to (85), $\uprho^{2} (\upomega_{i} ,\upomega_{j} |\upalpha){ \propto }1 - \exp \left( { -\upalpha \uprho ^{2} (\upomega_{i} ,\upomega_{j} )} \right)$, so,

$$ {\mathbf{B}}(\upalpha){ \propto }{\mathbf{C}}(\upalpha) - {\mathbf{D}},{\mathbf{D}} = \left( {\begin{array}{*{20}c} 1 & 1 & \cdots & 1 \\ 1 & 1 & \cdots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & 1 \\ \end{array} } \right) = {\mathbf{11}}^{\text{T}} , $$

(104)

$$ {\mathbf{C}}(\upalpha) = \left( {\begin{array}{*{20}c} {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{1} ,\upomega_{1} )} \right)} & {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{1} ,\upomega_{2} )} \right)} & \cdots & {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{1} ,\upomega_{n} )} \right)} \\ {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{2} ,\upomega_{1} )} \right)} & {\exp \left( { -\upalpha \uprho ^{2} (\omega_{2} ,\omega_{2} )} \right)} & \cdots & {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{2} ,\upomega_{n} )} \right)} \\ {} & \vdots & \ddots & \vdots \\ {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{n} ,\upomega_{1} )} \right)} & {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{n} ,\upomega_{2} )} \right)} & \cdots & {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{n} ,\upomega_{n} )} \right)} \\ \end{array} } \right). $$

(105)

Here matrix ${\mathbf{C}}(\upalpha)$ is always positive definite for any proto-Euclidean metric $\uprho(\upomega^{\prime } ,\upomega^{\prime \prime } )$ (103) on the force of Mercer’s theorem (Sect. 1.4), i.e., ${\varvec{\upbeta}}^{\text{T}} {\mathbf{C}}(\upalpha){\varvec{\upbeta}}\,{\mathbf{ > }}0$ if ${\varvec{\upbeta}} \ne {\mathbf{0}} \in {\mathbf{\mathbb{R}}}^{n}$.

Let us consider the quadratic function $q({\varvec{\upbeta}}|\upalpha) = {\varvec{\upbeta}}^{\text{T}} {\mathbf{B}}(\upalpha){\varvec{\upbeta}} = {\varvec{\upbeta}}^{\text{T}} \left( {{\mathbf{C}}(\upalpha) - {\mathbf{D}}} \right){\varvec{\upbeta}} =$ ${\varvec{\upbeta}}^{\text{T}} \left( {{\mathbf{C}}(\upalpha) - {\mathbf{11}}^{\text{T}} } \right){\varvec{\upbeta}} = {\varvec{\upbeta}}^{\text{T}} {\mathbf{C}}(\upalpha){\varvec{\upbeta}} - ({\varvec{\upbeta}}^{\text{T}} {\mathbf{1}})({\mathbf{1}}^{\text{T}} {\varvec{\upbeta}})$ on the hyperplane ${\mathbf{1}}^{\text{T}} {\varvec{\upbeta}} = 0$. It is clear that $\left. {q({\varvec{\upbeta}}|\upalpha)} \right|_{{{\mathbf{1}}^{\text{T}} {\varvec{\upbeta}} = 0}} = {\varvec{\upbeta}}^{\text{T}} {\mathbf{C}}(\upalpha){\varvec{\upbeta}}\,{\mathbf{ > }}0$. Thus, matrix ${\mathbf{B}}(\upalpha)$ is conditionally positive definite. ■

Proof of Theorem 7.

Proof is facilitated by the following two Lemmas.

Lemma 7.1.

Matrix ${\mathbf{B}}$ has the main eigenvalues $\uplambda_{1} = \ldots =\uplambda_{n - 1} = 1$ of multiplicity $n - 1$, the last one $\uplambda_{n} {\kern 1pt} = \, - \,(n\, - \,1)$ of multiplicity 1, the main eigenvectors ${\mathbf{z}}_{i} ,i = 1, \ldots ,n - 1$ with zero sums of elements ${\mathbf{1}}^{\text{T}} {\mathbf{z}}_{i} = 0$, $i = 1, \ldots ,n$, and the last eigenvector ${\mathbf{z}}_{n} = {\mathbf{1}} \in {\mathbf{\mathbb{R}}}^{n} .$

$$ {\mathbf{B}} = \left( {\begin{array}{*{20}c} 0 & { - {\kern 1pt} 1} & \cdots & { - {\kern 1pt} 1} \\ { - {\kern 1pt} 1} & 0 & \cdots & { - {\kern 1pt} 1} \\ \cdots & \cdots & \ddots & \cdots \\ { - {\kern 1pt} 1} & { - {\kern 1pt} 1} & \cdots & 0 \\ \end{array} } \right) $$

(106)

Indeed, the main eigenvalues and eigenvectors meet the equalities

$$ \left( {\begin{array}{*{20}c} 0 & { - 1} & \cdots & { - 1} \\ { - 1} & 0 & \cdots & { - 1} \\ \cdots & \cdots & \ddots & \cdots \\ { - 1} & { - 1} & \cdots & 0 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {z_{1} } \\ {z_{2} } \\ \vdots \\ {z_{n} } \\ \end{array} } \right) = \left( {\begin{array}{*{20}c} { - \sum\nolimits_{j = 1,j \ne 1}^{n} {z_{j} } } \\ { - \sum\nolimits_{j = 1,j \ne 2}^{n} {z_{j} } } \\ \vdots \\ { - \sum\nolimits_{j = 1,j \ne n}^{n} {z_{j} } } \\ \end{array} } \right) = \left( {\begin{array}{*{20}c} {z_{1} } \\ {z_{2} } \\ \vdots \\ {z_{n} } \\ \end{array} } \right),\;\;\left( {\begin{array}{*{20}c} {z_{1} = - \sum\nolimits_{j = 1,j \ne 1}^{n} {z_{j} } = - \sum\nolimits_{j = 1}^{n} {z_{j} } + z_{1} } \\ {z_{2} = - \sum\nolimits_{j = 1,j \ne 2}^{n} {z_{j} } = - \sum\nolimits_{j = 1}^{n} {z_{j} } + z_{2} } \\ \vdots \\ {z_{n} = - \sum\nolimits_{j = 1,j \ne n}^{n} {z_{j} } = - \sum\nolimits_{j = 1}^{n} {z_{j} } + z_{n} } \\ \end{array} } \right), $$

$$ \sum\limits_{l = 1}^{n} {z_{l} } = - n\sum\limits_{j = 1}^{n} {z_{j} } + \sum\limits_{l = 1}^{n} {z_{l} } ,\;\;n\sum\limits_{j = 1}^{n} {z_{l} } = \sum\limits_{l = 1}^{n} {z_{l} } - \sum\limits_{l = 1}^{n} {z_{l} } = 0,{\text{ i}}.{\text{e}}.,{\mathbf{1}}^{\text{T}} {\mathbf{z}}_{i} = 0,i = 1, \ldots ,n. $$

The respective equalities for the last eigenvalue and eigenvector have the form

$$ \left( {\begin{array}{*{20}c} 0 & { - {\kern 1pt} 1} & \cdots & { - {\kern 1pt} 1} \\ { - {\kern 1pt} 1} & 0 & \cdots & { - {\kern 1pt} 1} \\ \cdots & \cdots & \ddots & \cdots \\ { - {\kern 1pt} 1} & { - {\kern 1pt} 1} & \cdots & 0 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {z_{1} } \\ {z_{2} } \\ \vdots \\ {z_{n} } \\ \end{array} } \right) = - (n - 1)\left( {\begin{array}{*{20}c} {z_{1} } \\ {z_{2} } \\ \vdots \\ {z_{n} } \\ \end{array} } \right),\;z_{1} = z_{2} = \ldots = z_{n} ,\;{\text{i}}.{\text{e}}.\;{\mathbf{z}}_{n} = {\mathbf{1}}\, \in \,{\mathbf{\mathbb{R}}}^{n} ,{\text{QED}}. $$

Lemma 7.2.

Quadratic form $q({\varvec{\upbeta}}) = {\varvec{\upbeta}}^{\text{T}} {\mathbf{B}}\,{\varvec{\upbeta}}$ is positive $q({\varvec{\upbeta}}) > 0$, when ${\mathbf{1}}^{\text{T}} {\varvec{\upbeta}} = 0$ and ${\varvec{\upbeta}} \ne {\mathbf{0}} \in {\mathbf{\mathbb{R}}}^{n}$, hence, matrix ${\mathbf{B}}$ (106) is conditionally positive definite.

Indeed, due to Lemma 7.1, ${\mathbf{B}} = \sum\nolimits_{i = 1}^{n} {\uplambda_{i} {\mathbf{z}}_{i} {\mathbf{z}}_{i}^{\text{T}} } = \sum\nolimits_{i = 1}^{n - 1} {{\mathbf{z}}_{i} {\mathbf{z}}_{i}^{\text{T}} } - (n - 1){\mathbf{z}}_{n} {\mathbf{z}}_{n}^{\text{T}} =$$\sum\nolimits_{i = 1}^{n - 1} {{\mathbf{z}}_{i} {\mathbf{z}}_{i}^{\text{T}} } - (n - 1){\mathbf{11}}^{\text{T}}$. Let us consider the quadratic form $q({\varvec{\upbeta}}) = {\varvec{\upbeta}}^{\text{T}} {\mathbf{B}}\,{\varvec{\upbeta}} = \sum\nolimits_{i = 1}^{n - 1} {{\varvec{\upbeta}}^{\text{T}} {\mathbf{z}}_{i} {\mathbf{z}}_{i}^{\text{T}} {\varvec{\upbeta}}} - (n - 1){\varvec{\upbeta}}^{\text{T}} {\mathbf{11}}^{\text{T}} {\varvec{\upbeta}}$. On the hyperplane ${\mathbf{1}}^{\text{T}} {\varvec{\upbeta}} = 0$, it has the values $\left. {q({\varvec{\upbeta}})} \right|_{{{\mathbf{1}}^{\text{T}} {\varvec{\upbeta}} = 0}} = {\varvec{\upbeta}}^{\text{T}} {\mathbf{B}}\,{\varvec{\upbeta}} = {\varvec{\upbeta}}^{\text{T}} {\mathbf{B}}\,{\varvec{\upbeta}}$. Here matrix ${\mathbf{B}} = \sum\nolimits_{i = 1}^{n - 1} {{\mathbf{z}}_{i} {\mathbf{z}}_{i}^{\text{T}} }$ is positive definite, i.e., $\left. {q({\varvec{\upbeta}})} \right|_{{{\mathbf{1}}^{\text{T}} {\varvec{\upbeta}} = 0}} > 0$, ${\varvec{\upbeta}} \ne {\mathbf{0}} \in {\mathbf{\mathbb{R}}}^{n}$, QED.

Now we are ready to prove Theorem 7.

We have to prove that matrix ${\mathbf{B}}(\upalpha)$ is conditionally positive definite if $\upalpha$ is large enough. Let us consider the quadratic form

$$ {\mathbf{B}}(\upalpha) = \left( {\begin{array}{*{20}c} 0 & { -\uprho^{2} (\upomega_{1} ,\upomega_{2} |\upalpha)} & \cdots & { -\uprho^{2} (\upomega_{1} ,\upomega_{n} |\upalpha)} \\ { -\uprho^{2} (\upomega_{2} ,\upomega_{1} |\upalpha)} & 0 & \cdots & { -\uprho^{2} (\upomega_{2} ,\upomega_{n} |\upalpha)} \\ \cdots & \cdots & \ddots & \cdots \\ { -\uprho^{2} (\upomega_{n} ,\upomega_{1} |\upalpha)} & { -\uprho^{2} (\upomega_{n} ,\upomega_{2} |\upalpha)} & \cdots & 0 \\ \end{array} } \right) $$

$q({\mathbf{\beta |}}\upalpha) = {\varvec{\upbeta}}^{\text{T}} {\mathbf{B}}(\upalpha){\varvec{\upbeta}}$ on the intersection of the hyperplane ${\mathbf{1}}^{\text{T}} {\varvec{\upbeta}} = 0$ and hypersphere ${\varvec{\upbeta}}^{\text{T}} \,{{\varvec{\upbeta}} = 1}$. Since $q({\varvec{\upbeta}}\,{\mathbf{|}}\,\upalpha)$ is continuous function of $\upalpha$, $\mathop {\lim }\limits_{{\upalpha \to \infty }} {\mathbf{B}}(\upalpha) = {\mathbf{B}}$ and, so, $\mathop {\lim }\limits_{{\upalpha \to \infty }} q({\varvec{\upbeta}}\,{\mathbf{|}}\,\upalpha) =$ $\mathop {\lim }\limits_{{\upalpha \to {\infty }}} {\varvec{\upbeta}}^{\text{T}} {\mathbf{B}}(\upalpha){\varvec{\upbeta}} = {\varvec{\upbeta}}^{\text{T}} {\mathbf{B}}\,{\varvec{\upbeta}}\,{\mathbf{ = }}q({\varvec{\upbeta}}).$ In accordance with Lemma 7.1, matrix ${\mathbf{B}}$ (106) is conditionally positive definite, hence, due to Lemma 7.2, there exists $\upalpha_{0}$, such that $\left. {q({\mathbf{\beta |}}\upalpha)} \right|_{{{\mathbf{1}}^{\text{T}} {\varvec{\upbeta}} = 0}} > 0$, ${\varvec{\upbeta}} \ne {\mathbf{0}} \in {\mathbf{\mathbb{R}}}^{n}$, i.e., ${\mathbf{B}}(\upalpha)$ is conditionally positive definite if $\upalpha >\upalpha_{0}$. ■

Proof of Theorem 8.

Let the training assembly consist of four objects $N = 4$:

$$ \begin{aligned} &\uprho(\upomega_{1} ,\upomega_{2} ) =\uprho(\upomega_{3} ,\upomega_{4} ) = \sqrt 2 ,\;\uprho(\upomega_{1} ,\upomega_{3} ) =\uprho(\upomega_{1} ,\upomega_{4} ) =\uprho(\upomega_{2} ,\upomega_{3} ) =\uprho(\upomega_{2} ,\upomega_{4} ) = 1, \\ & y_{1} = y_{2} = 1,\;y_{3} = y_{4} = - 1. \\ \end{aligned} $$

(107)

Let us try to find to find a decision rule (68) that correctly classifies all the objects:

$$ \left\{ \begin{aligned} \underbrace {{\left( { -\uprho^{2} (\upomega_{1} ,\upomega_{1} )} \right)}}_{0}a_{1} {\kern 1pt} + {\kern 1pt} \underbrace {{\left( { -\uprho^{2} (\upomega_{2} ,\upomega_{1} )} \right)}}_{ - 2}a_{2} {\kern 1pt} + {\kern 1pt} \underbrace {{\left( { -\uprho^{2} (\upomega_{3} ,\upomega_{1} )} \right)}}_{ - 1}a_{3} + \underbrace {{\left( { -\uprho^{2} (\upomega_{4} ,\upomega_{1} )} \right)}}_{ - 1}a_{4} + b > 0, \hfill \\ \underbrace {{\left( { -\uprho^{2} (\upomega_{1} ,\upomega_{2} )} \right)}}_{ - 2}a_{1} + \underbrace {{\left( { -\uprho^{2} (\upomega_{2} ,\upomega_{2} )} \right)}}_{0}a_{2} + \underbrace {{\left( { -\uprho^{2} (\upomega_{3} ,\upomega_{2} )} \right)}}_{ - 1}a_{3} + \underbrace {{\left( { -\uprho^{2} (\upomega_{4} ,\upomega_{2} )} \right)}}_{ - 1}a_{4} + b > 0, \hfill \\ \underbrace {{\left( { -\uprho^{2} (\upomega_{1} ,\upomega_{3} )} \right)}}_{ - 1}a_{1} + \underbrace {{\left( { -\uprho^{2} (\upomega_{2} ,\upomega_{3} )} \right)}}_{ - 1}a_{2} + \underbrace {{\left( { -\uprho^{2} (\upomega_{3} ,\upomega_{3} )} \right)}}_{0}a_{3} + \underbrace {{\left( { -\uprho^{2} (\upomega_{4} ,\upomega_{3} )} \right)}}_{ - 2}a_{4} + b < 0, \hfill \\ \underbrace {{\left( { -\uprho^{2} (\upomega_{1} ,\upomega_{4} )} \right)}}_{ - 1}a_{1} + \underbrace {{\left( { -\uprho^{2} (\upomega_{2} ,\upomega_{4} )} \right)}}_{ - 1}a_{2} {\kern 1pt} + {\kern 1pt} \underbrace {{\left( { -\uprho^{2} (\upomega_{3} ,\upomega_{4} )} \right)}}_{ - 2}a_{3} + \underbrace {{\left( { -\uprho^{2} (\upomega_{4} ,\upomega_{4} )} \right)}}_{0}a_{4} + b < 0. \hfill \\ \end{aligned} \right. $$

(108)

Then, the numbers $(a_{1} ,a_{2} ,a_{3} ,a_{4} ,b)$ have to meet the equalities

$$ \left\{ \begin{aligned} - 2a_{2} - a_{3} - a_{4} + b > 0, \hfill \\ - 2a_{1} - a_{3} - a_{4} + b > 0, \hfill \\ - a_{1} - a_{2} - 2a_{4} + b < 0, \hfill \\ - a_{1} - a_{2} - 2a_{3} + b < 0, \hfill \\ \end{aligned} \right. \;{\text{or,}}\;{\text{what}}\;{\text{is}}\,{\text{equivalent,}}\;\;\left\{ \begin{aligned} \left\{ \begin{aligned} - 2a_{2} - a_{3} - a_{4} + b > 0, \hfill \\ - 2a_{1} - a_{3} - a_{4} + b > 0, \hfill \\ \end{aligned} \right. \hfill \\ \left\{ \begin{aligned} a_{1} + a_{2} + 2a_{4} - b > 0, \hfill \\ a_{1} + a_{2} + 2a_{3} - b > 0. \hfill \\ \end{aligned} \right. \hfill \\ \end{aligned} \right. $$

(109)

Adding the left and right parts of the first two inequalities results in the inequality $- (a_{1} + a_{2} ) -$$a_{3} - a_{4} + b > 0$, i.e. $a_{1} + a_{2} + a_{3} + a_{4} - b < 0$, and the same operation applied to the second two inequalities gives $a_{1} + a_{2} + a_{3} + a_{4} - b > 0$. It is clear that these two pairs of inequalities are incompatible, hence, the inequalities (109) are incompatible, too. Thus, the decision rule of kind (69), which would correctly classify (108) the assembly (107), does not exist. ■

Proof of Theorem 9.

Let us consider an arbitrary object of the training set $\upomega_{j} \in\Omega$. In accordance with (69), the decision rule (101) can be represented as

$$ d(\upomega_{j} |a_{1} , \ldots ,a_{N} ,b,\upalpha) = \frac{{1 +\upalpha}}{\upalpha}\left[ {a_{j} + \sum\limits_{i = 1,\;i \ne j}^{n} {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{j} ,\upomega_{i} )} \right)a_{i} } } \right] + b. $$

Indeed,

$$ \begin{aligned} & \sum\limits_{i = 1}^{n} {\left( { -\uprho^{2} (\upomega_{j} ,\upomega_{i} |\upalpha)} \right)a_{i} } + b = \frac{{1 +\upalpha}}{\upalpha}\sum\limits_{i = 1}^{n} {\left[ {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{j} ,\upomega_{i} )} \right) - 1} \right]a_{i} } + b = \\ & \quad \quad \quad \frac{1 + \alpha }{\alpha }\sum\limits_{i = 1}^{n} {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{j} ,\upomega_{i} )} \right)a_{i} } - \frac{{1 +\upalpha}}{\upalpha}\underbrace {{\sum\limits_{i = 1}^{n} {a_{i} } }}_{ = 0} + b = \\ & \quad \quad \quad \quad \quad \quad \quad \quad \frac{{1 +\upalpha}}{\upalpha}\underbrace {{\exp \left( { -\upalpha \uprho ^{2} (\upomega_{j} ,\upomega_{j} )} \right)}}_{ = 1}a_{j} + \frac{{1 +\upalpha}}{\upalpha}\sum\limits_{i = 1,\;i \ne j}^{n} {\exp \left( { -\upalpha \uprho ^{2} (\upomega_{j} ,\upomega_{i} )} \right)a_{i} } + b. \\ \end{aligned} $$

Since $\mathop {\lim }\limits_{{\upalpha \to {\infty }}} \left[ {(1 +\upalpha)/\upalpha} \right] = 1$, we have

$$ \mathop {\lim }\limits_{{\upalpha \to {\infty }}} d(\upomega_{j} |a_{1} , \ldots ,a_{N} ,b,\upalpha) = a_{j} + \sum\limits_{i = 1,\;i \ne j}^{n} {\underbrace {{\mathop {\lim }\limits_{{\upalpha \to \infty }} \exp \left( { -\upalpha \uprho ^{2} (\upomega_{j} ,\upomega_{i} )} \right)}}_{ = 0}a_{i} } + b = a_{j} + b. $$

Let $(a_{j} ,\;j = 1, \ldots ,N,b)$ be the parameter vector such that $a_{j} > 0$ if $y_{j} = 1$, $a_{j} < 0$ if $y_{j} = - 1$, and $b = 0$. Then

$$ \mathop {\lim }\limits_{{\upalpha \to {\infty }}} d(\upomega_{j} |a_{1} , \ldots ,a_{N} ,b,\upalpha) = a_{j} \left\{ {\begin{array}{*{20}l} { > 0,\;y_{j} = 1,} \hfill \\ { < 0,\;y_{j} = - 1,} \hfill \\ \end{array} } \right. $$

i.e., parameter vector $(a_{j} ,j{\kern 1pt} = \,1, \ldots ,N,b)$ correctly separates the entire training set. ■