Building Kernels from Distances

From Patient Distances to Kernels

A distance matrix summarizes how far apart patients are in an omics representation. A kernel matrix instead records pairwise similarities in a form that can be used by kernel methods. A common conversion assigns large similarity to close pairs and small similarity to distant pairs. The key statistical question is not only how to choose the conversion, but whether the resulting matrix is positive semidefinite (PSD). PSD is what lets the matrix act as a valid Gram matrix, representing inner products between feature vectors.

The earlier material on kernel matrices establishes the role of a PSD matrix as a patient-similarity representation. Here the focus is the condition on the distances that makes a Gaussian conversion PSD. In particular, an ordinary metric distance is not, by itself, enough.

Definition: For $n$ patients, let $\Delta$ be a symmetric matrix with $\Delta_{ii}=0$ and $\Delta_{ij}\geq 0$. Its entries represent squared dissimilarities, so that $\Delta_{ij}=d_{ij}^{\,2}$ when a distance $d_{ij}$ is available. For a scale parameter $\gamma>0$, the Gaussian distance kernel is the matrix $K_\gamma$ with entries $$ (K_\gamma)_{ij}=\exp(-\gamma\Delta_{ij}). $$ A symmetric matrix $K$ is positive semidefinite if $a^\mathsf{T}Ka\geq 0$ for every real vector $a$. The parameter $\gamma$ has units reciprocal to those of $\Delta_{ij}$, making the exponent dimensionless.

Since $\Delta_{ii}=0$, every diagonal entry of $K_\gamma$ is one. For $\gamma>0$, larger squared distances yield smaller similarities. The scale controls how quickly that decrease occurs: a large $\gamma$ makes similarities decay rapidly, while a small $\gamma$ gives distant patients more similar kernel values. The Gaussian formula always produces numerical entries between zero and one, but that fact alone does not ensure the matrix is PSD.

The Distance Condition Behind Positive Semidefiniteness

The relevant distance condition is called conditional negative definiteness. The word “conditional” refers to the restriction on the vectors used to test the matrix; it does not mean a conditional probability.

Definition: A symmetric, zero-diagonal matrix $\Delta$ is conditionally negative definite (CND) if $$ \sum_{i=1}^{n}\sum_{j=1}^{n} c_i c_j\Delta_{ij}\leq 0 \quad\text{for every }c\in\mathbb{R}^n \text{ such that }\sum_{i=1}^{n}c_i=0. $$ A matrix of squared Euclidean distances is CND. Conversely, a symmetric, zero-diagonal CND matrix can be represented as squared Euclidean distances, possibly in a higher-dimensional space.

The zero-sum restriction matters. A distance matrix is not usually negative semidefinite for every vector $c$; CND asks for nonpositive quadratic forms only in directions whose entries sum to zero. This condition precisely characterizes whether a squared-distance matrix can be realized by points in a Euclidean feature space.

Worked Example: Squared Distances Along a One-Dimensional Profile

Suppose three hypothetical patients have standardized profile values $x_1=0$, $x_2=1$, and $x_3=2$. Their squared Euclidean distances are $$ \Delta= \begin{pmatrix} 0&1&4\\ 1&0&1\\ 4&1&0 \end{pmatrix}. $$ Take $\gamma=0.5$ per squared profile unit. The Gaussian kernel is $$ K_{0.5}= \begin{pmatrix} 1&e^{-0.5}&e^{-2}\\ e^{-0.5}&1&e^{-0.5}\\ e^{-2}&e^{-0.5}&1 \end{pmatrix} \approx \begin{pmatrix} 1&0.6065&0.1353\\ 0.6065&1&0.6065\\ 0.1353&0.6065&1 \end{pmatrix}. $$

For this symmetric matrix, the leading principal minors are $1$, $1-(0.6065)^2\approx0.6321$, and the determinant. Writing $a=e^{-0.5}$ and $b=e^{-2}$, the determinant is $1-2a^2+2a^2b-b^2$, which evaluates to approximately $0.3455$. All three leading principal minors are positive, so this particular matrix is positive definite, and therefore PSD. The calculation is consistent with the general result for squared Euclidean distances.

The entries are similarities, not distances: patients 1 and 3 have squared distance 4 and kernel value about 0.1353, whereas adjacent patients have squared distance 1 and kernel value about 0.6065. The stated scale is in reciprocal squared profile units, so the exponent has no units.

Why Euclidean Squared Distances Give PSD Kernels

Two facts explain the guarantee. First, squared Euclidean distances are CND. Second, applying the exponential transformation to a CND matrix produces a PSD matrix for every positive scale. The following argument gives the essential justification and also explains the centered-matrix diagnostic.

Verify the CND property for Euclidean points.
If $\Delta_{ij}=\lVert x_i-x_j\rVert^2$ and $\sum_i c_i=0$, expanding the squared distances gives $\sum_{i,j}c_ic_j\Delta_{ij}=-2\left\lVert\sum_i c_ix_i\right\rVert^2\leq0$. Thus $\Delta$ is CND.

Recover a Euclidean representation from a CND matrix.
Let $H=I-\mathbf{1}\mathbf{1}^\mathsf{T}/n$, where $\mathbf{1}$ is the vector of $n$ ones, and define $B=-\tfrac12H\Delta H$. For every vector $z$, $Hz$ sums to zero, so $z^\mathsf{T}Bz=-\tfrac12(Hz)^\mathsf{T}\Delta(Hz)\geq0$. Hence $B$ is PSD and can be factored as a Gram matrix. Its rows can be taken as coordinates $x_i$, for which $\Delta_{ij}=\lVert x_i-x_j\rVert^2$.

Apply the Gaussian transformation.
For Euclidean coordinates, $K_{ij}=\exp(-\gamma\lVert x_i-x_j\rVert^2)=\exp(-\gamma\lVert x_i\rVert^2)\exp(-\gamma\lVert x_j\rVert^2)\exp(2\gamma x_i^\mathsf{T}x_j)$. The matrix with entries $x_i^\mathsf{T}x_j$ is a Gram matrix. Its elementwise powers are PSD by the Schur product theorem; the power series for the last exponential is a sum of those matrices with nonnegative coefficients. Multiplication by the positive diagonal factors preserves PSD. Therefore $K_\gamma$ is PSD.

Together these steps give the standard characterization: for a symmetric zero-diagonal matrix $\Delta$, $\Delta$ is CND if and only if $K_\gamma$, with entries $\exp(-\gamma\Delta_{ij})$, is PSD for every $\gamma>0$. Necessity can also be seen directly: if $K_\gamma$ is PSD for every positive $\gamma$, then for any $c$ with $\sum_i c_i=0$, expansion at $\gamma=0$ gives $c^\mathsf{T}K_\gamma c=-\gamma c^\mathsf{T}\Delta c+O(\gamma^2)$. Nonnegativity for arbitrarily small positive $\gamma$ requires $c^\mathsf{T}\Delta c\leq0$. A distance matrix that fails the CND condition may still yield a PSD matrix at a particular value of $\gamma$; failure of CND rules out the guarantee for all positive scales, not necessarily every single scale.

Worked Example: A Two-Dimensional Euclidean Omics Representation

Consider three hypothetical patient profiles represented by $x_1=(0,0)$, $x_2=(1,0)$, and $x_3=(0,2)$. Their squared Euclidean distances are 1, 4, and 5 for pairs $(1,2)$, $(1,3)$, and $(2,3)$, respectively. With $\gamma=1$ per squared profile unit, $$ K_1= \begin{pmatrix} 1&e^{-1}&e^{-4}\\ e^{-1}&1&e^{-5}\\ e^{-4}&e^{-5}&1 \end{pmatrix} \approx \begin{pmatrix} 1&0.3679&0.01832\\ 0.3679&1&0.006738\\ 0.01832&0.006738&1 \end{pmatrix}. $$

For any real coefficients $a_1,a_2,a_3$, the quadratic form $a^\mathsf{T}K_1a$ is nonnegative by the Euclidean Gaussian-kernel argument above. Thus the matrix is PSD without needing to infer PSD merely from its positive entries. As a direct distance check, take $c=(1,-1,0)$, whose entries sum to zero. Then $c^\mathsf{T}\Delta c=-2\Delta_{12}=-2\leq0$, as required by CND. This one check is illustrative, not a complete numerical verification of CND; the Euclidean coordinate construction supplies the full guarantee.

The third patient is farther from patient 2 than patient 1 is, so the corresponding kernel value $e^{-5}\approx0.006738$ is smaller than $e^{-1}\approx0.3679$. The values are dimensionless similarities, while the scale is reciprocal to the squared-profile units.

A Metric Need Not Produce a Valid Kernel

A distance may satisfy nonnegativity, symmetry, identity of indiscernibles, and the triangle inequality while its squared-distance matrix is not CND. Consequently, applying the Gaussian formula to a metric is not an automatic route to a PSD kernel.

Worked Example: A Metric Whose Gaussian Matrix Is Not PSD

Take four hypothetical patients arranged on a cycle, with shortest-path distances one between neighbors and two between opposite patients. This is a metric: in particular, the largest distance 2 does not exceed the sum of the two edges on a shortest connecting path. The squared-distance matrix is $$ \Delta= \begin{pmatrix} 0&1&4&1\\ 1&0&1&4\\ 4&1&0&1\\ 1&4&1&0 \end{pmatrix}. $$ For $c=(1,-1,1,-1)^\mathsf{T}$, the entries sum to zero. The four neighboring pairs contribute $-8$ in total to $c^\mathsf{T}\Delta c$, while the two opposite pairs contribute $16$, giving $c^\mathsf{T}\Delta c=8>0$. Therefore $\Delta$ is not CND.

Set $\gamma=0.1$ per squared path-length unit. The Gaussian kernel matrix has diagonal 1, neighbor entries $a=e^{-0.1}\approx0.9048$, and opposite-pair entries $b=e^{-0.4}\approx0.6703$. The vector $c$ above is an eigenvector, with eigenvalue $1-2a+b\approx1-1.8097+0.6703=-0.1394$. Since this eigenvalue is negative, the kernel matrix is not PSD. The construction produces similarities in $[0,1]$, and the input is a genuine metric; neither property prevents this failure.

Diagnostics, Alternatives, and Limitations

For a proposed distance-derived kernel, use checks that address both the input distances and the resulting matrix. A small negative eigenvalue may arise from floating-point error; a clearly negative eigenvalue indicates a substantive failure of PSD for that scale.

Inspect the input. Confirm symmetry, a zero diagonal, nonnegative entries, and consistent units. If $\Delta$ is claimed to contain squared distances, verify that the entries really are squared values rather than unsquared distances.
Check the centered matrix. Compute $B=-\tfrac12H\Delta H$. It should be PSD, up to numerical tolerance, for squared Euclidean distances. A materially negative eigenvalue means the distances do not have a Euclidean squared-distance representation.
Check the actual kernel. Compute the smallest eigenvalue of $K_\gamma$ at the chosen scale. The CND condition guarantees PSD for all positive scales; direct checking addresses the particular matrix and can reveal numerical or implementation errors.
Assess scale sensitivity. Extremely small $\gamma$ makes most entries close to one, while very large $\gamma$ makes distinct-patient entries close to zero. Either extreme can make the similarities uninformative, even when PSD holds.

The main alternatives depend on what the distance represents. If profiles have meaningful coordinates and Euclidean distance is appropriate, use their squared Euclidean distances; the PSD guarantee follows directly. If a scientifically motivated dissimilarity is not known to be Euclidean, test whether it is CND and check the resulting kernel at the scale of interest. An arbitrary patient-similarity or affinity matrix is another object: it should not be treated as a PSD kernel unless its PSD property has been established. Altering a non-PSD matrix, for example by replacing negative eigenvalues, can produce a PSD matrix, but it changes the original similarities and requires justification rather than being a harmless numerical correction.

The Gaussian transformation also has substantive limitations. It converts the chosen distance geometry rather than validating it: scaling, feature selection, missing-data handling, and the influence of outliers can all alter the patient distances and therefore the kernel. A PSD guarantee does not establish that the representation is biologically meaningful, nor that the similarities are associated with a clinical outcome. It is a mathematical property of the matrix, not evidence of causation or predictive performance.

Key takeaway: For squared distances, the decisive guarantee is conditional negative definiteness. Squared Euclidean distances satisfy it, so their Gaussian kernels are PSD for every positive scale. A metric or a matrix of plausible-looking similarities alone does not establish that guarantee.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

If squared distances are measured in standardized-profile units squared, what are the units of $\gamma$ in $\exp(-\gamma\Delta_{ij})$?
Why does a squared Euclidean distance matrix satisfy the CND inequality when the coefficients sum to zero?
Does failure of CND prove that a Gaussian matrix is non-PSD at every possible scale? Explain.
A symmetric, zero-diagonal distance matrix yields a centered matrix $B=-\tfrac12H\Delta H$ with a substantially negative eigenvalue. What conclusion follows about a squared Euclidean representation?
Why is “all Gaussian similarities are between zero and one” not a sufficient PSD diagnostic?

Solutions. (1) $\gamma$ has reciprocal squared-profile units, so $\gamma\Delta_{ij}$ is dimensionless. (2) For $\sum_i c_i=0$, expansion gives $\sum_{i,j}c_ic_j\lVert x_i-x_j\rVert^2=-2\lVert\sum_i c_ix_i\rVert^2\leq0$. (3) No. It rules out a PSD guarantee for every positive scale; a particular scale may still give a PSD matrix. (4) The matrix is not a squared Euclidean distance matrix, subject to numerical tolerance. (5) Entrywise nonnegativity does not imply that every quadratic form $a^\mathsf{T}Ka$ is nonnegative; the cycle example has entries between zero and one but a negative eigenvalue.