Gram Matrix

linear-algebra statistics machine-learning

Definition

Gram Matrix

Given a kernel function $k$ and a set of instances $D=\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$, the Gram matrix (or kernel matrix) $K\in {\mathbb{R}}^{n\times n}$ is the symmetric matrix of all pairwise kernel evaluations. Formally:

$K_{ij}=k({\mathbf{x}}_i,{\mathbf{x}}_j)$

$$K=\left(\begin{array}{cccc}k({\mathbf{x}}_1,{\mathbf{x}}_1)& k({\mathbf{x}}_1,{\mathbf{x}}_2)& \dots & k({\mathbf{x}}_1,{\mathbf{x}}_n)\\ k({\mathbf{x}}_2,{\mathbf{x}}_1)& k({\mathbf{x}}_2,{\mathbf{x}}_2)& \dots & k({\mathbf{x}}_2,{\mathbf{x}}_n)\\ ⋮& ⋮& \ddots & ⋮\\ k({\mathbf{x}}_n,{\mathbf{x}}_1)& k({\mathbf{x}}_n,{\mathbf{x}}_2)& \dots & k({\mathbf{x}}_n,{\mathbf{x}}_n)\end{array}\right)$$

Properties

Symmetry: The matrix is inherently symmetric ($K=K^{\top }$) because the underlying kernel function is symmetric.

Positive Semi-Definiteness: A function $k$ is a valid kernel if and only if its Gram matrix is positive semi-definite for any finite sample. Formally, ${\mathbf{c}}^{\top }K\mathbf{c}\ge 0$ for all vectors $\mathbf{c}\in {\mathbb{R}}^n$, which implies that all eigenvalues of $K$ are non-negative.

Factorisation: Since $K$ is PSD, it can be factorised as $K=\Phi {\Phi }^{\top }$, where the rows of $\Phi$ correspond to the feature mappings $\varphi (x_i)$.

Algebraic Properties of PSD Matrices

Given a symmetric positive semi-definite matrix $K$:

Principal Submatrices: Any principal submatrix of $K$ (formed by selecting the same set of row and column indices) is also positive semi-definite.

Matrix Powers: The square of a symmetric PSD matrix, $G=KK$, is also positive semi-definite, as its eigenvalues ${\lambda }_i^2$ are non-negative.

Scaling: For any constant $c\ge 0$, the matrix $cK$ remains positive semi-definite.