Does MATLAB has matrix convolution function

I know that MATLAB has a conv(u,v) function that can conduct convolution. Usually u are v are supposed to be vectors of real numbers or complex numbers. Does this function accept matrix input, i.e., u and v are both a sequence of matrices? If it can not, is there any function in MATLAB that can do this job? Thanks!

[Matt J]

Does this function accept matrix input, i.e., u and v are both a sequence of matrices?

Do you mean "u and v are both a sequence of vectors"? You want to convolve column by column for example?

[Heng]

I mean the elements in u and v are matrix. For example, u is a sequence containing 5 matrices of size 2x2, and v is a sequence containing 4 matrices of size 2x1. So in the definition formula:

http://i50.tinypic.com/5v2dg3.png

the product in the summation is a matrix multiplication between a matrix of size 2x2 and a matrix of size 2x1.

Answer 1

[Matt J]

Here's another method, requiring only stock MATLAB functions. As before, I assume that u is 2x2xM and v is 2xN, i.e., u(:,:,i) are the sequence of matrices and v(:,j) are the sequence of vectors.

 u(:,:,M+1)=0;
 U=num2cell(u,[1,2]);
 L=M+N-1;

 T=toeplitz(1:L,[1,ones(1,N-1)*(M+1)]);
 T(T>M)=M+1;
 result = cell2mat(U(T))*v(:);

 result=reshape(result,2,[])

[Heng]

That's cool. Please give me some time to verify it.

[Heng]

Thank you for so many replies. But I still favor this answer. Thank you again!

[Matt J]

OK, but bear in mind that this solution probably uses more for-loops than all the others, even though they are hidden from you. cell2mat and num2cell are implemented in .m files (MathWorks provided) and if you look inside them, you will see for-loops.

[Matt J]

In fact, if you have a long sequences of small matrices/vectors to convolve, you may have actually chosen the slowest by far of my 3 proposals. See my timing comparison below.

   M=2000;
    N=2000;
   nu=2;
   u=rand(nu,nu,M);
   v=rand(nu,N);

   tic;%METHOD 1 - add up convolutions

       nu=size(u,2);
       result2=0;
           for j=1:nu
             t=squeeze(u(:,j,:));
             result2 = result2 + conv2(t,v(j,:)); 
           end

   toc;
   %Elapsed time is 0.039432 seconds.

   mtimesx SPEED;   %METHOD 2 - using MTIMESX

   tic;

     T=permute(mtimesx(u,v),[1,3,2]);
       map=rot90(reshape(1:M*N,[M,N]));
       d=-(N-1):(M-1);
       L=length(d);
       result1=zeros(2,L);
       for ii= 1:L
           idx=diag(map,d(ii));
           result1(:,ii) = sum(T(:,idx),2);
       end

   toc
   %Elapsed time is 0.312369 seconds.

    tic; %METHOD 3 - using block Toeplitz matrices

      u(:,:,M+1)=0;
       U=num2cell(u,[1,2]);
       L=M+N-1;
       T=toeplitz(1:L,[1,ones(1,N-1)*(M+1)]);
       T(T>M)=M+1;
       result0 = cell2mat(U(T))*v(:);
       result0=reshape(result0,2,[]);
   toc;
   %Elapsed time is 2.615746 seconds.

Answer 2

[Matt J]

Below is a way you could reduce it to 1 loop, using FEX: mtimesx. In my example, I assume that u is 2x2xM and v is 2xN, i.e., u(:,:,i) are the sequence of matrices and v(:,j) are the sequence of vectors.

%%Fake data
 M=5;
 N=4;
 u=repmat(eye(2),[1,1,M]);
 v=ones(2,N);

 %%Engine
 T=permute(mtimesx(u,v),[1,3,2]);

 map=reshape(1:M*N,[M,N]);

 d=-(M-1):(N-1);
 L=length(d);
 result=zeros(2,L);

 for ii= 1:L

     idx=diag(map,d(ii));
     result(:,ii) = sum(T(:,idx),2);

 end

[Heng]

Thank you but, if there must be a loop in the code, I can implement it just by following the definition, then I don't need to ask this question. So I'm not asking how to implement the matrix convolution, I'm asking if there is a function call in MATLAB, or a vectorized implementation without for loop, to compute the matrix convolution.

[Matt J]

No, if you were to follow the definition, it would require 2 loops, one over k and one over j.

Also, you could vectorize the 1 loop I've left for you. I just doubt that it's worth it. The primary hard work (the sequence of matrix-vector multiplications) has been vectorized for you.

Answer 3

[Image Analyst]

Not sure I understand what you're asking. But yes, there is conv(), as you already know, and there are conv2() and convn() as well, that do convolution in 2 or higher dimensions. You can do "sequences of matrices" if your matrices care constructed correctly and you use the proper function.

Answer 4

[Matt J]

Yet another approach and probably the best one, IMO, if you have a long sequence of small matrices. You'll notice that this uses a double for-loop, but the loops are very small since they only run over the dimensions of a single u(:,:,i). This method is also the most memory conservative.

 [mu,nu,ku]=size(u);
 [mv,nv]=size(v);

 L=M+N-1; 
 result=zeros(nu,L);

 for i=1:mu

     c=0;
     for j=1:nu

       t=u(i,j,:);
       c = c + conv(t(:).',v(j,:)); 

     end
     result(i,:)=c;

 end

[Matt J]

Even simpler, and only one small loop (in this case nu=2)!

 nu=size(u,2);

 result=0;

     for j=1:nu

       t=squeeze(u(:,j,:));
       result = result + conv2(t,v(j,:)); 

     end