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}

  • $\begingroup$ What information should I provide? $\endgroup$ – YohanRoth Mar 14 at 23:41
  • $\begingroup$ Oh, sorry. never mind the "more information" part. That $\mathbf{x_i}$ notation wasn't clear to me at that time. $\endgroup$ – Rócherz Mar 15 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.