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 ShermanMorrison formula



Hi:
Given A*x = b, where A is MbyN and of rank N, M >= N, there is
a recursive formula called ShermanMorrison 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 NbyN 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 ShermanMorrison 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 ShermanMorrison 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 MbyN and of rank N, M >= N, there is
a recursive formula called ShermanMorrison 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 NbyN 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 ShermanMorrison formula for M < N.

Let's add some more details. Given A*x = b, where A is MbyN 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 ShermanMorrison 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 MbyN and of rank N, M >= N, there is
a recursive formula called ShermanMorrison 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 NbyN 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 ShermanMorrison formula for M < N.
Thanks,
by Cheng Cosine
Jul/09/2k6 NC

ShermanMorrison 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 ShermanMorrison formula



On 20060710 13:29:50 0300,
spellucci@fb04373.mathematik.tudarmstadt.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 MbyN and of rank N, M >= N, there is
a recursive formula called ShermanMorrison 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 NbyN 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 ShermanMorrison formula for M < N.
Thanks,
by Cheng Cosine
Jul/09/2k6 NC
ShermanMorrison 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.
ShermanMorrison (or the slightly more generalized ShermanMorrisonWoodbury)
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 ShermanMorrison formula



"Peter Spellucci" <spellucci@fb04373.mathematik.tudarmstadt.de> wrote in
message news:e8tv9u$16s$1@fb04373.mathematik.tudarmstadt.de...
Quote:  ...
ShermanMorrison 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 NbyN. Result using SM
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;
% ShermanMorrison formula
C = C1.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 ShermanMorrison formula



Hi:
ShermanMorrison updating/downdating formula works for
add/delete rows for A*x = b, where A is MbyN 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 2by2 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 ShermanMorrison formula



In article <n1_tg.19983$so3.6840@southeast.rr.com>,
"Cheng Cosine" <acosine@spamfree.com> writes:
Quote:  Hi:
ShermanMorrison updating/downdating formula works for
add/delete rows for A*x = b, where A is MbyN 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 2by2 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 ShermanMorrison formula



"Peter Spellucci" <spellucci@fb04373.mathematik.tudarmstadt.de> wrote in
message news:e9g9n5$fpk$1@fb04373.mathematik.tudarmstadt.de...
Quote: 
In article <n1_tg.19983$so3.6840@southeast.rr.com>,
"Cheng Cosine" <acosine@spamfree.com> writes:
Hi:
ShermanMorrison updating/downdating formula works for
add/delete rows for A*x = b, where A is MbyN 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 2by2 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 SchurBanachwiewicz 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'*aa'*AA*B*AA'*a ) = inv( ra'*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 Tue Dec 12, 2017 6:28 am  All times are GMT

