Gram matrix
Topic of Support vector machines, part of Statistical learning
Gram matrix
| Type | Topic |
| Taught in | Support vector machines |
| Part | Statistical learning |
| Questions using it | 1 |
The n\times n matrix of kernel values K_{ij}=K(\mathbf{x}_i,\mathbf{x}_j) on a sample. A function is a valid kernel exactly when every such matrix is symmetric and positive semi-definite, which is what keeps the support vector dual convex.
In Support vector machines
A proposed similarity is not automatically an inner product. The necessary and sufficient condition is symmetry and positive semidefiniteness of every finite Gram matrix. This yields a representation in a Hilbert feature space. Mercer’s spectral theorem adds regularity and domain assumptions. The finite-Gram criterion is the condition needed for the convex dual:
\sum_{i=1}^{n}\sum_{j=1}^{n} c_i c_j K(x_i,x_j)\ge 0
for every finite choice of input points and every real vector c. Equivalently, the Gram matrix K_S=(K(x_i,x_j))_{ij} must be positive semidefinite. Checking one training Gram matrix checks that particular optimisation problem, not validity of the function on every possible data set.
Used in
- Taught in Support vector machines
- Questions that use it (1) — A Gram matrix
- All 10 questions on Support vector machines
See also
Kernel · Kernel density estimator · Positive definite matrix · Support vectors and their multipliers · Signed distance · Vapnik’s radius–margin bound · Hard-margin primal · Hard-margin dual