Gram Matrix

linear-algebra statistics machine-learning

Definition

Gram Matrix

Given a kernel function and a set of instances , the Gram matrix (or kernel matrix) is the symmetric matrix of all pairwise kernel evaluations. Formally:

Properties

Symmetry: The matrix is inherently symmetric () because the underlying kernel function is symmetric.

Positive Semi-Definiteness: A function is a valid kernel if and only if its Gram matrix is positive semi-definite for any finite sample. Formally, for all vectors , which implies that all eigenvalues of are non-negative.

Factorisation: Since is PSD, it can be factorised as , where the rows of correspond to the feature mappings .

Algebraic Properties of PSD Matrices

Given a symmetric positive semi-definite matrix :

Principal Submatrices: Any principal submatrix of (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, , is also positive semi-definite, as its eigenvalues are non-negative.

Scaling: For any constant , the matrix remains positive semi-definite.