Matt J
Posts:
4,996
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/25969efficientobjectorientedkroneckerproductmanipulation
In your case, this would lead to
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!

