5
$\begingroup$

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points.

For the L2 (euclidean) distance I can use optimized matrix multiplication routines (blas etc.).

X and Y which are matrices $ n\times k $, and $ m\times k $ comprised of the points $x_1..x_n $, and $y_1..y_m$ stacked as row vectors ($k$ is the dimension of the points), the final output D a matrix $ n\times m $ of pairwise distances, with elements:

$ d_{ij} = ||x_i - y_j||^2 = ||x_i||^2 + ||y_j||^2 - 2x_i.y_j $

Where the last term $ 2x_i.y_i $ can be computed by matrix multiplication $2XY^T$ and the first two terms can be computed for each $ ||x_i||^2 = x_i . x_i $ and $ ||y_j||^2 = y_j . y_j $

Better described in this paper: http://www.plosone.org/article/fetchObject.action?uri=info%3Adoi%2F10.1371%2Fjournal.pone.0092409&representation=PDF

Is there any way to vectorize the L1 (Manhattan) distance similarly?

$\endgroup$
  • $\begingroup$ I'm not sure why computing $\| x - y \|^2$ could be slower than computing the dot products of $x$ and $y$, of $x$ and $x$, and of $y$ and $y$. $\endgroup$ – Tunococ Oct 22 '14 at 11:02
  • $\begingroup$ It's not - but if I can use optimized sums/matrix multiplication it is a lot faster than any hand rolled code. $\endgroup$ – Oliver Oct 22 '14 at 11:22
  • $\begingroup$ What exactly does $X$ and $Y$ represent? Is each of them one point? (Does $i,j$ denote the dimension or is it an index of a point? and are $x_i$ and $y_j$ vectors or coordinates?) $\endgroup$ – flawr Oct 22 '14 at 12:16
  • $\begingroup$ i and j are the index of a point. $ d_{ij} $ is the euclidean distance between $ x_i $ a point of dimension $k$, and $ y_j $, another point of dimension $k$. I've edited it, hopefully makes more sense now. $\endgroup$ – Oliver Oct 22 '14 at 21:59

Your Answer

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

Browse other questions tagged or ask your own question.