|
|
| Author |
Message |
Cheng Cosine
science forum Guru Wannabe
Joined: 26 May 2005
Posts: 168
|
 Posted: Sun Jul 09, 2006 5:13 pm Post subject:
? algorithm to fill out the gap of Sherman-Morrison formula
|
|
|
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, *x_app_1 = b(1:1) => solve x_app_1
A(1:2,*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
|
| Posted: Mon Jul 10, 2006 5:01 am Post subject:
Re: ? algorithm to fill out the gap of Sherman-Morrison formula
|
|
|
"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,*x_app_1 = b(1:1) => solve x_app_1
A(1:2,*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
|
| Posted: Mon Jul 10, 2006 4:29 pm Post subject:
Re: ? algorithm to fill out the gap of Sherman-Morrison formula
|
|
|
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,*x_app_1 = b(1:1) => solve x_app_1
A(1:2,*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
|
| Posted: Mon Jul 10, 2006 5:12 pm Post subject:
Re: ? algorithm to fill out the gap of Sherman-Morrison formula
|
|
|
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,*x_app_1 = b(1:1) => solve x_app_1
A(1:2,*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
|
| Posted: Tue Jul 11, 2006 10:46 pm Post subject:
Re: ? algorithm to fill out the gap of Sherman-Morrison formula
|
|
|
"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,';
C = pinv( w*w' ); % MatLab pseudoinverse command
xRLS = C*( w*b(n) );
for n = 2:1:No
w = A(n,'; % 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
|
| Posted: Sat Jul 15, 2006 4:19 am Post subject:
Re: ? algorithm to fill out the gap of Sherman-Morrison formula
|
|
|
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
|
| Posted: Mon Jul 17, 2006 3:17 pm Post subject:
Re: ? algorithm to fill out the gap of Sherman-Morrison formula
|
|
|
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
|
| Posted: Mon Jul 17, 2006 11:17 pm Post subject:
Re: ? algorithm to fill out the gap of Sherman-Morrison formula
|
|
|
"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 |
|
|
|
|
The time now is Mon Dec 01, 2008 6:08 pm | All times are GMT
|
|
Mortgage | Fantasy Football NFL | Mortgage | Loans | Remortgages
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
num-analysis
