How to find the pairwise differences between rows of two very large matrices using numpy?

by

Here’s another way to perform :

(a-b)^2 = a^2 + b^2 – 2ab

with np.einsum for the first two terms and dot-product for the third one –

import numpy as np

np.einsum('ij,ij->i',A,A)[:,None] + np.einsum('ij,ij->i',B,B) - 2*np.dot(A,B.T)

Runtime test

Approaches –

def loopy_app(A,B):
    m,n = A.shape[0], B.shape[0]
    out = np.empty((m,n))
    for i,a in enumerate(A):
       out[i] = np.sum((a - B)**2,1)
    return out

def broadcasting_app(A,B):
    return ((A[:,np.newaxis,:] - B)**2).sum(-1)

# @Paul Panzer's soln
def outer_sum_dot_app(A,B):
    return np.add.outer((A*A).sum(axis=-1), (B*B).sum(axis=-1)) - 2*np.dot(A,B.T)

# @Daniel Forsman's soln
def einsum_all_app(A,B):
    return np.einsum('ijk,ijk->ij', A[:,None,:] - B[None,:,:], \
                                        A[:,None,:] - B[None,:,:])

# Proposed in this post
def outer_einsum_dot_app(A,B):
    return np.einsum('ij,ij->i',A,A)[:,None] + np.einsum('ij,ij->i',B,B) - \
                                                            2*np.dot(A,B.T)

Timings –

In [51]: A = np.random.randn(1000,100)
    ...: B = np.random.randn(1000,100)
    ...: 

In [52]: %timeit loopy_app(A,B)
    ...: %timeit broadcasting_app(A,B)
    ...: %timeit outer_sum_dot_app(A,B)
    ...: %timeit einsum_all_app(A,B)
    ...: %timeit outer_einsum_dot_app(A,B)
    ...: 
10 loops, best of 3: 136 ms per loop
1 loops, best of 3: 302 ms per loop
100 loops, best of 3: 8.51 ms per loop
1 loops, best of 3: 341 ms per loop
100 loops, best of 3: 8.38 ms per loop

More Related Contents:

  1. Change sign of elements with an odd sum of indices
  2. Difference between numpy.array shape (R, 1) and (R,)
  3. What are the differences between numpy arrays and matrices? Which one should I use?
  4. How does numpy.newaxis work and when to use it?
  5. numpy matrix vector multiplication [duplicate]
  6. Numpy matrix to array
  7. how does multiplication differ for NumPy Matrix vs Array classes?
  8. Bin elements per row – Vectorized 2D Bincount for NumPy
  9. Numpy – create matrix with rows of vector
  10. How do I use np.newaxis?
  11. Numpy ‘smart’ symmetric matrix
  12. Convert a 1D array to a 2D array in numpy
  13. Vectorized NumPy linspace for multiple start and stop values
  14. numpy get index where value is true
  15. Deprecation status of the NumPy matrix class
  16. Efficiently Calculating a Euclidean Distance Matrix Using Numpy
  17. Iterating over Numpy matrix rows to apply a function each?
  18. Subtracting numpy arrays of different shape efficiently
  19. How to get element-wise matrix multiplication (Hadamard product) in numpy?
  20. NumPy Broadcasting: Calculating sum of squared differences between two arrays
  21. NumPy array/matrix of mixed types
  22. Replace sub part of matrix by another small matrix in numpy
  23. How to convert a column or row matrix to a diagonal matrix in Python?
  24. Is there a standard solution for Gauss elimination in Python?
  25. How to find linearly independent rows from a matrix
  26. Numpy select rows based on condition
  27. Multiple matrix multiplication
  28. Numpy array broadcasting rules
  29. A numpy array unexpectedly changes when changing another one despite being separate
  30. Numpy `ValueError: operands could not be broadcast together with shape …`

Leave a Comment