Least Squares Solutions:

Introduction

Dr. Morley, the world-renowned scientist who discovered the secret of gravity, has been working on his new invention: the gravity laser!

The laser shoots a beam of energy that disintegrates everything in its path... but more than that, it creates a gravitational force on everything within a certain range of any point on the beam, thus pulling them in and disintegrating them! Just as he is putting the finishing touches on his gravity laser, the power in his laboratory goes out... "What's going on?" He asks himself. He looks through his telescope

and sees magnetized asteroids heading for the earth at the speed of sound!

"What am I to do?" He asks himself. "Hm... Well, the asteroids seem to be in a straight line, but it's not exact. I know that I can find an approximate solution to Ax=b by using least squares solution so I could probably find the least squares solution with the minimal mean square error. I could then fire the gravity laser along that line." "When juxtaposed onto a coordinate plane with the Earth as the origin, the asteroids, based on astronomical units (AUs) have the coordinates (1,0), (2,3), (3,7), (4,14), and (5,22). I'll just put that into Math Lab... OH NO!!!!!! Math Lab is disabled! I must do it by hand!"

Chapter 1

"How do I do LSS again?... I know that |Axo-b|^2 <= |Ax-b|^2 for all x..." "But how do I get this?"

Proof

Therefore, (A^T)Axo = (A^T)b. The least squares solution to the problem is xo = (A^T A)^-1(A^T)b. All I have done is transformed the unsolvable system into a solvable one to find an approximate solution.

Back to Saving the World

Since the points are (1,0), (2,3), (3,7), (4,14), and (5,22), and I'm trying to model a best-fit line of the form y=ax+b, or in other words...

Chapter 2

Just as Dr. Morley was about to fire his laser... he realized that he didn't have enough power in his laser to pull every asteroid into the beam! He thought some more, then came up with the solution. "I bet these asteroids follow a quadratic pattern instead of a linear one."

The Quadratic Fit

Okay, well since we want to get this right, let's remain calm in the face of impending doom and try a quadratic fit with y = a + bx + cx^2

Proof that the Quadratic Best-Fit Line is Better

Chapter 3

With his new quadratic linear regression line of best fit, Morley sends up faux-black holes to bend light of the laser... This creates a more accurate fit to the asteroids with minimal error, so the gravity laser works and Morley saves the day!!

Of Note: A Shortcut (to Save the World even Faster!)

If you can use the Gram-Schmidt method to make the columns of A orthonormal or if you QR factorize matrix A, the problem becomes much more simple because QRx=b can be solved by Q^TQRx=Q^Tb, but Q^TQ = I (the identity matrix) because Q is orthonormal, so the least squares solution is merely Rx=Q^Tb. Also, if matrix A is rank deficient (meaning that the rank of A is less than the number of columns of A), then you only need to use the pivot columns for matrix A rather than the entire system when computing its LSS.

Applications:

"LSS is very useful for fitting quadratics, exponential growth, fitting equations to sequences of numbers, the distance between 2 lines, numerical smoothing and differentiation, surface fitting, curve fitting with B-splines, chemometrics, calibration curve, standard addition, Gran plot, and analysis of mixtures."

Note

The original question. Linear Algebra From the Beginning, Carlen and Carvalho. 2007 (1st printing). ISBN13: 978-0-7167-4894-6 Page 184, Problem 2.5. Chapter 3: The Image of a Linear Transformation. Section 2: The Closest Vector Problem and Normal Equations.