[Math] Compute the pairwise Euclidean distance matrix

linear algebra

Can someone explain what is going on in the first two terms?
How does it compute pairwise Euclidean distance between rows in matrix $X$?

Is it $X^2 + (X^T)^2 -2XX^T$

In order to calculate the input pairwise similarity, we need to compute the pairwise Euclidean distance matrix $\mathbf D$ first. Using the matrix operations we could compute this matrix efficiently without using loops to do pairwise calculation:
$$D = \begin{bmatrix} \vdots & \vdots & \vdots \\ \|\mathbf x_{\mathbf i}\|^2 & \ldots & \|\mathbf x_{\mathbf i}\|^2 \\ \vdots & \vdots & \vdots \end{bmatrix} + \begin{bmatrix} \ldots & \|\mathbf x_{\mathbf i}\|^2 & \ldots \\ \ldots & \vdots & \ldots \\ \ldots & \|\mathbf x_{\mathbf i}\|^2 & \ldots \end{bmatrix} -2 \mathbf X \cdot \mathbf X^{\mathbf T} \text{ where } \mathbf X = \begin{bmatrix} \vdots \\ \mathbf x_{\mathbf i} \\ \vdots \end{bmatrix}$$

Best Answer

The first matrix is $\operatorname{diag}(X X^{\mathrm T}) \cdot \vec1$, where $\operatorname{diag}(X X^{\mathrm T})$ is a vector with the diagonal entries of $X X^{\mathrm T}$, and $\vec1$ is an all-ones matrix (with as much entries as $X$ has rows.) The second matrix is just the first one transposed, then.

For instance, if $X$ has three rows: \begin{align} X &= \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \\ \\ X^{\mathrm T} &= \Big[ \matrix{ x_1^{\mathrm T} & x_2^{\mathrm T} & x_3^{\mathrm T} } \Big] \\ \\ X X^{\mathrm T} &= \begin{bmatrix} \|x_1\|^2 & x_1 x_2^{\mathrm T} & x_1 x_3^{\mathrm T} \\ x_2 x_1^{\mathrm T} & \|x_2\|^2 & x_2 x_3^{\mathrm T} \\ x_3 x_1^{\mathrm T} & x_3 x_2^{\mathrm T} & \|x_3\|^2 \end{bmatrix} \\ \\ \operatorname{diag} (X X^{\mathrm T}) &= \begin{bmatrix} \|x_1\|^2 \\ \|x_2\|^2 \\ \|x_3\|^2 \end{bmatrix} \\ \\ \operatorname{diag} (X X^{\mathrm T}) \cdot \vec1 &= \begin{bmatrix} \|x_1\|^2 \\ \|x_2\|^2 \\ \|x_3\|^2 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} \\ &= \begin{bmatrix} \|x_1\|^2 & \|x_1\|^2 & \|x_1\|^2 \\ \|x_2\|^2 & \|x_2\|^2 & \|x_2\|^2 \\ \|x_3\|^2 & \|x_3\|^2 & \|x_3\|^2 \end{bmatrix}. \end{align}

Related Question