Gram matrix

Alicia Y. Tsai; Authors: Laurent EI Ghaoui; Contributors: Phan Hoang, Tony Tin, Ha To Tam, Nguyen Van Kep, Le Dinh Nam, Juliette Decugis, Nguyen Quoc Cuong.; Giuseppe C. Calafiore

Gram matrix

Consider $m$ $n$ -vectors $x_1, \cdots, x_m$ . The Gram matrix of the collection is the $m\times m$ matrix $G$ with elements $G_{ij}=x_i^Tx_j$ . The matrix can be expressed compactly in terms of the matrix $X = [x_1, \cdots, x_m]$ , as

$\begin{align*} G &= X^T X = \left(\begin{array}{c} x_1^T \\ \vdots \\ x_m^T \end{array}\right) \left(\begin{array}{lll} x_1 & \ldots & x_m \end{array}\right). \end{align*}$

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^TGu \ge 0$ for every vector $u \in \mathbb{R}^n$ (this comes from the identity $u^TGu = ||Xu||_2^2$ ).

Assume that each vector $x_i$ is normalized: $||x_i||_2 =1$ . Then the coefficient $G_{ij}$ can be expressed as

$\begin{align*} G_{ij} &= \cos \theta_{ij}, \end{align*}$

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:

License

Icon for the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

License

Share This Book