Vectorize the pairwise kronecker product in matlab

4
votes

Suppose there are two matrices of the same size, and I want to calculate the summation of their column-wise kronecker product. Due to sometimes the column size is quite large so that the speed could be very slow. Thus, is there anyway to vectorize this function or any function may help reducing the complexity in matlab? Thanks in advance.

The corresponding matlab code with a for-loop is provided below, and the answer of d is the interested output: 

A = rand(3,7);
B = rand(3,7);
d = zeros(size(A,1)*size(B,1),1);
for i=1:size(A,2)
    d = d + kron(A(:,i),B(:,i));
end
2
matlabmathvectorvectorization
You can edit your own question by clicking the tiny "edit" label below the tags of your post, it might be more sustainable than adding information in comments. - Andras Deak
And you can remove your comments by clicking the small "x" icon which appears if you hover above your comment. This is sometimes useful to keep questions and answers free from garbage. I will delete this comment and my previous one in a while as they are now not needed for your question. - Andras Deak

2 Answers

4
votes

Using the rewriting of the Kronecker product given by Daniels answer

e=zeros(size(B,1),size(A,1));
for i=1:size(A,2)
    e = e + B(:,i)*A(:,i).';
end
e=reshape(e,[],1);

we say that

C = A'

and thus

for i=1:m
    e = e + B(:,i)*C(i,:);
end

which is the definition of the matrix product

B*C.

In conclusion the problem can thus be solved by the simple matrix product

d = reshape(B*A',[],1);
3
votes

The kronecker product of two vectors is just a reshaped result of the matrix multiplication of both vectors:

e=zeros(size(B,1),size(A,1));
for i=1:size(A,2)
    e = e + B(:,i)*A(:,i).';
end
e=reshape(e,[],1);

Now knowing that it's just a sum of products, it can be put into a single line using bsxfun

f=reshape(sum(bsxfun(@times,permute(B,[1,3,2]),permute(A,[3,1,2])),3),[],1);

Depending on the input, the bsxfun-sulution is slightly faster than the matrix multiplication, but that comes with a high memory consumption. The bsxfun-solution uses O(size(A,1)*size(B,1)*size(B,2)) while the for-loop only uses O(size(A,1)*size(B,1)) in addition to the input arguments.