Faster projected-norm (quadratic-form, metric-matrix...) style computations

I need to perform lots of evaluations of the form

X(:,i)' * A * X(:,i)   i = 1...n

where X(:,i) is a vector and A is a symmetric matrix. Ostensibly, I can either do this in a loop

for i=1:n
    z(i) = X(:,i)' * A * X(:,i)
end

which is slow, or vectorise it as

z = diag(X' * A * X)

which wastes RAM unacceptably when X has a lot of columns. Currently I am compromising on

Y = A * X
for i=1:n
    z(i) = Y(:,i)' * X(:,i)
end

which is a little faster/lighter but still seems unsatisfactory.

I was hoping there might be some matlab/scilab idiom or trick to achieve this result more efficiently?

Answers


Try this in MATLAB:

z = sum(X.*(A*X));

This gives results equivalent to Federico's suggestion using the function DOT, but should run slightly faster. This is because the DOT function internally computes the result the same way as I did above using the SUM function. However, DOT also has additional input argument checks and extra computation for cases where you are dealing with complex numbers, which is extra overhead you probably don't want or need.

A note on computational efficiency:

Even though the time difference is small between how fast the two methods run, if you are going to be performing the operation many times over it's going to start to add up. To test the relative speeds, I created two 100-by-100 matrices of random values and timed the two methods over many runs to get an average execution time:

    METHOD        AVERAGE EXECUTION TIME
--------------------------------------------
Z = sum(X.*Y);        0.0002595 sec
Z = dot(X,Y);         0.0003627 sec

Using SUM instead of DOT therefore reduces the execution time of this operation by about 28% for matrices with around 10,000 elements. The larger the matrices, the more negligible this difference will be between the two methods.

To summarize, if this computation represents a significant bottleneck in how fast your code is running, I'd go with the solution using SUM. Otherwise, either solution should be fine.


Try this:

z = dot(X, A*X)

I don't have Matlab here to test, but it works on Octave, so I expect Matlab to have an analogous dot() function.

From Octave's help:

  -- Function File:  dot (X, Y, DIM)
     Computes the dot product of two vectors. If X and Y are matrices,
     calculate the dot-product along the first non-singleton dimension.
     If the optional argument DIM is given, calculate the dot-product
     along this dimension.

For completeness, gnovice's answer in Scilab would be

z = sum(X .* Y, 1)'

Need Your Help

ImageMagick extend canvas with transparent background

background imagemagick png transparency

convert input.png -extent 100x100 -gravity center -background white output.png

Uncaught TypeError: Cannot read property 'children' of undefined

javascript jquery

I need to get href property of all a elements under a all divs of specified class. There is no problem when i hande just one div but when the number of divs increase i get the error on the title of