Positive Definite Kernels and Gram Matrices

From Similarity Scores to Gram Matrices

A function that assigns a large value to similar inputs may look like a useful kernel, but an intuitive notion of similarity is not enough. The defining test is algebraic: for every finite selection of inputs, the matrix of pairwise function values must be symmetric and have no negative quadratic directions. This condition is what makes the function a positive semidefinite kernel.

The test is finite-dimensional even when the input domain is large or has no vector-space structure. Choose any finite list of inputs, form the matrix of pairwise values, and check its quadratic form. A valid kernel must pass for every such list, not merely for one data set.

Definition: Let \(\mathcal X\) be a nonempty set. A real-valued function \(k:\mathcal X\times\mathcal X\to\mathbb R\) is a positive semidefinite kernel if, for every integer \(n\geq 1\), every \(x_1,\ldots,x_n\in\mathcal X\), and every \(a_1,\ldots,a_n\in\mathbb R\), it satisfies \(k(x_i,x_j)=k(x_j,x_i)\) for all \(i,j\), and \[ \sum_{i=1}^n\sum_{j=1}^n a_i a_j k(x_i,x_j)\geq 0. \] The matrix \(K\in\mathbb R^{n\times n}\) with entries \(K_{ij}=k(x_i,x_j)\) is the Gram matrix for those inputs. The condition is equivalently that every such Gram matrix is symmetric positive semidefinite.

Repeated inputs are allowed in this definition. A Gram matrix need not be invertible: positive semidefinite means that its eigenvalues are nonnegative, not necessarily strictly positive. Some texts use “positive definite kernel” as a synonym for positive semidefinite kernel. To avoid ambiguity, this tutorial uses positive semidefinite for the nonnegative quadratic-form condition. A kernel is strictly positive definite if every Gram matrix on pairwise distinct inputs has strictly positive quadratic form for every nonzero coefficient vector; strictness is a stronger property and is not required here.

Quadratic Forms as the Test

For a chosen list of inputs, write \(a=(a_1,\ldots,a_n)^\mathsf T\). The kernel condition is \(a^\mathsf TKa\geq 0\) for every \(a\in\mathbb R^n\). For a real matrix, this quadratic-form condition alone does not check symmetry: the antisymmetric part contributes zero to every quadratic form. Symmetry must therefore be verified separately, unless it is built into the formula for \(k\).

When a particular Gram matrix is symmetric, the spectral theorem says it is positive semidefinite exactly when all its eigenvalues are nonnegative. This is useful for checking a small example, but a calculation on one finite set does not establish that a function is a kernel on its whole domain. The definition quantifies over every finite choice of inputs.

Worked Example: The Linear Kernel

Let \(\mathcal X=\mathbb R\) and \(k(x,y)=xy\). For the three inputs \(x_1=1,x_2=2,x_3=3\), the Gram matrix is

K= \begin{pmatrix} 1&2&3\\ 2&4&6\\ 3&6&9 \end{pmatrix}.

It is symmetric. For arbitrary coefficients \(a_1,a_2,a_3\), its quadratic form is

\sum_{i=1}^3\sum_{j=1}^3a_i a_jx_ix_j =\left(\sum_{i=1}^3a_ix_i\right)^2 =(a_1+2a_2+3a_3)^2\geq 0.

The same calculation works for any finite number of real inputs, not just these three. Thus \(k(x,y)=xy\) is a positive semidefinite kernel on \(\mathbb R\). The displayed matrix is singular, which is allowed: the coefficients \((2,-1,0)\), for example, give quadratic form zero.

Worked Example: A Constant Kernel

Let \(k(x,y)=c\) for all \(x,y\in\mathcal X\), where \(c\) is a fixed real number. For any \(n\) inputs, every entry of the Gram matrix is \(c\), and for any coefficient vector \(a\),

a^\mathsf TKa =\sum_{i=1}^n\sum_{j=1}^n a_i a_jc =c\left(\sum_{i=1}^n a_i\right)^2.

If \(c\geq 0\), this is nonnegative for all choices, so the function is a positive semidefinite kernel. If \(c<0\), take \(n=1\) and \(a_1=1\); then the quadratic form is \(c<0\). Therefore the constant function is a positive semidefinite kernel exactly when \(c\geq 0\). In particular, the constant kernel with \(c=2\) is valid, while the one with \(c=-1\) is not.

A Sufficient Test Using Vectors

Many kernel checks can be simplified by expressing the function as an ordinary inner product of vectors. This gives a useful sufficient condition without requiring any assumption that the input domain itself is a vector space.

Proposition: Suppose there is a map \(\phi:\mathcal X\to\mathbb R^m\), for some finite \(m\), such that \(k(x,y)=\phi(x)^\mathsf T\phi(y)\) for all \(x,y\in\mathcal X\). Then \(k\) is a positive semidefinite kernel.

Proof. The inner product is symmetric, so \(k(x,y)=k(y,x)\). Choose any \(n\) inputs \(x_1,\ldots,x_n\) and real coefficients \(a_1,\ldots,a_n\). By the assumed representation and bilinearity of the inner product,

\sum_{i=1}^n\sum_{j=1}^n a_i a_j k(x_i,x_j) =\sum_{i=1}^n\sum_{j=1}^n a_i a_j\phi(x_i)^\mathsf T\phi(x_j) =\left\|\sum_{i=1}^n a_i\phi(x_i)\right\|^2 \geq 0.

This holds for every finite input list and every coefficient vector, which proves the proposition. \(\square\)

For the linear kernel, take \(\phi(x)=x\) on \(\mathbb R\), recovering the squared-sum calculation above. The criterion is sufficient, not a requirement that every kernel be presented in this particular finite-dimensional way.

Distance-Based Functions: A Valid Kernel and a Counterexample

A function of distance is not automatically a kernel. In fact, raw distance and squared distance fail the Gram-matrix test in a particularly simple way. By contrast, the Gaussian function of squared Euclidean distance is a standard valid kernel.

Worked Example: Squared Distance Fails the Kernel Test

Take \(\mathcal X=\mathbb R\) and \(k(x,y)=(x-y)^2\). On the two inputs \(x_1=0\) and \(x_2=1\), the Gram matrix is

K= \begin{pmatrix} 0&1\\ 1&0 \end{pmatrix}.

With coefficients \(a_1=1\) and \(a_2=-1\), the quadratic form is

a^\mathsf TKa = \begin{pmatrix}1&-1\end{pmatrix} \begin{pmatrix}0&1\\1&0\end{pmatrix} \begin{pmatrix}1\\-1\end{pmatrix} =-2<0.

Thus squared distance is not a positive semidefinite kernel. The same two inputs also disprove the claim for the raw distance \(k(x,y)=|x-y|\): its Gram matrix is again \(\begin{pmatrix}0&1\\1&0\end{pmatrix}\), and the same coefficient vector gives \(-2\). These failures show why symmetry and nonnegative similarity values alone are insufficient.

Theorem: For every \(\gamma\geq 0\), the Gaussian function \(k(x,y)=\exp(-\gamma\|x-y\|^2)\) on \(\mathbb R^d\) is a positive semidefinite kernel.

Proof. If \(\gamma=0\), the function is the constant kernel \(1\), already shown to be positive semidefinite. Suppose \(\gamma>0\). Using \(\|x-y\|^2=\|x\|^2+\|y\|^2-2x^\mathsf Ty\), factor the kernel as

k(x,y) =\exp(-\gamma\|x\|^2)\exp(-\gamma\|y\|^2)\exp(2\gamma x^\mathsf Ty).

For \(x,y\in\mathbb R^d\), the exponential power series and the multinomial formula give

\exp(2\gamma x^\mathsf Ty) =\sum_{m=0}^{\infty}\frac{(2\gamma)^m}{m!}(x^\mathsf Ty)^m =\sum_{\alpha\in\mathbb N_0^d} \frac{(2\gamma)^{|\alpha|}}{\alpha!}x^\alpha y^\alpha.

Here \(\alpha=(\alpha_1,\ldots,\alpha_d)\), \(|\alpha|=\sum_{r=1}^d\alpha_r\), \(\alpha!=\prod_{r=1}^d\alpha_r!\), and \(x^\alpha=\prod_{r=1}^d x_r^{\alpha_r}\). Thus for any finite inputs \(x_1,\ldots,x_n\) and coefficients \(a_1,\ldots,a_n\), the Gram quadratic form is

\sum_{i,j=1}^n a_i a_j k(x_i,x_j) = \sum_{\alpha\in\mathbb N_0^d} \frac{(2\gamma)^{|\alpha|}}{\alpha!} \left( \sum_{i=1}^n a_i\exp(-\gamma\|x_i\|^2)x_i^\alpha \right)^2 \geq 0.

The rearrangement is valid: for each of the finitely many pairs \((i,j)\), the exponential series is absolutely convergent, so the finite weighted sum over pairs can be interchanged with the series. Every term on the right is nonnegative. Symmetry follows from \(\|x-y\|=\|y-x\|\). Hence every finite Gram matrix is symmetric positive semidefinite, proving the theorem. \(\square\)

Worked Example: Checking a Gaussian Gram Matrix

Take \(k(x,y)=\exp(-(x-y)^2)\) on \(\mathbb R\), so \(\gamma=1\), and use \(x_1=0,x_2=1,x_3=2\). Set \(r=e^{-1}\) and \(s=e^{-4}\). The Gram matrix is

K= \begin{pmatrix} 1&r&s\\ r&1&r\\ s&r&1 \end{pmatrix}.

For a concrete quadratic-form check, choose \(a=(1,-2,1)^\mathsf T\). Direct multiplication gives

a^\mathsf TKa=6-8r+2s =6-\frac{8}{e}+\frac{2}{e^4} \approx 3.094>0.

This particular calculation checks only one coefficient vector. The theorem proves the required nonnegativity for every coefficient vector and every finite selection of real inputs; that universal conclusion cannot be inferred from this single numerical check.

Common Pitfalls and Why the Condition Matters

The Gram condition is the precise constraint that distinguishes a valid kernel from an arbitrary symmetric similarity score. It ensures that no finite collection of inputs produces a negative quadratic form. This algebraic structure is central to kernel methods: later constructions use positive semidefinite kernels to build function spaces and learning procedures. At this stage, the essential point is to verify the finite-matrix condition, rather than to assume that an intuitive similarity measure will satisfy it.

Pitfall: checking only that the values are nonnegative. A symmetric function can have nonnegative entries and still have a negative quadratic form. For example, the squared-distance Gram matrix above has nonnegative entries but fails the test.
Pitfall: testing only one data set. A positive semidefinite Gram matrix for one finite input list does not prove that the function is a kernel. The definition requires the condition for every finite list.
Pitfall: demanding a strictly positive quadratic form. A zero quadratic form is permitted for a positive semidefinite kernel. The linear-kernel example has nonzero coefficients that produce zero.
Pitfall: forgetting symmetry. A nonnegative quadratic form by itself does not establish that a real-valued function is a kernel; symmetry is a separate requirement in the definition.

For a proposed function, a reliable workflow is to check symmetry first, then form small Gram matrices to look for counterexamples. To establish validity, use an argument that covers arbitrary finite inputs and coefficients, such as a squared-norm representation or the Gaussian expansion.

Check Your Understanding

Use the finite Gram-matrix definition to answer the following questions.

For \(k(x,y)=xy\) on \(\mathbb R\), write the quadratic form for arbitrary finite inputs and coefficients as a square.
For which real values of \(c\) is \(k(x,y)=c\) a positive semidefinite kernel? Give a coefficient choice that rules out every other value.
Why does a nonnegative quadratic form for a real matrix not, by itself, verify the full kernel definition?
Use two inputs to show that \(k(x,y)=|x-y|\) is not a positive semidefinite kernel.
In the Gaussian example, why does checking one coefficient vector not establish that a function is a kernel?