Vectorize the calculation for Euclidean distance between matrix and vector

Question

I want to calculate the Euclidean distance between matrices and a standard vector. All my matrices are stored in a list, let's say, A, so that

A = [[1,2,3],[2,3,4]...,[8,9,10]],

And the standard vector is, let's say, [1,1,1],

I can do this using for-loop, but it's really time-consuming since there usually hundreds of matrices in A. How can I vectorize this calculation to shorten the runtime?

score 2 · Accepted Answer · answered Mar 23 '19 at 19:17

2

A = np.array([[1,2,3],
              [2,3,4],
              [3,4,5],
              [4,5,6],
              [5,6,7],
              [6,7,8],
              [7,8,9],
              [8,9,10]])

v = np.array([1,1,1])

# Compute the length (norm) of the distance between the vectors
distance = np.linalg.norm(A - v, axis = 1)
print(distance)

[ 2.23606798  3.74165739  5.38516481  7.07106781  8.77496439 10.48808848
 12.20655562 13.92838828]

answered Mar 23 '19 at 19:17

Nathaniel

3,230
11
18

Is this the fastest way? – HAOYANG MI Mar 23 '19 at 20:59
[Here](https://stackoverflow.com/questions/1401712/how-can-the-euclidean-distance-be-calculated-with-numpy/21986532) is one of several questions that compares the speed of different methods. Particularly for large/numerous matrices, I would strongly recommend ``np.linalg.norm()``. – Nathaniel Mar 23 '19 at 21:59

Divakar · Answer 2 · 2019-03-24T09:54:28.457

Approach #1

Use np.einsum for the distance computations. To solve our case here, we could do -

def dist_matrix_vec(matrix, vec):    
    d = np.subtract(matrix,vec)
    return np.sqrt(np.einsum('ij,ij->i',d,d))

Sample run -

In [251]: A = [[1,2,3],[2,3,4],[8,9,10]]

In [252]: B = np.array([1,1,1])

In [253]: dist_matrix_vec(A,B)
Out[253]: array([ 2.23606798,  3.74165739, 13.92838828])

Approach #2

When working with large data, we can use numexpr module that supports multi-core processing if the intended operations could be expressed as arithmetic ones. To solve our case, we can express it like so -

import numexpr as ne

def dist_matrix_vec_numexpr(matrix, vec): 
    matrix = np.asarray(matrix)
    vec = np.asarray(vec)
    return np.sqrt(ne.evaluate('sum((matrix-vec)**2,1)'))

Timings on large arrays -

In [295]: np.random.seed(0)
     ...: A = np.random.randint(0,9,(10000,3))
     ...: B = np.random.randint(0,9,(3,))

In [296]: %timeit np.linalg.norm(A - B, axis = 1) #@Nathaniel's soln
     ...: %timeit dist_matrix_vec(A,B)
     ...: %timeit dist_matrix_vec_numexpr(A,B)
1000 loops, best of 3: 244 µs per loop
10000 loops, best of 3: 131 µs per loop
10000 loops, best of 3: 96.5 µs per loop

In [297]: np.random.seed(0)
     ...: A = np.random.randint(0,9,(100000,3))
     ...: B = np.random.randint(0,9,(3,))

In [298]: %timeit np.linalg.norm(A - B, axis = 1) #@Nathaniel's soln
     ...: %timeit dist_matrix_vec(A,B)
     ...: %timeit dist_matrix_vec_numexpr(A,B)
100 loops, best of 3: 5.31 ms per loop
1000 loops, best of 3: 1.43 ms per loop
1000 loops, best of 3: 918 µs per loop

The numexpr based one was with 8 threads. Thus, with more number of threads available for compute, it should improve further. Related post on how to control multi-core functionality.

Vectorize the calculation for Euclidean distance between matrix and vector

2 Answers2