gram matrix

Gram matrix

Given vectors $v_1,\dots ,v_m$ in an inner product space $(\mathcal{H},⟨\cdot ,\cdot ⟩)$, the Gram matrix is $G\in {\mathbb{R}}^{m\times m}$ with entries $G_{ij}=⟨v_i,v_j⟩$.

$G$ is symmetric positive semidefinite
$G$ is positive definite iff $v_i$ are linearly independent.

Sample gram matrix

For $X\in {\mathbb{R}}^{n\times d}$, the sample gram matrix is $G=X{X}^T\in {\mathbb{R}}^{n\times n}$.

Feature gram matrix

For $X\in {\mathbb{R}}^{n\times d}$, the feature gram matrix $G=X^{T}X\in {\mathbb{R}}^{d\times d}$
The second moment matrix refers to the and covariance matrix.

Both $X{X}^T$ and $X^{T}X$ can be the same Gram matrices the difference is whether your vectors are stored as rows or columns of $X$, respectively. They can also be represented as a sum of rank-1 matrices from outer products!

Vectors-as-columns convention is standard in linear algebra where we usually think of vectors as column vectors.
However, in machine learning and data science, we often use the vectors-as-rows convention (each row is a data point with $n$ features), which would make $X{X}^T$ the Gram matrix.

Let $X\in {\mathbb{R}}^{m\times n}$, rows $x_i^{\top }$ and columns $y_k$ (so $X=[y_1{y}_2\dots y_n]=\left[\begin{array}{c}{x}_1^{\top }\\ ⋮\\ x_m^{\top }\end{array}\right]$).
We use the same dummy index $k$ in both views (its range differs).

Vectors-as-rows (ML convention): Gram is $X{X}^{\top }\in {\mathbb{R}}^{m\times m}$.

Entrywise (inner products):

$$X{X}^{\top }=\left[\begin{array}{cccc}{\sum }_{k=1}^n{X}_{1k}^2& {\sum }_{k=1}^n{X}_{1k}{X}_{2k}& \cdots & {\sum }_{k=1}^n{X}_{1k}{X}_{mk}\\ {\sum }_{k=1}^n{X}_{2k}{X}_{1k}& {\sum }_{k=1}^n{X}_{2k}^2& \cdots & {\sum }_{k=1}^n{X}_{2k}{X}_{mk}\\ ⋮& ⋮& \ddots & ⋮\\ {\sum }_{k=1}^n{X}_{mk}{X}_{1k}& {\sum }_{k=1}^n{X}_{mk}{X}_{2k}& \cdots & {\sum }_{k=1}^n{X}_{mk}^2\end{array}\right]\text{so}(X{X}^{\top }{)}_{ij}=\sum _{k=1}^n{X}_{ik}{X}_{jk}.$$

Sum of outer products of columns (same matrix):

$$X{X}^{\top }=\sum _{k=1}^n{y}_k{y}_k^{\top },\text{with}(y_k{y}_k^{\top }{)}_{ij}=(y_k{)}_i(y_k{)}_j.$$

---

Vectors-as-columns (classical LA): Gram is $X^{\top }X\in {\mathbb{R}}^{n\times n}$.

Entrywise (inner products):

$$X^{\top }X=\left[\begin{array}{cccc}{\sum }_{k=1}^m{X}_{k1}^2& {\sum }_{k=1}^m{X}_{k1}{X}_{k2}& \cdots & {\sum }_{k=1}^m{X}_{k1}{X}_{kn}\\ {\sum }_{k=1}^m{X}_{k2}{X}_{k1}& {\sum }_{k=1}^m{X}_{k2}^2& \cdots & {\sum }_{k=1}^m{X}_{k2}{X}_{kn}\\ ⋮& ⋮& \ddots & ⋮\\ {\sum }_{k=1}^m{X}_{kn}{X}_{k1}& {\sum }_{k=1}^m{X}_{kn}{X}_{k2}& \cdots & {\sum }_{k=1}^m{X}_{kn}^2\end{array}\right]\text{so}(X^{\top }X{)}_{ij}=\sum _{k=1}^m{X}_{ki}{X}_{kj}.$$

Sum of outer products of rows (same matrix):

$$X^{\top }X=\sum _{k=1}^m{x}_k^{\top }{x}_k,\text{with}(x_k^{\top }{x}_k{)}_{ij}=(x_k{)}_i(x_k{)}_j.$$