John VanSickle <evi### [at] hotmailcom> wrote:
> Just posted this and I was wondering if it's got any serious problems
> (other than lack of examples):
>
> http://www.geocities.com/evilsnack/least_squares.pdf
>
> In other news, OpenOffice's formula editor is rather nifty.

I can find no errors, and I read it over fairly carefully.  I don't know who
your audience is, but it couldn't hurt to emphasize that (2) is a sort of total
error to be minimized, and to see the resulting matrix equations put together at
the end.  Of course neither of these things are really necessary.

Since you had us proofread it though, it's my turn to rant about least squares.
Perhaps you know this already, but I'm just enjoying the review out loud.  This
is the derivation I had always seen, but last fall I was introduced to a neat
alternative version:

Think of a point lying off a line.  (Not a data point, but instead a point in
the space of the coefficients you're trying to determine.)  How close along the
line can we get to that point?  Well, 'squares' just means Euclidian distance,
so it's along a second line perpendicular to the first, of course.

So if it's a linear problem in the coefficients, the residual is just

r = b-Ax,

 where A is a matrix full of the basis functions evaluated at all points, x is
the unknown coefficients, and b is the data points.  A does not need to be
square!  In fact it will be m x n, where m is the number of data points and n
is the number of basis functions.

If the problem is solved, then the length of r has been minimized so that Ax is
as close to b as possible.  This corresponds to the situation above where we
can't actually get the point onto the line, so instead we have to wander off
perpendicular to the line until we hit a point we can use.  It turns out the
condition for orthogonality is

A* r = 0,

where * is just an adjoint (or transpose), and plugging in r,

A* A x = A* b

Solving for x,

x = (A* A)^(-1) A* b

Holy cow!  ((A* A)^(-1) A*) fits into the equation just like an A^(-1) would if
it weren't a least squares problem!  That's why it's called the pseudoinverse.
Of course, you should always avoid solving this equation (the Normal Equations)
directly for a robust implementation and should instead use a QR or SVD
factorization, both of which are much more stable.

Sorry.  Been a while, but I always that was a pretty neat idea.

 - Ricky

Post a reply to this message