COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### kron product of multiple vectors OR continued kron product

• Follow

```lets say i have 4 vectors {x1, x2, x3, x4} and i m interested in the
following quantity

v = kron(x1, kron(x2, kron(x3, x4))))

which is easy to write down for a small number of vectors but how can
one generalize this?

the following is a solution using for loop:

x = rand(2,4); % 4 vectors each of length 2
v = kron(x(:,3), x(:,4));
for n=1:2
v = kron(x(:,3-n), v);
end
v - kron(x(:,1), kron(x(:,2), kron(x(:,3), x(:,4)))) % check

is there any other way?

the order of the kron products is important of course.
```
 0
Reply awimagic (10) 10/22/2011 1:32:14 AM

```What's wrong using the for-loop?

Bruno
```
 0
Reply b.luong5955 (6336) 10/22/2011 8:38:12 AM

```Here is a vectorized engine, but honestly I don't see the point of insisting on vectorization:

% Random data
x1 = ceil(5*rand(1,3))
x2 = ceil(5*rand(1,2))
x3 = ceil(5*rand(1,4))

X1 = kron(x1,kron(x2,x3))

% Vectorize engine
x={x1 x2 x3};
n=length(x);
c = cell(size(x));
[c{:}]=ndgrid(x{end:-1:1});
c = cat(n+1,c{:});
X2 = reshape(prod(c,n+1),1,[])

isequal(X1,X2)

% Bruno
```
 0
Reply b.luong5955 (6336) 10/22/2011 12:45:17 PM

```On 22 Okt., 14:45, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Here is a vectorized engine, but honestly I don't see the point of insisting on vectorization:
>
> % Random data
> x1 = ceil(5*rand(1,3))
> x2 = ceil(5*rand(1,2))
> x3 = ceil(5*rand(1,4))
>
> X1 = kron(x1,kron(x2,x3))
>
> % Vectorize engine
> x={x1 x2 x3};
> n=length(x);
> c = cell(size(x));
> [c{:}]=ndgrid(x{end:-1:1});
> c = cat(n+1,c{:});
> X2 = reshape(prod(c,n+1),1,[])
>
> isequal(X1,X2)
>
> % Bruno

Hi,

the  v = kron(x1, kron(x2, kron(x3, x4))))  is a typical recursive
problem.
You can write a recursive function, which calculates your result. But
it probably wouldn't really be faster.
Since you have a working solution, I'm not sure it would be worthwile.

Here's the wikipedia article on recursion :
http://en.wikipedia.org/wiki/Recursion_%28computer_science%29

And here's the pseusocode for a recursive implementation of the
factorial function, just as an example:

factorial(n)
if (n <= 1)
return 1;
else
return n * factorial(n-1);

```
 0

```Awhan Patnaik <awimagic@gmail.com> wrote in message <64ee5575-c0f8-4faf-bbb5-db488ed49654@k13g2000prg.googlegroups.com>...
> lets say i have 4 vectors {x1, x2, x3, x4} and i m interested in the
> following quantity
>
> v = kron(x1, kron(x2, kron(x3, x4))))
>
> which is easy to write down for a small number of vectors but how can
> one generalize this?
==============

Consider not expanding out the kronecker product at all (unless you really need to) using this tool:

http://www.mathworks.com/matlabcentral/fileexchange/25969-efficient-object-oriented-kronecker-product-manipulation

In your case it would be

v=KronProd({x4,x3,x2,x1});

If you really need to, you can expand it using
full(v) or sparse(v), as appropriate. This will use a for-loop, but like Bruno says, I don't see why vectorizing is preferable.
```
 0
Reply mattjacREMOVE (3177) 10/22/2011 5:19:13 PM

```The fastest is for-loop using matrix product:

n = 10;
m = 5;
x = rand(m,n); % 10 vectors of length 5

tic
X1 = 1;
for k=1:size(x,2)
X1 = kron(X1,x(:,k));
end
toc

% Fastest method
tic
X2 = 1;
for k=1:size(x,2)
X2 = x(:,k)*X2;
X2 = X2(:)';
end
X2 = X2';
toc

% Bruno
```
 0
Reply b.luong5955 (6336) 10/22/2011 7:15:28 PM

```thanks for the answers and comments. nothing wrong with the for loop
as it gets the job done. just wanted to see if any alternate approach
was possible. thanks again.
```
 0
Reply awimagic (10) 10/23/2011 4:32:54 AM

6 Replies
43 Views

5/18/2013 4:55:48 PM