# Optimized way to compute L1 distance matrix

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?

• 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$. – Tunococ Oct 22 '14 at 11:02
• It's not - but if I can use optimized sums/matrix multiplication it is a lot faster than any hand rolled code. – Oliver Oct 22 '14 at 11:22
• 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?) – flawr Oct 22 '14 at 12:16
• 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. – Oliver Oct 22 '14 at 21:59