Thread Subject: usage of inv(K+a*I) to find inv(K)

Hi,
I am dealing with huge matrices (> 2000: square matrix).
It's also symmetric.

I have to find inv(K + a*I) and inv(K) at two different steps. where a= constant, I =identity matrix and K is the semivariogram(or assume covariance) of size >= 2000X2000.

I used 'SCHUR COMPLEMENT' to decrease the computation time.
Can I use anything or replicate any value from inv(K+A)(by schur complement) to find inv(K)?

or, is there anything else to make it faster.
p.s. '\' operator gave slight change in time.

"vineet " <vin_rajput2005@yahoo.com> wrote in message <jejftg$dop$1@newscl01ah.mathworks.com>...
> Hi,
> I am dealing with huge matrices (> 2000: square matrix).
> It's also symmetric.
>
> I have to find inv(K + a*I) and inv(K) at two different steps. where a= constant, I =identity matrix and K is the semivariogram(or assume covariance) of size >= 2000X2000.
>
> I used 'SCHUR COMPLEMENT' to decrease the computation time.
> Can I use anything or replicate any value from inv(K+A)(by schur complement) to find inv(K)?
>
> or, is there anything else to make it faster.
> p.s. '\' operator gave slight change in time.

You could simply perform eigen-value decomposition of K (take about 8 secs on my computer). Afteward inversions (for both matrices) are almost instantaneous.

The Schur's decomposition also works, but it takes 22 secs.

Bruno

Thanks,
but its not working. MSE is increased.
in my computer, SCHUR COMPLEMENT is only taking 3.8 sec(+(-) .4). (matrix size- 2000x2000)

the IMPORTANT thing is: I have the result of inv(K + a*I). Can i use this result to find inv(K) so that, i dont have to calculate it again.

"vineet " <vin_rajput2005@yahoo.com> wrote in message <jejjr4$olm$1@newscl01ah.mathworks.com>...

>
> the IMPORTANT thing is: I have the result of inv(K + a*I). Can i use this result to find inv(K) so that, i dont have to calculate it again.

In general no. This issue is confronted daily by people who search for optimal regularization parameter (a). I don't believe seeing any short cut without simplifying the problem.

Note that Schur's decomposition is no related to Schur's complement.

Bruno

yes i know its not equivalent to decomposition.
the result with schur complement is better than schur decomposition w.r.t time and MSE.

approximations can be used to use the result but that works only with small a. its not general.
anyways thanks for the replies. :)

"vineet " <vin_rajput2005@yahoo.com> wrote in message <jejl68$sdl$1@newscl01ah.mathworks.com>...
> yes i know its not equivalent to decomposition.
> the result with schur complement is better than schur decomposition w.r.t time and MSE.
>
> approximations can be used to use the result but that works only with small a. its not general.
> anyways thanks for the replies. :)

Hello,

if you had used the eigenvalue decomposition (I know, takes a while),

[V,S] = eig(K+a*I);

K+a*I = V*S*inv(V);
inv(K+a*I) = V*inv(S)*inv(V);
and inv(K) = V*inv(S-a*I)*inv(V);

S is easy to invert since S is diagonal. If K is symmetric,inv(V) is transpose V.

I hope i have understood you correctly.
J.

its working and MSE is exactly the same.
But the time is increased to 120 secs XD

and thanks for the information that inv(V) is equal to V' if K is symmetric. It will help me a lot. :)

"vineet " <vin_rajput2005@yahoo.com> wrote in message <jek1c9$49p$1@newscl01ah.mathworks.com>...
>
> and thanks for the information that inv(V) is equal to V' if K is symmetric. It will help me a lot. :)

Mathematically inv(V) = V', if V does not have multiple-order eigenvalue. No such equality is ensured otherwise.

However in my experience Matlab EIG() always returns orthogonal. I don't thing this property is officially documented (?) by TMW.

Bruno