# Compute the pairwise Euclidean distance matrix

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}$$

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}
• Oh, sorry. never mind the "more information" part. That $\mathbf{x_i}$ notation wasn't clear to me at that time. – Rócherz Mar 15 at 0:20