FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » num-analysis
? algorithm to fill out the gap of Sherman-Morrison formula
Post new topic   Reply to topic Page 1 of 1 [8 Posts] View previous topic :: View next topic
Author Message
Cheng Cosine
science forum Guru Wannabe


Joined: 26 May 2005
Posts: 168

PostPosted: Sun Jul 09, 2006 5:13 pm    Post subject: ? algorithm to fill out the gap of Sherman-Morrison formula Reply with quote

Hi:

Given A*x = b, where A is M-by-N and of rank N, M >= N, there is

a recursive formula called Sherman-Morrison formula to give LS soln

when a new observation w'*x = beta is added.

My question is that are there any similar approaches like the formula

above that solves A*x = b, where A is N-by-N and of rank N, by

gradually increasing row info of A. That is:

A(1:1,Smile*x_app_1 = b(1:1) => solve x_app_1

A(1:2,Smile*x_app_2 = b(1:2) => solve x_app_2 with the aid of x_app_1

and so on, until true soln A*x = b is determined. Or one can think of the

algorithm to fill out the gap of Sherman-Morrison formula for M < N.

Thanks,
by Cheng Cosine
Jul/09/2k6 NC
Back to top
Cheng Cosine
science forum Guru Wannabe


Joined: 26 May 2005
Posts: 168

PostPosted: Mon Jul 10, 2006 5:01 am    Post subject: Re: ? algorithm to fill out the gap of Sherman-Morrison formula Reply with quote

"Cheng Cosine" <acosine@spamfree.com> wrote in message
news:TOasg.19232$so3.4410@southeast.rr.com...
Quote:
Hi:

Given A*x = b, where A is M-by-N and of rank N, M >= N, there is

a recursive formula called Sherman-Morrison formula to give LS soln

when a new observation w'*x = beta is added.

My question is that are there any similar approaches like the formula

above that solves A*x = b, where A is N-by-N and of rank N, by

gradually increasing row info of A. That is:

A(1:1,Smile*x_app_1 = b(1:1) => solve x_app_1

A(1:2,Smile*x_app_2 = b(1:2) => solve x_app_2 with the aid of x_app_1

and so on, until true soln A*x = b is determined. Or one can think of the

algorithm to fill out the gap of Sherman-Morrison formula for M < N.


Let's add some more details. Given A*x = b, where A is M-by-N and M >= N,

we have recursive formula to determine its LS solution when new rows/columns

are added/deleted. But how about the cases when M < N but new rows/columns

are added/deleted?

Thanks,
by Cheng Cosine
Jul/10/2k6 NC
Back to top
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

PostPosted: Mon Jul 10, 2006 4:29 pm    Post subject: Re: ? algorithm to fill out the gap of Sherman-Morrison formula Reply with quote

In article <TOasg.19232$so3.4410@southeast.rr.com>,
"Cheng Cosine" <acosine@spamfree.com> writes:
Quote:
Hi:

Given A*x = b, where A is M-by-N and of rank N, M >= N, there is

a recursive formula called Sherman-Morrison formula to give LS soln

when a new observation w'*x = beta is added.

My question is that are there any similar approaches like the formula

above that solves A*x = b, where A is N-by-N and of rank N, by

gradually increasing row info of A. That is:

A(1:1,Smile*x_app_1 = b(1:1) => solve x_app_1

A(1:2,Smile*x_app_2 = b(1:2) => solve x_app_2 with the aid of x_app_1

and so on, until true soln A*x = b is determined. Or one can think of the

algorithm to fill out the gap of Sherman-Morrison formula for M < N.

Thanks,
by Cheng Cosine
Jul/09/2k6 NC



Sherman-Morrison updating concerns the pdating of an invertible matrix.
in principle you could start with a noninvertible system, but then you need to
define which solution you want to update: the minimum norm least squares solution?
I think there is no much to be gained in doing this.
hth
peter
Back to top
Gordon Sande
science forum beginner


Joined: 11 May 2005
Posts: 48

PostPosted: Mon Jul 10, 2006 5:12 pm    Post subject: Re: ? algorithm to fill out the gap of Sherman-Morrison formula Reply with quote

On 2006-07-10 13:29:50 -0300,
spellucci@fb04373.mathematik.tu-darmstadt.de (Peter Spellucci) said:

Quote:

In article <TOasg.19232$so3.4410@southeast.rr.com>,
"Cheng Cosine" <acosine@spamfree.com> writes:
Hi:

Given A*x = b, where A is M-by-N and of rank N, M >= N, there is

a recursive formula called Sherman-Morrison formula to give LS soln

when a new observation w'*x = beta is added.

My question is that are there any similar approaches like the formula

above that solves A*x = b, where A is N-by-N and of rank N, by

gradually increasing row info of A. That is:

A(1:1,Smile*x_app_1 = b(1:1) => solve x_app_1

A(1:2,Smile*x_app_2 = b(1:2) => solve x_app_2 with the aid of x_app_1

and so on, until true soln A*x = b is determined. Or one can think of the

algorithm to fill out the gap of Sherman-Morrison formula for M < N.

Thanks,
by Cheng Cosine
Jul/09/2k6 NC



Sherman-Morrison updating concerns the pdating of an invertible matrix.
in principle you could start with a noninvertible system, but then you need to
define which solution you want to update: the minimum norm least
squares solution?
I think there is no much to be gained in doing this.
hth
peter

Updating of Least Squares solutions is usually done by updating a QR
decomposition. See Ake Bjorck's book which is published by SIAM.

You seem to be hinting at pseudo inverses. Again, see Bjorck.

Sherman-Morrison (or the slightly more generalized Sherman-Morrison-Woodbury)
is for matrix inverses whch have been modified, as Peter says, but that is
a different problem. They are both updating and linear algebra but otherwise
you have just confused things by explicitly asking for a method in the
wrong context. Nice example of where a little knowledge has been harmful.
Back to top
Cheng Cosine
science forum Guru Wannabe


Joined: 26 May 2005
Posts: 168

PostPosted: Tue Jul 11, 2006 10:46 pm    Post subject: Re: ? algorithm to fill out the gap of Sherman-Morrison formula Reply with quote

"Peter Spellucci" <spellucci@fb04373.mathematik.tu-darmstadt.de> wrote in
message news:e8tv9u$16s$1@fb04373.mathematik.tu-darmstadt.de...
Quote:
...
Sherman-Morrison updating concerns the pdating of an invertible matrix.
in principle you could start with a noninvertible system, but then you
need to
define which solution you want to update: the minimum norm least squares
solution?
I think there is no much to be gained in doing this.
hth


Well, not really. See the MatLab script using that formula to solve for A*x
= b by

gradually adding rows so that A finally becomes N-by-N. Result using S-M
formula

does not matach x = inv(A)*b.

by Cheng Cosine
Jul/11/2k6 NC

************* The code ************

No = 5; A = magic(No);
x = linspace(1,No,No)';
b = A*x;

% test for adding row
n = 1;
w = A(n,Smile';
C = pinv( w*w' ); % MatLab pseudoinverse command
xRLS = C*( w*b(n) );

for n = 2:1:No
w = A(n,Smile'; % add new row
u = C*w;

% Sherman-Morrison formula
C = C-1.0E0/( 1.0E0+w'*u )*u*u'; % update C
KalmanGain = ( b(n)-w'*xRLS ); % scalar
xRLS = xRLS+KalmanGain*C*w; % update x
n
xRLS
end % n loop


******** The outputs **************

n =

2


xRLS =

2.9873
4.2174
0.1757
1.4058
2.6359


n =

3


xRLS =

3.5448
5.0045
0.2085
1.6682
3.1278


n =

4


xRLS =

3.7206
5.2526
0.2189
1.7509
3.2829


n =

5


xRLS =

3.7243
5.2578
0.2191
1.7526
3.2861

>>
Back to top
Cheng Cosine
science forum Guru Wannabe


Joined: 26 May 2005
Posts: 168

PostPosted: Sat Jul 15, 2006 4:19 am    Post subject: Re: ? algorithm to fill out the gap of Sherman-Morrison formula Reply with quote

Hi:

Sherman-Morrison updating/downdating formula works for

add/delete rows for A*x = b, where A is M-by-N and M >= N.

But how about deleting an existing COLUMN for A when M >=N?

I tried the following approach but got stop and did not how to proceed. :(

Let C = A^H*A, then we look for downdating formula for inv(C).

Let A_j = [A_(j+1), h] so that the downdated matrix A_(j+1) have one

fewer column than original matrix A_j.

inv(C_j) = inv( A_j^H*A_j ) = inv( [A_(j+1), h]^H*[A_(j+1), h] )

= inv( [A_(j+1)^H*A_(j+1), A_(j+1)^H*h; h^H*A_(j+1), h^H*h] )

Here MatLab notation is used, e.g., for a 2-by-2 matrix it is denoted as:

A = [a_11, a_12; a_21, a22]

We get inv(C_j) = inv( [C_(j+1), A_(j+1)^H*h; h^H*A_(j+1), h^H*h] )

Then I don't know how to proceed. Can anyone help?

Thanks,
by Cheng Cosine
Jul/15/2k6 NC
Back to top
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

PostPosted: Mon Jul 17, 2006 3:17 pm    Post subject: Re: ? algorithm to fill out the gap of Sherman-Morrison formula Reply with quote

In article <n1_tg.19983$so3.6840@southeast.rr.com>,
"Cheng Cosine" <acosine@spamfree.com> writes:
Quote:
Hi:

Sherman-Morrison updating/downdating formula works for

add/delete rows for A*x = b, where A is M-by-N and M >= N.

But how about deleting an existing COLUMN for A when M >=N?

I tried the following approach but got stop and did not how to proceed. :(

Let C = A^H*A, then we look for downdating formula for inv(C).

Let A_j = [A_(j+1), h] so that the downdated matrix A_(j+1) have one

fewer column than original matrix A_j.

inv(C_j) = inv( A_j^H*A_j ) = inv( [A_(j+1), h]^H*[A_(j+1), h] )

= inv( [A_(j+1)^H*A_(j+1), A_(j+1)^H*h; h^H*A_(j+1), h^H*h] )

Here MatLab notation is used, e.g., for a 2-by-2 matrix it is denoted as:

A = [a_11, a_12; a_21, a22]

We get inv(C_j) = inv( [C_(j+1), A_(j+1)^H*h; h^H*A_(j+1), h^H*h] )

Then I don't know how to proceed. Can anyone help?

Thanks,
by Cheng Cosine
Jul/15/2k6 NC



what you mean: how to compute (A'*A)^{-1} after deleting a column in A:
this is just reverse to the process of adding a column
(application of these methods is discouraged because of numerical instability.
better use QR for A and get , if really needed (in most cases it is _not_
needed) inv(A'*A) as inv(R)'*inv(R)

but to be explicit:
you first make the column to be deleted the last one. this amounts to a
symmetric permutation of the given (large) inverse. We name the column to be
deleted a , the right lower (n,n) element of the given inverse 1/r
the matrix A being
A=[ AA , a]

then
inv(A'*A) = [ B + B*AA'*a*a'*AA*B/r , -B*AA'*a/r ; -a'*AA*B/r , 1/r ]

= [ C , c ; c' , gamma ]
(IN MATLAB NOTATION)
and you get
B = inv(AA'*AA) = C -c*c'/gamma ;


from this .

hth
peter
Back to top
Cheng Cosine
science forum Guru Wannabe


Joined: 26 May 2005
Posts: 168

PostPosted: Mon Jul 17, 2006 11:17 pm    Post subject: Re: ? algorithm to fill out the gap of Sherman-Morrison formula Reply with quote

"Peter Spellucci" <spellucci@fb04373.mathematik.tu-darmstadt.de> wrote in
message news:e9g9n5$fpk$1@fb04373.mathematik.tu-darmstadt.de...
Quote:

In article <n1_tg.19983$so3.6840@southeast.rr.com>,
"Cheng Cosine" <acosine@spamfree.com> writes:
Hi:

Sherman-Morrison updating/downdating formula works for

add/delete rows for A*x = b, where A is M-by-N and M >= N.

But how about deleting an existing COLUMN for A when M >=N?

I tried the following approach but got stop and did not how to proceed.
:(

Let C = A^H*A, then we look for downdating formula for inv(C).

Let A_j = [A_(j+1), h] so that the downdated matrix A_(j+1) have one

fewer column than original matrix A_j.

inv(C_j) = inv( A_j^H*A_j ) = inv( [A_(j+1), h]^H*[A_(j+1), h] )

= inv( [A_(j+1)^H*A_(j+1), A_(j+1)^H*h; h^H*A_(j+1), h^H*h] )

Here MatLab notation is used, e.g., for a 2-by-2 matrix it is denoted as:

A = [a_11, a_12; a_21, a22]

We get inv(C_j) = inv( [C_(j+1), A_(j+1)^H*h; h^H*A_(j+1), h^H*h] )

Then I don't know how to proceed. Can anyone help?

Thanks,
by Cheng Cosine
Jul/15/2k6 NC



what you mean: how to compute (A'*A)^{-1} after deleting a column in A:
this is just reverse to the process of adding a column
(application of these methods is discouraged because of numerical
instability.
better use QR for A and get , if really needed (in most cases it is _not_
needed) inv(A'*A) as inv(R)'*inv(R)

but to be explicit:
you first make the column to be deleted the last one. this amounts to a
symmetric permutation of the given (large) inverse. We name the column to
be
deleted a , the right lower (n,n) element of the given inverse 1/r
the matrix A being
A=[ AA , a]

then
inv(A'*A) = [ B + B*AA'*a*a'*AA*B/r , -B*AA'*a/r ; -a'*AA*B/r , 1/r ]

= [ C , c ; c' , gamma ]
(IN MATLAB NOTATION)

Don't get teh aboive. According to Schur-Banachwiewicz inverse formula, one
shpuld have:

inv(A'*A) = [ B + B*AA'*a**inv(S)*a'*AA*B , -B*AA'*a*inv(S)
; -inv(S)*a'*AA*B , inv(S) ]

inv(S) = inv( a'*a-a'*AA*B*AA'*a ) = inv( r-a'*AA*inv(AA'*AA)*AA'*a )

don't see why you have inv(S) = 1/r


Quote:
and you get
B = inv(AA'*AA) = C -c*c'/gamma ;


Totally lost. How did you get B = inv(AA'*AA) = C -c*c'/gamma from

inv(A'*A) = [ B + B*AA'*a*a'*AA*B/r , -B*AA'*a/r ; -a'*AA*B/r , 1/r ]

= [ C , c ; c' , gamma ]

Thanks,
by Cheng Cosine
Jul/17/2k6 NC
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [8 Posts] View previous topic :: View next topic
The time now is Tue Dec 12, 2017 6:28 am | All times are GMT
Forum index » Science and Technology » Math » num-analysis
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am
No new posts Stumped with figuring a formula... moriman Recreational 8 Mon Jul 17, 2006 12:21 am
No new posts Name of algorithm for pairwise comparison ? Paul Nutteing Math 10 Fri Jul 14, 2006 6:55 am
No new posts Need an algorithm Dave111 Math 4 Fri Jul 14, 2006 2:19 am
No new posts Newton's formula kunzmilan@atlas.cz Math 0 Thu Jul 13, 2006 11:12 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0257s ][ Queries: 16 (0.0038s) ][ GZIP on - Debug on ]