Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Efficiently computing large numbers of vector norms
Replies: 16   Last Post: Nov 15, 2012 8:32 AM

 Messages: [ Previous | Next ]
 Matt J Posts: 4,997 Registered: 11/28/09
Re: Efficiently computing large numbers of vector norms
Posted: Nov 8, 2012 8:05 PM

"Harry Commin" wrote in message <k7elhj\$as1\$1@newscl01ah.mathworks.com>...
> I am frequently faced with problems where I need to find the norm (squared) of row vectors having the following structure:
>
> A(:,i)'*X
>
> where A is (N x Q) complex, and solutions must be found for all i = 1,2,...,Q. Doing this efficiently turns out to be extraordinarily important in my code. In this simple case, I find the following to be pretty swift (compared to a for loop):
>
> sum(abs(A'*X).^2,2)
>
> However, I become stumped with a slightly more complicated case:
>
> kron(A1(:,i),A2(:,j))'*X2

So first, you could do this simultaneously for all i and j without looping by reorganizing as follows

result = sum( abs( kron(A1',A2')*X2 ).^2 , 2) ;

As Bruno says, though, efficient algorithms are available for matrix multiplications with a Kronecker product and my KronProd class implements them,

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

result = sum( abs( KronProd(A2',A1')*X2 ).^2 , 2) ;

Note also that if X also happens to be a Kronecker product,

X2= kron(XX2,XX1);

then the whole thing gets even simpler/faster

rownorms = @(M) sum(abs(M).^2);

result=kron(rownorms(A2'*XX2) , rownorms(A1'*XX1));

>
> where now a fast solution is needed for all i = 1,2,...,Q1 and j = 1,2,...,Q2. Here, I resort to:
>
> Z = zeros(Q1,Q2);
> for j = 1:Q2
> Z(:,j) = sum(abs(kron(A1,A2(:,j))'*X2).^2,2);
> end
>
> Is there a neat way to speed this up? Is there a way to further speed up my sum(abs(A'*X).^2,2)? Efficiency really is critical here!

Date Subject Author
11/7/12 Harry Commin
11/7/12 Harry Commin
11/8/12 Teja Muppirala
11/8/12 Teja Muppirala
11/8/12 Bruno Luong
11/8/12 Matt J
11/9/12 Matt J
11/12/12 Harry Commin
11/12/12 Harry Commin
11/13/12 Matt J
11/13/12 Harry Commin
11/13/12 Matt J
11/13/12 Harry Commin
11/13/12 Matt J
11/14/12 Harry Commin
11/15/12 Harry Commin
11/15/12 Matt J