Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Least Squares for Linear Equations

Date: 06/06/2012 at 10:41:50
From: gul
Subject: Least Square Method

How does the least squares solution take you from an over-determined
system of equations to an exactly determined one?



Date: 06/07/2012 at 10:23:18
From: Doctor George
Subject: Re: Least Square Method

Hi gul,

Thanks for writing to Doctor Math. 

This is a great question!

Assuming that you have in mind linear least squares, consider this
over-determined system of equations:

    -      - - -   -  -
    |ux  vx| |a|   |px|
    |uy  vy| |b| = |py|
    |uz  vz| - -   |pz|
    -      -       -  -

I chose this example because we can interpret it in ordinary 3D space. On
the right-hand side, we have a matrix composed of two 3D column vectors, u
and v, which we will assume are non-collinear.

We can rewrite it like this:

    -  -    -  -   -  -
    |ux|    |vx|   |px|
   a|uy| + b|vy| = |py|
    |uz|    |vz|   |pz|
    -  -    -  -   -  -

We are looking for a linear combination of u and v that gives us point p.
But there can only be a solution if p is in the plane formed by u and v.

If there is no solution, then the least squares solution will be when the
difference between the left- and right-hand sides is the shortest possible
vector. In other words, we are looking for the point on that plane that is
closest to p, which is the projection of p onto that plane. There will
only be one such point, so the least squares solution will be unique, or
exactly determined.

Now let r be the vector that represents the difference between the left-
and right-hand sides.

    -  -    -  -    -  -   -  -
    |rx|    |ux|    |vx|   |px|
    |ry| = a|uy| + b|vy| - |py|
    |rz|    |uz|    |vz|   |pz|
    -  -    -  -    -  -   -  -

Making r as short as possible means that it will be perpendicular to the
plane formed by u and v for the best choice of a and b. Making r
perpendicular to the plane means that it is perpendicular to both u and v.
This means that we want

    -          - -  -
    |ux  uy  uz| |rx|
    |vx  vy  vz| |ry| = 0
    -          - |rz|
                 -  - 

Now substitute for r in this equation and re-arrange the terms to get

    -          - -      - - -   -          - -  -
    |ux  uy  uz| |ux  vx| |a|   |ux  uy  uz| |px|
    |vx  vy  vz| |uy  vy| |b| = |vx  vy  vz| |py|
    -          - |uz  vz| - -   -          - |pz|
                 -      -                    -  -

This equation is normally written with transpose notation. On the
left-hand side, we get a 2x2 matrix that is invertible. So the linear
algebra representation will produce the unique solution.

The projection operation has reduced the number of dimensions in the
problem by one, and that is what we needed to go from being over-
determined to uniquely determined.

The same principles apply for higher dimension problems.

Does that make sense? Write again if you need more help.

- Doctor George, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Linear Equations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/