 Forum index » Science and Technology » Math » num-analysis
Author Message
Cheng Cosine
science forum Guru Wannabe

Joined: 26 May 2005
Posts: 168 Posted: Tue Jul 11, 2006 11:27 pm    Post subject: ? LS expression for A*x = b 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 Helmut Jarausch
science forum beginner

Joined: 08 Jul 2005
Posts: 49 Posted: Wed Jul 12, 2006 7:26 am    Post subject: Re: ? LS expression for A*x = b 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 Joined: 08 Oct 2005
Posts: 70 Posted: Wed Jul 12, 2006 8:39 am    Post subject: Re: ? LS expression for A*x = b 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 Cheng Cosine
science forum Guru Wannabe

Joined: 26 May 2005
Posts: 168 Posted: Wed Jul 12, 2006 8:56 am    Post subject: Re: ? LS expression for A*x = b "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 Peter Spellucci
science forum Guru

Joined: 29 Apr 2005
Posts: 702 Posted: Wed Jul 12, 2006 10:14 am    Post subject: Re: ? LS expression for A*x = b 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 ] = 
[ 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  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Wed Mar 27, 2019 2:19 am | 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 Integrate erf type expression Pratim Vakish num-analysis 4 Mon Jul 17, 2006 2:27 pm How to get the analytical PDF of this expression? glare22@gmail.com num-analysis 3 Thu Jul 13, 2006 9:08 am Simplifying Algebraic expression Jeffrey Spoon Math 4 Wed Jul 12, 2006 3:04 pm What is the correct expression in English? pkg Math 4 Sat Jul 08, 2006 1:47 pm Are there any closed-form expression for evaluating predi... comtech Math 1 Tue Jul 04, 2006 8:43 pm