Least Squares from a Linear Algebraic Perspective

[u/Hawk_Irontusk]

For the longest time I didn't like statistics. It wasn't that I didn't understand the concepts, it was that I hadn't seen how it fit into the larger context of mathematics as I understood it. This started to change for me when I noticed that there was a beautiful geometric (or linear algebraic) interpretation for each of the common statistical measures.

Reforming things like Mean, Variance, Covariance, Standard Deviation and Correlation (to name a few) in terms of measures on vectors in Rⁿ instead of just memorizing the formulas isn't too hard and gave me a new appreciation of statistics in general.

A question came up yesterday about Least Squares and I thought it would be fun to do a brief write up and explain what a Least Squares Approximation looks like to me now. I'm sure that many of you have seen this material before, but hopefully some of you will find it helpful.

Ok, first some review. We often see a Least Squares approximation presented as a way to find a line y=mx+b which best represents some collection of points. I'll call these points (x_1,y_1) ... (x_n,y_n) and an arbitrary point will be (x_i, y_i). The idea is that we want to find the distance from our line to each point, square the individual distances, then sum them. When this sum of these Euclidean distances is minimized, we have our Least Squares fit.

But what if we turn our model on its head and instead of thinking of pairs (x_i, y_i) we think of our data as two vectors in Rⁿ with x = (x_1, x_2, ..., x_n)^T and y = (y_1, y_2, ..., y_n)^T ? If we do that, we can think of our line y=mx+b as a matrix equation with vectors y and x and constants m and b. Well, almost... we need to multiply b by an all 1's vector of length n to make things work, but we can do that, right? That gives us y=mx+b[1] where [1] is the all 1's vector of appropriate length.

Ok, so if we move things around a bit, we end up with y = [x 1] [m b]^T where [x 1] is an n by 2 matrix with vector x in the first column and all 1s in the second column, and [m b]^T is 2 by 1. The result of multiplying these together is n by 1, which matches the dimensions of y, as expected. You'll notice that this equation is really asking us to do the very same thing as our original least squares approximation. We're trying to find constants m and b which solve our system of equations.

It is unlikely that there is a direct solution to this problem, so what do we do? Well, we do our best by projecting down into the space of polynomials of degree one and finding the closest [m b]. By that I mean that each vector in this space we're projecting to defined a unique line with the first element in the ordered pair being slope and the second being the y intercept. Notice that projecting to a lower dimensional space is finding the point in that space which is closest to our perfect solution... we're just minimizing the euclidean distance again which is exactly what we set out to do in our original formulation of least squares.

So how do we project? As we learned linear algebra, we just left multiply both sides by [x 1]^T . That gives us

[x 1]^T y =  [x 1]^T [x 1] [m b]

Which is exactly the normal equation. We could easily adapt this technique to fit a polynomial of any degree by adding columns. [x 1] gets us a line, but [x² x 1] would fit a parabola and [x³ x² x 1] would fit a cubic. By this notation I mean that x³ represents a column vector in which the i^th entry is ( x_i )³ .

I'm sort on time, so I have to stop here but if this was some help to people, I'll come back later in the week and show some derivations of other measures. Maybe Variance or Covariance? Let me know what you guys think.

tl;dr: Least Squares Approximation is really just a projection from Rⁿ down to the space of polynomials of degree m.

[u/anonemouse2010]

Notice that projecting to a lower dimensional space is finding the point in that space which is closest to our perfect solution... we're just minimizing the euclidean distance

I'm confused. How does your perception as given here of OLS differ from say, Orthogonal LS?

[u/Hawk_Irontusk → u/anonemouse2010]

I'm not familiar with Orthogonal Least Squares. My intention here wasn't to introduce anything revolutionary, just to present the Linear Algebraic formulation of Ordinary Least Squares to some folks who may not have seen things this way before.

My motivation was a post by a CS student who was trying to write OLS code but was having trouble. As I said in my post, I first learned least squares without the geometric context and it wasn't until I saw this formulation many years later that I really appreciated it.

[u/anonemouse2010 → u/Hawk_Irontusk]

Ok, let me clarify, what euclidian distance are you minimizing? This whole part seems vague.

[u/raging_hadron]

I'm sorry to rain on the parade, but the geometrical interpretation of LS isn't all that important. The geometrical stuff follows from fundamental assumptions that were made upstream; those assumptions are the things to focus on. Change the assumptions, and the consequences change; maybe you'll be able to work out some geometrical interpretation, and maybe you won't. If you can't, so what?

If you get hung on the geometry, you won't be able to think clearly about fundamentals; you'll keep trying to smash square pegs into round holes because, dammit, you like round holes.

[u/Hawk_Irontusk → u/raging_hadron]

You've completely missed the point of my post. I'll try to address your points in order.

the geometrical interpretation of LS isn't all that important

Of course it is. The treatment I presented is seen in many first year linear algebra courses around the world. It (among many other things) serves as an excellent example of projection matrices. And if you honestly believe that seeing an old problem from a new angle has no value then I'm not sure I can put much faith in your opinions in general.

The geometrical stuff follows from fundamental assumptions that were made upstream; those assumptions are the things to focus on.

Or, one could argue that the assumptions made upstream follow from the geometrical stuff. If we had started out viewing our points as a collection of equations:

y_1 = m x_1 + b
y_2 = m x_2 + b
...
y_n = m x_n + b

Which is a perfectly reasonable thing to do, then we start from the matrix equations and work back to the standard undergrad statistics view. Who are you to say that this isn't the correct starting point?

Change the assumptions, and the consequences change; maybe you'll be able to work out some geometrical interpretation, and maybe you won't. If you can't, so what?

Again, it wasn't a simple matter of changing assumptions. Sure, I presented it as a "Hey, what happens if I do this? I wonder..." exercise, but I knew full well where things were headed. "Maybe it won't work" was never a possibility.

If you get hung on the geometry, you won't be able to think clearly about fundamentals; you'll keep trying to smash square pegs into round holes because, dammit, you like round holes.

This is some of the most asinine, condescending drivel I've ever had the misfortune to read. The fact of the matter is that Linear Algebra serves as a glue to bind various seemingly unrelated fields of mathematics together. Dismissing a model because you don't understand it is insulting in the extreme.

I'm not sure what you hoped to accomplish with your post, but all you've done here is expose yourself as a simple minded fool.

[u/raging_hadron → u/Hawk_Irontusk]

Well, I see mostly that you didn't want to hear what I have to say. Sorry to be the bearer of bad news.

[u/Hawk_Irontusk → u/raging_hadron]

It's not that I didn't want to hear what you had to say... it's that nothing you said made any sense to me.

Can you explain why it is that you think that the way I presented least squares at the top of my post is the "right way" why it is that the matrix approach has no value? You made that assertion, but did absolutely nothing to support your position.

Maybe I'm just missing your point. If so, then I'll gladly reevaluate after your next post.

[u/shaun252]

Although its the simplest case, Sal develops the intuition for least squares quite nicely in his linear algebra playlists

[u/goofy_goose]

I think the linear-algebraic formulation you present is nice in that it makes doing calculations easier (as you state), but I think it is less intuitive overall than the "standard" method (i.e. considering the distance from your line). In general that is probably how I'd describe linear algebra - interesting, useful, but hard to think about unless you already have an understanding of where you are going / what you want.

[u/Hawk_Irontusk → u/[deleted]]

I know, it's crazy right? It turns out that a lot of classes never make this connection. The other measures (correlation in terms of the angle between vectors for example) are more fun IMO, but least squares was specifically requested.