Gram matrix

L. El Ghaoui

Gram matrix

Consider $m n$ -vectors $x_{1},\dots, x_{m}$ . The Gram matrix of the collection is the $m \times n$ matrix $G$ with elements $G_{ij}=sx_{i}^{T}x_{j}.$ . The matrix can be expressed compactly in terms of the matrix $X = [x_{1},\dots,x_{m}]$ , as

$G = X^{T}X = \begin{pmatrix} x_{1}^{T} \\ \vdots \\ x_{m}^{T} \end{pmatrix} \begin{pmatrix}x_{1} & \dots & x_{m} \end{pmatrix}.$

By construction, a Gram matrix is always symmetric, meaning that $G_{ij}=G_{ji}$ for every pair $(i, j)$ . It is also positive semi-definite, meaning that $u^{T}Gu \le 0$ for every vector $u \in \mathbb{R}^{n}$ (this comes from the identity $u^{T}Gu = || Xu ||_{2}^{2}$ ).

Assume that each vector $x_{i}$
is normalized: $|| x_{i} ||_{2}=1$ . Then the coefficient $G_{ij}$
can be expressed as

$G_{ij} = \cos\theta_{ij},$

where $\theta_{ij}$ is the angle between the vectors $x_{i}$ and $x_{j}$ . Thus $G_{ij}$
is a measure of how similar $x_{i}$ and $x_{j}$ are.

The matrix $G$ arises for example in text document classification, with $G_{ij}$
a measure of similarity between the $i$ -th and $j$ -th document, and $x_{i}, x_{j}$ their respective bag-of-words representation (normalized to have Euclidean norm $1$ ).

See also:

Gram matrix

License

Share This Book