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
? LS expression for A*x = b
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
Author Message
Cheng Cosine
science forum Guru Wannabe


Joined: 26 May 2005
Posts: 168

PostPosted: Tue Jul 11, 2006 11:27 pm    Post subject: ? LS expression for A*x = b Reply with quote

A*x = b and A is M-by-N where M < N.

Its least-squares solution is written as:

xLS = A'*inv(A*A')*b

and this is easy to check A*xLS = A*A'*inv(A*A')*b = b

But how does one derive this when one has no idea how

solution looks like? BTW, I knew this can be expressed using

SVD, which is more general. But I am just curious on how

this expression, xLS = A'*inv(A*A')*b, was derived.

Thanks,
by Cheng Cosine
Jul/11/2k6 NC
Back to top
Helmut Jarausch
science forum beginner


Joined: 08 Jul 2005
Posts: 49

PostPosted: Wed Jul 12, 2006 7:26 am    Post subject: Re: ? LS expression for A*x = b Reply with quote

Cheng Cosine wrote:
Quote:
A*x = b and A is M-by-N where M < N.

Its least-squares solution is written as:

xLS = A'*inv(A*A')*b

that's not true, see below
Quote:

and this is easy to check A*xLS = A*A'*inv(A*A')*b = b

But how does one derive this when one has no idea how

solution looks like? BTW, I knew this can be expressed using

SVD, which is more general. But I am just curious on how

this expression, xLS = A'*inv(A*A')*b, was derived.


The least-squares principles says: minimize

|| A*x - b || where ||.|| denotes the Euclidean norm
Equivalently one can minimize the square of it, which is

(A*x-b)' * (A*x-b)
Now, a necessary condition is that the 1st derivative
must vanish. The first derivative in the directory of
(an arbitrary vector) v is

2*(A*x-b)' * A*v
For this to vanish for all v one must have
(take transposes and divide by 2)
A'*(A*x-b) = 0 or

(A'*A)*x = A'*b or

x= inv(A'*A)*A'*b


--
Helmut Jarausch

Lehrstuhl fuer Numerische Mathematik
RWTH - Aachen University
D 52056 Aachen, Germany
Back to top
Duncan Muirhead
science forum addict


Joined: 08 Oct 2005
Posts: 70

PostPosted: Wed Jul 12, 2006 8:39 am    Post subject: Re: ? LS expression for A*x = b Reply with quote

On Wed, 12 Jul 2006 09:26:58 +0200, Helmut Jarausch wrote:

Quote:
Cheng Cosine wrote:
A*x = b and A is M-by-N where M < N.

Its least-squares solution is written as:

xLS = A'*inv(A*A')*b

that's not true, see below

and this is easy to check A*xLS = A*A'*inv(A*A')*b = b

But how does one derive this when one has no idea how

solution looks like? BTW, I knew this can be expressed using

SVD, which is more general. But I am just curious on how

this expression, xLS = A'*inv(A*A')*b, was derived.


The least-squares principles says: minimize

|| A*x - b || where ||.|| denotes the Euclidean norm
Equivalently one can minimize the square of it, which is

(A*x-b)' * (A*x-b)
Now, a necessary condition is that the 1st derivative
must vanish. The first derivative in the directory of
(an arbitrary vector) v is

2*(A*x-b)' * A*v
For this to vanish for all v one must have
(take transposes and divide by 2)
A'*(A*x-b) = 0 or

(A'*A)*x = A'*b or

x= inv(A'*A)*A'*b


There's also the completing-the-square argument:
assuming A'*A invertible:
(A*x-b)'*(A*x-b) = x'*A'*A*x - 2*x'*A'*b + b'*b
= (x-P*A'b))'*A'*A*(x-P*A'b)) + b'*(I-A*P*A)*b
where P = inv(A'*A)
Since A'*A >=0, the minimising x is P*A'b
Duncan
Back to top
Cheng Cosine
science forum Guru Wannabe


Joined: 26 May 2005
Posts: 168

PostPosted: Wed Jul 12, 2006 8:56 am    Post subject: Re: ? LS expression for A*x = b Reply with quote

"Helmut Jarausch" <jarausch@igpm.rwth-aachen.de> wrote in message
news:4hjmi2F1ruh7jU1@news.dfncis.de...
Quote:
Cheng Cosine wrote:
A*x = b and A is M-by-N where M < N.

Its least-squares solution is written as:

xLS = A'*inv(A*A')*b

that's not true, see below

and this is easy to check A*xLS = A*A'*inv(A*A')*b = b

But how does one derive this when one has no idea how

solution looks like? BTW, I knew this can be expressed using

SVD, which is more general. But I am just curious on how

this expression, xLS = A'*inv(A*A')*b, was derived.


The least-squares principles says: minimize

|| A*x - b || where ||.|| denotes the Euclidean norm
Equivalently one can minimize the square of it, which is

(A*x-b)' * (A*x-b)
Now, a necessary condition is that the 1st derivative
must vanish. The first derivative in the directory of
(an arbitrary vector) v is

2*(A*x-b)' * A*v
For this to vanish for all v one must have
(take transposes and divide by 2)
A'*(A*x-b) = 0 or

(A'*A)*x = A'*b or

x= inv(A'*A)*A'*b


Thanks, but I asked for A*x = b and A is M-by-N where M < N.

When M < N, A'*A is of N-by-N, which is not full-ranked, and therefore

inv(A'*A) does not exist.

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


Joined: 29 Apr 2005
Posts: 702

PostPosted: Wed Jul 12, 2006 10:14 am    Post subject: Re: ? LS expression for A*x = b Reply with quote

In article <8tWsg.19451$so3.8947@southeast.rr.com>,
"Cheng Cosine" <acosine@spamfree.com> writes:
Quote:

A*x = b and A is M-by-N where M < N.

Its least-squares solution is written as:

xLS = A'*inv(A*A')*b

and this is easy to check A*xLS = A*A'*inv(A*A')*b = b

But how does one derive this when one has no idea how

solution looks like? BTW, I knew this can be expressed using

SVD, which is more general. But I am just curious on how

this expression, xLS = A'*inv(A*A')*b, was derived.

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



since A*x=b is underdetermined, you seek the minimum norm least squares solution.
we assume rank(A)=M, otherwise the problem may be unsolvable using the
approach that follows now (and of course in your formula, inv(A'*A) makes no
sense)
we write the problem as
minimize x'*x/2
subject to A*x=b (! observe that we assume compatibility of the
constraints here, hence the rank assumption)
we write down the Lagrange multiplier necessary (and in this convex regular case
sufficient) optimality conditions:

x - A'*lambda = 0 lambda are the Lagrange multipliers for the equality
constraints
A*x = b

or in matrix form

[ I A' ] [x ] = [0]
[ A O ] [-lambda] [b]
now we invert the block matrix using block Gauss elimination which is possible
since I is invertible
[ I A' ] = [ I O ] [ I A' ]
[ A O ] [ A I ] [ O -A*A' ]
inverting the product
inv(...) = [ I A'*(inv(A*A') ] [ I O ]
[ O -inv(A*A') ] [ -A I ]
=
[ I - A'*inv(A*A')*A A'*inv(A*A') ]
[ inv(A*A')*A -inv(A*A') ]
and multiplying this with the right hand side
[ 0 ]
[ b ]
you get your formula for xLS.
but this is not the way this should be computed. you use the QR-decomposition of
A' :
Q*A' = [ R ; O ] and let y=Q'*x = [y1;y2] (matlab notation)
with y1 in R^M.
the y2=0, R'*y1=b is the minimum norm solution and xLS=Q*y.
here you can indeed update, adding roews to A means adding columns to A',
this is even rather easy. but as said already, in your application I see
little sense in considering this.
hth
peter
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Thu Sep 20, 2018 2:12 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 Integrate erf type expression Pratim Vakish num-analysis 4 Mon Jul 17, 2006 2:27 pm
No new posts How to get the analytical PDF of this expression? glare22@gmail.com num-analysis 3 Thu Jul 13, 2006 9:08 am
No new posts Simplifying Algebraic expression Jeffrey Spoon Math 4 Wed Jul 12, 2006 3:04 pm
No new posts What is the correct expression in English? pkg Math 4 Sat Jul 08, 2006 1:47 pm
No new posts Are there any closed-form expression for evaluating predi... comtech Math 1 Tue Jul 04, 2006 8:43 pm

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.0138s ][ Queries: 16 (0.0019s) ][ GZIP on - Debug on ]