Put Pairwise Differences Of Matrix Rows In 3-d Array

I have a matrix Y of shape (n, d). I already calculated the pairwise row-differences in the following way: I, J = np.triu_indices(Y.shape[0], 0) rowDiffs = (Y[I, :] - Y[J, :]) No

Solution 1:

I have found some success with this:

row_diffs = Y[:, np.newaxis] - Y

Y[:, np.newaxis] creates a version of Y with dimensions (n, 1, 3). Then, the subtraction uses broadcasting to do what you want.

Unfortunately, I've found this approach to be relatively slow and I haven't yet found a better way.

Full example:

>>> x = np.random.randint(10, size=(4, 3))
>>> x
array([[4, 0, 8],
       [8, 5, 3],
       [4, 1, 6],
       [2, 2, 4]])
>>> x[:, np.newaxis] - x
array([[[ 0,  0,  0],
        [-4, -5,  5],
        [ 0, -1,  2],
        [ 2, -2,  4]],

       [[ 4,  5, -5],
        [ 0,  0,  0],
        [ 4,  4, -3],
        [ 6,  3, -1]],

       [[ 0,  1, -2],
        [-4, -4,  3],
        [ 0,  0,  0],
        [ 2, -1,  2]],

       [[-2,  2, -4],
        [-6, -3,  1],
        [-2,  1, -2],
        [ 0,  0,  0]]])

Solution 2:

Here's a vectorized approach using broadcasting and np.einsum -

np.einsum('ij,ijk->ik',W,Y[:,None] - Y)

Runtime test -

In [29]: def original_app(Y,W):
    ...:     m = Y.shape[0]
    ...:     C = np.zeros((m,m))
    ...:     for i in range(Y.shape[0]): 
    ...:         for j in range(Y.shape[0]):
    ...:             C[i,:] = C[i,:] + W[i, j] * (Y[i, :]-Y[j, :])
    ...:     return C
    ...: 

In [30]: # Inputs
    ...: Y = np.random.rand(100,100)
    ...: W = np.random.rand(100,100)
    ...: 

In [31]: out = original_app(Y,W)

In [32]: np.allclose(out, np.einsum('ij,ijk->ik',W,Y[:,None] - Y))
Out[32]: True

In [33]: %timeit original_app(Y,W)
10 loops, best of 3: 70.8 ms per loop

In [34]: %timeit np.einsum('ij,ijk->ik',W,Y[:,None] - Y)
100 loops, best of 3: 4.01 ms per loop