 Forum index » Science and Technology » Math » num-analysis
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 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

Thanks,
by Cheng Cosine
Jul/10/2k6 NC 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 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 , "Cheng Cosine" 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. 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
 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

>> 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 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 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
 Quote: In article , "Cheng Cosine" 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  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Wed Mar 20, 2019 8:02 pm | All times are GMT Forum index » Science and Technology » Math » num-analysis
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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