2

So first off, I think what I'm trying to achieve is some sort of Cartesian product but elementwise, across the columns only.

What I'm trying to do is, if you have multiple 2D arrays of size [ (N,D1), (N,D2), (N,D3)...(N,Dn) ]

The result is thus to be a combinatorial product across axis=1 such that the final result will then be of shape (N, D) where D=D1*D2*D3*...Dn

e.g.

A = np.array([[1,2],
              [3,4]])
B = np.array([[10,20,30],
              [5,6,7]])

cartesian_product( [A,B], axis=1 )
>> np.array([[ 1*10, 1*20, 1*30, 2*10, 2*20, 2*30 ]
             [ 3*5,  3*6,  3*7,  4*5,  4*6,  4*7  ]])

and extendable to cartesian_product([A,B,C,D...], axis=1)

e.g.

A = np.array([[1,2],
              [3,4]])
B = np.array([[10,20],
              [5,6]])
C = np.array([[50, 0],
              [60, 8]])
cartesian_product( [A,B,C], axis=1 )
>> np.array([[ 1*10*50, 1*10*0, 1*20*50, 1*20*0, 2*10*50, 2*10*0, 2*20*50, 2*20*0] 
             [ 3*5*60,  3*5*8,  3*6*60,  3*6*8,  4*5*60,  4*5*8,  4*6*60,  4*6*8]])

I have a working solution that essentially creates an empty (N,D) matrix and then broadcasting a vector columnwise product for each column within nested for loops for each matrix in the provided list. Clearly is horrible once the arrays get larger!

Is there an existing solution within numpy or tensorflow for this? Potentially one that is efficiently paralleizable (A tensorflow solution would be wonderful but a numpy is ok and as long as the vector logic is clear then it shouldn't be hard to make a tf equivalent)

I'm not sure if I need to use einsum, tensordot, meshgrid or some combination thereof to achieve this. I have a solution but only for single-dimension vectors from https://stackoverflow.com/a/11146645/2123721 even though that solution says to work for arbitrary dimensions array (which appears to mean vectors). With that one i can do a .prod(axis=1), but again this is only valid for vectors.

thanks!

undercurrent
  • 285
  • 1
  • 2
  • 12
  • How do you have those multiple 2D arrays stored? As a list of arrays? Or maybe as one 3D array? – Divakar Jun 02 '17 at 07:48
  • @Divakar At the moment, the multiple 2D arrays are stored in memory, in a list as per the example [A, B...]. These are as a result of a previous step of broadcasted dot product. For now, this is ok and it's not a bottleneck to store them individually. If there are any suggestions for optimizing this stage too i'm all ears! – undercurrent Jun 02 '17 at 07:59

1 Answers1

1

Here's one approach to do this iteratively in an accumulating manner making use of broadcasting after extending dimensions for each pair from the list of arrays for elmentwise multiplications -

L = [A,B,C]  # list of arrays
n = L[0].shape[0]
out = (L[1][:,None]*L[0][:,:,None]).reshape(n,-1)
for i in L[2:]:
    out = (i[:,None]*out[:,:,None]).reshape(n,-1)
Divakar
  • 218,885
  • 19
  • 262
  • 358