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?