Thread Subject: speeding up matrix algebra

Hi all,
a:
cov=(X'*X)^-1

It takes about <0.00001 seconds

If I run
cova=(X'(Z*((Z'Z)^-1)*Z')*X)

It takes about 2.6 seconds

Where X has dim 10,000 x 10
And Z has dim 10,000 x 11

so that cov X has dim 10 x 10...

Any suggestions on how I could speed up the calculation of cova?

Regards
Hans

"Hans Henrik Sievertsen" <hhsievertsen@gmail.com> wrote in message <ho7ijn$7mu$1@fred.mathworks.com>...
> Hi all,
> a:
> cov=(X'*X)^-1
>
> It takes about <0.00001 seconds
>
> If I run
> cova=(X'(Z*((Z'Z)^-1)*Z')*X)
>
> It takes about 2.6 seconds
>
> Where X has dim 10,000 x 10
> And Z has dim 10,000 x 11
>
> so that cov X has dim 10 x 10...
>
> Any suggestions on how I could speed up the calculation of cova?
>
> Regards
> Hans

For starters:

>> tic;a^-1;toc
Elapsed time is 1.122925 seconds.

>> tic;inv(a);toc
Elapsed time is 0.482904 seconds.

On 22 Mar, 12:00, "Hans Henrik Sievertsen" <hhsievert...@gmail.com>
wrote:
> Hi all,
> a:
> cov=(X'*X)^-1
>
> It takes about <0.00001 seconds
>
> If I run
> cova=(X'(Z*((Z'Z)^-1)*Z')*X)
>
> It takes about 2.6 seconds
>
> Where X has dim 10,000 x 10
> And Z has dim 10,000 x 11
>
> so that cov X has dim 10 x 10...
>
> Any suggestions on how I could speed up the calculation of cova?

1) Compute the SVD of Z.
2) Eliminate terms.
3) See what's left - it shouldn't be much.

My attempt (*don't* trust this!!!):

Z = USV
Z' = V'SU'
V'V = VV' = I
U'U = UU' = I

Z'Z = V'SU'USV = V'S^2 V
(Z'Z)^-1 = V'S^{-2}V
Z(Z'Z)^-1z = USVV'S^{-2}VV'SU' = UU'

If my arithmetics is correct, you only need the left-singular
vectors of Z. Once they have been computed, first compute Y = X'U
and last the cross product C = YY'.

Make sure you call the SVD routine as

[...] = svd(Z,0);

or the computations will take forever.

Rune

"Hans Henrik Sievertsen" <hhsievertsen@gmail.com> wrote in message <ho7ijn$7mu$1@fred.mathworks.com>...

> Any suggestions on how I could speed up the calculation of cova?
=============

Precompute Z'*X and recycle it appropriately in the computations:

tic;
iZtZ=inv(Z'*Z);
ZtX=Z'*X;
cova=(ZtX)'*iZtZ*ZtX;
toc
%Elapsed time is 0.004999 seconds.