Lecture 4 Fall 2025: Least Squares and Optimization transcript

Welcome back everybody. Today we are going to continue with our discussion of lease squares. [Music] So just to remind everybody of the set setting, we start by being given training data. So in particular we have features x i and we think about each of these as being a vector of real numbers with p different elements and we have labels y i. And so in a classification setting, this might be plus or minus ones. Or we might represent the labels with zeros and ones.

Or in a regression setting, they just might be real numbers that we're trying to predict. And so now our goal is oh, and excuse me, this is the training samples are for i= 1 to n. So we've got an total of n different training samples. Now, our goal is to predict [Music] a new label Y for a new feature X. And the way we are going to do it is using a linear model. So specifically our prediction is going to have the form um w transpose x where we take the inner product or in other words we are going to have the sum from j = 1 to p of weight j * this vector x's j element.

And so if we were for instance looking at what prediction we would be making on our E training sample then we'd be taking the inner product of W our weight vector with X I and we'd be multiplying in the sum by the X I JS. And so our hope is to find a weight vector W so that this weighted sum is close to the training label Y that we have. So we're going to use our training samples to find a good weight vector. So we said before that we can write this a little bit more simply using matrix vector notation.

So we could have a label vector Y which just has labels Y1 through Y N in it. And we could also have a feature matrix X where the first row is the first feature vector transpose. The second row is the second feature vector transpose all the way down to the nth row which is the nth feature vector transpose. And so altogether this is a matrix with n rows and p columns. And so our linear model can now be written like this.

We want our weight vector w so that this label vector y is close to this feature matrix x times our weight vector w. So, what we looked at last time was least squares where what we wanted to do was to find the W that would minimize the sum of all the squared differences between the training labels and the predicted labels. So we tried to minimize y - x w and we wrote this as this two norm or equivalently the two norm squared.

So we wanted to minimize this and what we derived [Music] was a le squares weight vector that had the form xrpose x inverse xrpose y But we were left hanging a little bit because a core question that we had not addressed is when does this matrix xrpose x have an inverse? When can we even compute this least squares expression? And what ensures that it's nice and well defined? And what we claim is that this exists um these this inverse exists when [Music] x has p linearly independent columns.

So what we're going to do to start off today is to talk about this notion of linear independence. What it means mathematically, look at a few examples and connect it to the notion of computing this inverse and seeing why that's important for us to have a good le square solution. On an intuitive level, remember that these different columns of X, these P different columns of X correspond to different features. So, let's think about this running example we've been talking about where we've got measurements of people's facial features and we want to predict whether their photograph represents smiling or not.

Let's say that one measurement corresponds to left eye corner to mouth left mouth corner distance and another feature corresponds to right eye corner to right mouth corner distance. If all n of the people whose photos we have um are just perfectly symmetric people, then those distances would be equal and those features would be indistinguishable from one another. And so this would be an example of a case where we have two features that are not linearly independent of one another.

Because those features are indistinguishable from one another, we cannot compute this simple lease squares formula and we have to turn to more sophisticated methods that we'll talk about later in this course. But first let's focus on this notion of linear independence and when we can compute this matrix inverse. So we say that a set of P vectors V1 through VP all of which are in Rn is linearly independent. [Music] if and only if we can write uh it a weighted sum of these vectors.

And the only way that that weighted sum can equal zero is if all the weights are zero. [Music] Okay. So a little bit more specifically, if I were to write a sum from J = 1 to P of A J * VJ, then if this is equal to zero, then that implies that all of the AJS are also equal to zero. And similarly, if all the AJ's are equal to zero, then the weighted sum is equal to zero. Okay, so then these vectors are linearly independent.

And another way of thinking about this is that there's no way I can write any of the VJS as a weighted sum of the other remaining VJS. And so let's look at um an example that I want to make sure is is crystal clear. And in this case, we are going to have n being equal to three. So we're going to have each of these vectors have three different entries. And p is equal to four. So each one of them is going to have four different oop.

Yeah, I got that wrong. Each one is going to have n entries. I'm going to have four different vectors. [Music] I think I wrote it raw right and said it wrong. So my V1 is going to be 1 0 0. V2 is going to be 0 1 1. V3 is going to be 0 1 0 and V4 is going to be [Music] 1 0 1. So now the question is are these vectors linearly independent or not? And so if we were to look at a1 v1 plus a2 v2 plus a3 v3 plus a4 v4 and just write that out.

In this case it's a nice simple expression. So in the top we would have a1 + v um plus a4. The second entry would be a2 plus a3. The third entry would be a2 plus a4. Let's make sure I got that right. And so what happens here is that it's possible to find combinations of the a1 2 3 and four so that each one of these entries is equal to zero without the a's all being equal to zero. Right? So in other words I can write one of these v's and it's a weighted sum of the other v's.

So just to be explicit about it, if we had a1 was equal to a4 which is equal to a2 which is a3 then this weighted sum that I have written on the board would be equal to zero. Okay. Alternatively we can say we can do this explicitly writing one vector as a weighted sum of the others. And in fact in this case v4 is equal to vub1 um plus v2 minus v3. [Music] And so from this we can conclude that these vectors are linearly dependent.

They are not linearly independent. And in general, a key point is that [Music] if you have linear independence, it implies that the that P is going to be less than or equal to N. And if you have P greater than N like we do in this example, then it implies that your vectors are going to be linearly dependent. [Music] So when we're working with machine learning like the classification problem that we started off with or the regression problem that we started off with, we typically like to work in the regime where the number of features P is smaller than the number of samples N.

This is the case in least squares. When people talk about overparameterized machine learning, they might be working in the regime where P is greater than N and where the least squares techniques that we're talking about today will not necessarily work or not. You can't just use the formula that I wrote on the board and you have to start looking at other methods. But in the context of le squares as we're learning it here, we need to have the number of features be less than or equal to the number of training samples available.

Another important concept that we touched on earlier is that of matrix rank. And the rank of a matrix is simply equal to the number of linearly independent columns. and that is equal to the number of linearly independent rows of X. They're the same thing. Now, this notion of matrix rank is something that's going to show up um throughout this course, and we're going to see it from multiple different perspectives. We're going to see different ways of thinking about the matrix rank.

But for now, we can think about it simply as this number of linear independent columns or rows. Yes. >> Uh for P less than or equal to N case, I feel like you can also construct like a matrix where it is still linearly dependent. >> Right? So these arrows are not going both ways. So I'm saying if it's already linearly independent, then P must be less than or equal to N. But you can certainly con, this is a great point, you could certainly construct a matrix where P is less than N, but you do not have linear independence, right?

But I'm just saying if you know it's linearly independent, then you must have P less than or equal to N. Fantastic point. Are there any other questions? Yes. >> So for linear independence, why can't like we predict P smaller or equal to instead of P equal to for this case the maximum rank should be P and for N there is definitely going to be summed like dependenc. >> Okay. So I think your question was why does linear independence not require that p is equal to n but certainly in we uh one of the examples that we've covered in the past you can have p less than n and have linear independence.

So let's just do a very quick one. So here's an example where n is equal to what was it? n is equal to 3 and p is equal to 2. And so my first vector is going to be the same as my first vector in our previous example. Um 1 0 0 and my second vector is going to be 0 1 1. So these two vectors are linearly independent. I cannot write one as a weighted sum of the other. >> But rows are >> um okay we're not we don't really talk about the linear independence of rows in a vector.

So we're really just talking about linear independence of a set of vectors here. So we're talking about whether the set V_sub_1 and V2 are linearly independent or not. on making a matrix we focus on the columns >> in the context of least squares we said that we can use this formula when the p columns of x are linearly independent. Yeah. Okay. [Music] And so from here we have that uh the following. So, I'm going to just make a claim and we're going to uh there there's a little bit more detail in the printed lecture notes online and we're going to flesh it out a little bit more later today.

But specifically, if the P columns of our feature matrix X are linearly independent, [Music] then first of all, if we were to compute X transpose X and this is called a gram matrix. It also has P linearly independent columns. [Music] And so another way of thinking about this is XRpose X is a matrix that has P rows and P columns. And since it has P linearly independent columns, the rank of this matrix is P. Rank of X transpose X is equal to P.

And these two things the f or the fact that this matrix has rank p and is p by p tells us that xrpose x is invertible. [Music] And so we were a little bit rushed when we tried to cover this before. And so let's go through it now. matrix inverse. The inverse of a square matrix A which we write as A to the power -1 is the matrix A that satisfies that if I were to take A inverse and multiply it by a. Or if I were to take a and multiply it by a inverse, either way, I'm going to get an identity matrix.

And just as a reminder, an identity matrix is a matrix where I've got all ones along the diagonal and every other entry in the matrix is um zero. And so just as a little aside, right? If I told you about I don't know 10 inverse, then this is just equal to 1 / 10. And so if I think about my matrix A as being a 1 by 1 matrix with value 10, then A * A inverse would simply be equal to 1. So it's conceptually related to this notion of in inverse that you have encountered before.

And so my claim over here is that now if our matrix X of features has P linearly independent columns then the gram matrix XRpose X is invertible. And then we can use this formula that we have on the top that the camera is not capturing. There we go. That we have on the top in order to compute a le square solution. >> Yes. >> Um matrix is that >> yes so we can derive using the fact that just the form of the gram matrix and the fact that the p columns of x are linearly independent. we can derive that Xrpose X also has plinearly independent columns and that's written out in some detail in the online notes.

Yeah, I'm just not going to cover it in class today. Okay, great. And so then going back to lease squares, there we go. Um, the final thing that I wanted to mention is just going back to this um, geometric perspective that we drew out last time. And so if you recall, we had the span of the columns of X and we were writing these different vectors in it. So we had here this was the span of the columns of x or the range of x.

And so here was our origin and here we had the first column and here we had the second column. And then we had our label vector y. And we said that the vector in this span that was as close as possible to y that minimized the distance and we called this vector r. So that minimized that r was we called this yhat. And so this uh yhat is now corresponding to our x what. So this is the formula that we derived where what is equal to xrpose x inverse um xrpose y gives us the set of weights.

So that when we compute yhat equals x what that that yhat is the vector in this span of the columns of x that's as close as possible to our label vector y. And if we were to expand this out, so I've got x and then I put in sorry my w hat. So now I've got xrpose x inverse xrpose y. What I'm doing here is I'm taking my label vector and I'm multiplying it by this big matrix here that's composed of all the features that I've collected in my training set.

And this matrix also has a special name. This is called a projection matrix. And our geometric picture of le squares gives us a sense of why because it's sort of like we are projecting y onto the span of all of the columns of x. So the projection operation is finding this closest vector. Another way of maybe thinking about it is imagine that you know the um the span of the vectors is just like the blackboard and I've got some vector y whose point is out here and I shine a projector on it and I see where that point lands then that's going to tell me what yhat is.

So I am just projecting my original vector y onto the span of the columns of x. Any questions about this? Okay, so we derived all of this from the perspect from this geometric perspective and it allowed us to get introduced to a lot of core concepts like span linear independence and rank and invert inversion of matrices. But now what we're going to do is we are going to derive this same expression for le squares from an optimization perspective.

And this is you're going to think, well, why? We already know what the formula is. But we're this is going to allow us to learn a little bit about optimization. That's going to be extremely useful later on when we get to problems where there isn't a simple um formula that can describe the optimal value and where we have to compute it numerically using optimization tools. So, we're going to be thinking about this same problem now from a new perspective in order to acquire some new skills that'll be super valuable downstream.

[Music] >> Yes, >> I do have a question. Um, >> okay. I don't know if I completely heard you correctly but I think what you said was um in this expression that we have over here we are taking our this vector y and multiplying it by a collection of vectors I'm sorry matrices and you asked how do we know when the this product is going to also be a vector is that right >> okay so um there were some kind of diagrams I tried to draw in uh notes and on the board I always think about it myself just in terms of dimensions.

So y I think of as being an n by one vector in rows one column. Um so x remember is n by p and that means that xrpose is going to be p by n. So here I've got a p by n matrix and then xrpose x. So I'm just going to do this one off to the side. xrpose x is going to be p by n * n by p. And so when I'm multiplying two matrices together like this, I think of these inner dimensions as cancelling out because this is where I'm taking my inner products.

And so the result is going to be a p matrix. So down here I've got something that's p by p. And then finally I've got n by p. And so again whenever I'm doing these multiplications I think of the inner dimensions as cancelling out because the each inner dimension is like rows and vectors that I'm taking inner products of. And so those cancel out and those cancel out and those cancel out. And this tells me that this entire product now is going to be n by one or a vector with n entries.

Yeah, I don't know if that's the level of intuition you were hoping for, but um yeah, I guess the other thing I would mention is we said that this matrix right here is a projection matrix. And so for projection matrices in general, they are going to be square. In this case, it's n byn because we're taking a vector um in in n dimensions and we're projecting it onto this span, but it's still in an n- dimensional space.

So the kind of vector we're multiplying by and the output that we're getting back are both the same length vector, which is what we would hope for. Yeah. Any other questions? [Music] Okay. [Music] All right. So if we recall the way we set this up, we said that W hat was going to be the argument W that minimizes um the sum over all of our training samples of the residual R I squared associated with W. and just expanding that a little bit.

This is the sum from i= 1 to n. And then the residual is just the difference between our training label yi and what we're going to get out of this le squares predictor which is the inner product of x i and w and then square that. So our w hat is going to make this sum of squared errors as small as possible. Now we can write this same thing in with our vector notation. So this is the arg min over w of if I form my residual vector I'm just taking the norm of that vector squared.

And for my expansion here, it's the argument w that minimizes y - x w^ squared. So again, this comports exactly with our geometric picture. We're just trying to make the length of this residual vector r as small as possible. And then we are writing that residual be vector explicitly in terms of our matrices and vectors. Now we're just going to expand this a little bit. So in particular when we take the norm of a vector remember that's just that vector inner product with itself.

And so what we have here is y - x w transpose time y - xw. This is just using this notion of the uklidian norm. And now what I'm going to do is I'm going to expand this even further using the same kind of foil trick that you guys learned in algebra, but now applied to vectors and matrices. So we've got the argument W that minimizes. And so first I'm going to multiply the two first terms here y and y. And so I'm going to have y transpose y.

Then I'm going to do the outer term. So I'm going to multiply yrpose * xw *x w. And then I'm going to have the inner terms. So xwrpose and y. So I've got x w transpose * y. And then finally the last terms. So plus xwrpose xw. Any questions about this so far? Okay. And so now we've got yranspose y and we've got y transpose x w um and then we have here a transpose of this product of x and w. So when we're doing the transpose of a product, what we do is we take the transpose of each factor in the product and we reverse the order.

So this is going to be minus wrpose xrpose y. And similarly for this last term we're going to have plus wrpose xrpose x w. And the final thing that I'm going to do is I'm going to use the fact that yranspose xw and wrpose xrpose y those are the same thing right they're both scalar values one I've written one as the transpose of the other but since they're scalers transposes don't matter so they're exactly the same thing so I'm going to combine my terms so I'm going to have the arg over W of Yrpose Y minus um 2 Wrpose XRpose Y plus Wranspose XRpose W.

Okay. So now we have an expression here in terms of our matrices and vectors. And we want what this is saying is we want to search over all possible W's and find the W that's going to make this expression as small as possible. And this is very related to things that you have already encountered in calculus. And so we're going to start off with a simple scalar example and then build from there. But already you can see hints that we are going to be headed towards something that is as we would hope exactly what we derived from the geometric perspective.

Right? We're already seeing here this xrpose xw and this xrpose y which showed up in our system of equations that we were solving last time from the geometric perspective. Okay. Yes. Could you explain the ending of that second line again where we have y - x w how these two things are equal to each other. >> So how these two are the same? >> Yes. >> So just in general if I were to have um the ukitian norm of a vector squared just what this notation means.

I'm not really like doing anything fancy. This just means ranspose r that that's all. And so now I'm just doing the same thing with y - xw. I'm just replacing r with y - xw and putting it in parenthesis. [Music] >> That's right. I I wouldn't even call it a property. More like the definition. So it's not like I've done something advanced here. I've just like plugged in the definition. >> Yeah. Yes. >> So when because it's the minimization problem and y t y sorry ypose y is going to be the same for any value of uh any set of weights we choose can we remove it from the equation >> absolutely right that's a super insight uh I was going to get to that super very quickly for the video the question was well yranspose y is going to have exactly the same value no matter what we choose for w so why are we even bothering writing it down is this necess neessary or can we get rid of it?

And yes, we can absolutely get rid of it. Won't matter in the least. Excellent insight. [Music] Okay. So, yes, let's do a little warm up here. Um Oops. And just think about finding the minimum of a function in the scalar world that we all are familiar with. Is the red easy to read? Yeah. Okay. So imagine that we have a loss function L that depends on a variable W. And just to be clear over here, this thing that we're minimizing, this is our loss function.

This is our loss associated with W, where the loss corresponds to the sum of squared errors. Um, so now we're going to imagine a simpler loss function, which is simply 12 w^2 minus w - 12. And we can make a plot of this function. So on this axis we've got W and on this axis we've got our loss associated with W and it looks something like this and we want to find the value of W for which this is as small as possible. So here's the minimum and this is the W hat here that we are going after the minimizing value of W.

Okay. So the way that we learned to approach this in calculus would be to compute the derivative and set it equal to zero. So the derivative of L with respect to W. So take the derivative here. So we've got 2 * a half is 1. So we would have W. And then we would take the derivative of the linear term and we would just have minus1. And then we take the derivative of our constant. It's zero. And so our derivative is simply w -1.

We set that equal to zero and that tells us that our w hat is equal to 1. So right here this is equal to one. Okay, simple concept. Um in order for this to work of course this function has to be convex or in this context bowlshaped as opposed to a hump. Otherwise we'd be finding a maximum instead of a minimum. So all of these concepts are going to now show up as we think about le squares from an optimization perspective.

It's just now we're going to be working with matrices and vectors instead of scalers. But we're still going to be doing things like or analogous to taking derivatives and setting them equal to zero and making sure that the function we're minimizing is nicely B-shaped. So we're finding minimizers as opposed to maximizers or something else. Okay. [Music] So the first notion that we need to introduce here is a gradient.

And this is just analogous to a vector. I'm sorry. Analogous to a derivative but for vectors. [Music] Okay. So, in particular, I'm sorry I keep putting this on just do not disturb and I keep getting messages. Okay. So, uh gradient. So we have a loss L that is going to take in a vector W and output a scalar say the sum of squared errors. And so now the gradient of L with respect to W is the following gra. I'm going to write this as the gradient of L and then I'm going to put a little W down there in order to indicate that I'm taking derivatives basically with respect to W.

And all I'm going to do is just compute a whole bunch of derivatives with respect to the different elements of W. So first I'm going to have the derivative of my loss with respect to the first weight. And then I'll have the derivative of the loss with respect to the second weight all the way down to the derivative of the loss with respect to my final path weight. So the gradient is simply this vector of derivatives where I've got one derivative for each one of the different weights that I'm trying to learn.

Okay. So we're going to now work through four critical examples of gradients that are going to be very essential to our notion of le squares and give us some core concepts. And so the first one is where my loss is equal to w transpose c where c is just a vector of constants. So c1 all the way to uh cp. So I want to know what is the derivative of this. So recall this notion of of inner product tells us that this is just w1 c1 plus w2 c2 all the way to wp cp.

So now if I want to compute the gradient of my loss with respect to W, then I'm computing first the derivative of this loss with respect to the first weight. And what is that? C1 and with respect to the second weight C2. Excellent. And so forth all the way to CP, which is exactly this. So in this example, the gradient of this loss, which is just the inner product of a weight vector and a constant vector, is simply that constant vector.

Make sense? Okay, let's work through a few other examples. [Music] So here my loss is going to be um the two norm of w^2 or w transpose w and if we were to write this out the long way we would have w1 + w2^ 2 all the way to wp^2. And so now if I wanted to compute the gradient of this loss with respect to w. First I compute the derivative with respect to w1. And what do I get? 2 w1 and then 2 w2 all the way to 2 w. And so this is simply 2 * my original weight vector, which hopefully these should feel comforting, right?

Like if we simply had in our first example, if these were scalers, right? And I had a function that was a constant times my variable and I take the derivative, I would just get the constant back, right? That's what I would hope. Similarly, if in example two, we had a quadratic expression and or a quadratic function and we took the derivative, we'd expect 2 * our variable to pop up, right? Like if we had f of Yeah. Anyway, sorry.

So, this is consistent. If if p was equal to one and everything were in the scalar case, it's consistent with everything we're experienced with with derivatives. Okay. Now, the third example is super important. We're going to use this a lot, but the derivation is a little tedious, and we're not going to go through it all here in class. [Music] But the example is where the loss with respect um or the loss of W is equal to Wrpose* some matrix square matrix Q * W.

So in this case, it's a little bit like example two, only we've got this Q matrix popping up. And so writing out the expression for the loss and longhand is a, like I said, more tedious. But in this case, you it is possible if tedious to work out the gradient of L with respect to W is equal to Q * W plus QROSE * W. And if Q is symmetric, which means that Q and QRpose are the same matrix, then the gradient of this loss with respect to W is 2 Q * W.

Okay. [Music] So our final example, my loss with my loss as a function of W is equal to Y transpose Y - 2 Wrpose XRpose Y + Wrpose XRpose XRpose W. [Music] Okay. So, we want to compute the gradient of this function which if you recall is our least squares loss function, right? And now we can put the all the pieces that we have together. [Music] So the gradient of our loss with respect to w as we pointed out before this is a constant doesn't depend on w at all.

So that gradient is just going to be equal to zero. Now if we look at this term here, what example have we already seen that can help us here? Right? This is just like example one. We have got Wrpose times a vector that doesn't depend on W. So it's a constant relative to W. And so we are going to be left with that constant vector which in this case is 2 xrpose y. And for this expression oops what can we use in order to compute this gradient?

Yes. So that would be 2 * wos. >> Okay. This is my fault for not labeling it because I think you're thinking exactly along the right lines. Um so in this case we do have this matrix um x transpose x showing up in here. And so this is the form of the previously unlabeled example three. Um, and so just like you were saying, we now have 2 * xrpose x w showing up. Make sense? Yes. >> Um, sorry, this is >> so the loss function is it's a function.

So it's like a mapping. So it's taking a vector in and outputting a scalar, which I think is what you were saying. And then you're saying, well, why is the gradient then not a scalar and instead a vector? So that's an excellent question. It's a little bit hard to draw, but I'm going to give it a shot here. So let's imagine that our loss function is sort of like this this bowl shaped thing. Um so here I've got weight one and this direction is my weight two and this direction is my loss with respect to my weight vector.

So if I were to yeah sorry I'm just not great at drawing this but imagine that I'm at a point here and I want to compute the gradient. The gradient is telling me how is this loss changing in the W1 direction and then separately how is it changing in the W2 direction. So even though the loss only has a scalar value, the gradient is telling me how much it's changing or how quickly it's changing in each of the different directions that the function depends on.

Yeah, great question. Any other questions? Yeah. Yeah. Yes. >> Here Q is a square matrix. >> Yes, that's right. And Q would have to be square in order for our dimensions to work out. So here w is um a p by 1 vector. So wranspose is 1 by p. And so in order for this multiplication to even be possible, q would have to be p by p. And of course by the same like dimensions cancelelling out argument that we had earlier, this product is going to be just a scalar or a one by one.

Great. Any other questions? All right. So now that we have this expression for um the gradient of our loss, [Music] remember that we wanted to compute the arg min with respect to w of this particular loss of yrpose y minus 2 wtranspose xrpose y plus wrpose xrpose xw. And so our inclination would be to take the gradient and set it equal to zero. So let's just see what happens if we do that. So set gradient to zero. So we would get um here -2 xrpose y + 2 xrpose x w is equal to zero.

Now I'm going to divide both sides of my equation by two. Simplifies things right off the bat. Now I'm going to move my negative xrpose y to the other side. So that I have xrpose x w is equal to xrpose y. We derived exactly this equation when we were looking at things from the geometric perspective. And if xrpose x is invertible then this tells us that the solution to this optimization problem will look like xrpose x inverse xrpose y.

So from this optimization perspective we have derived exactly the same formula for the le square solution. But again this hinges on xrpose x having an inverse. So we talked about that a little bit from this notion of linear independence and matrix rank. But I want to talk about it more now from this perspective of optimization and when we can expect our optimum to correspond to this formula. Are there any questions so far?

[Music] Okay, so recall that when we were talking about, you know, finding the minimum of a function back in calculus, we would take the derivative and set it equal to zero. But that depended on the function being convex or kind of B-shaped. Otherwise, we would risk finding, say, a maximum or some other point that is not the minimum we seek. And so now what we want to do is to think about what's the analog of that concept in this vector um setting that we are in now.

Okay. So in particular we are going to talk about positive definite matrices. And this is important because um if we have a matrix X that is N by P where N is greater than or equal to P and the rank of X is equal to P. So x has got p linearly independent columns. Then we know that x is invert or xrpose x is invertible. [Music] And we also know that xrpose x is positive definite. Okay, so this is not a definition. I'm going to define it in just a second.

But the claim here is that this notion of invertability which shown up a couple of different times now is intimately connected to this notion of positive definitess. So when we think about positive definite matrices, one of the reasons that we care about this is it is telling us when we can perform this matrix inverse that's essential to this machine learning procedure that we've derived. So the matrix Q is positive definite.

And we write this sometimes as P D. Um or we might say that this matrix Q we write it as sort of this curly greater than sign and then a zero. So both of those things correspond to positive definite PD or Q curly uh greater than zero. [Music] If whenever we take a vector w and compute wtranspose qw that this is greater than zero for any vector w that is not equal to zero. Okay. So clearly if w is equal to zero then this product is zero.

But aside from that, for any other weight vector, if we were to compute wrpose qw, that has to be zero in order for the matrix Q to be positive definite. We can also say a matrix Q is positive semi definite and I really think mathematicians come up with funny names for things sometimes but PS D or we write Q and we've got this curly now greater than or equal to sign zero if wrpose qw is greater than or equal to zero.

Um well for all w. [Music] Okay. So this I think right now feels very abstract. And so what I want to do is to now connect these definitions to the optimization framework that we've been working in today and think about the geometry of the optimization problem and how it relates to positive definite matrices. Okay. So [Music] let's start where W is I guess I won't even write the underline just a scalar and so is Q right so we're going to work with a very simple scalar setting first and so then this notion of wrpose qw W when everything's a scalar is just Q * W^2.

And so the question is when would q W^2 be equal to zero? Well, this is always greater than zero if um W is not equal to zero. We want to know if Q is positive, definite or not in this scalar toy setting. So we want to know when qw ^2 is greater than zero assuming that w is not equal to zero. And so when will that happen for what values of q? Any thoughts? [Music] um when I think I heard this murmuring whenever q is positive right so w is non zero positive or negative and I square it I'm going to get a positive number so as long as q is positive the product's going to be positive right so in this case a positive definite scalar q is just a positive number q but now we can see why this is relevant because we can say imagine trying to minimize a loss L of W equaling Q W^2.

And so we can consider the case where Q is a positive number. And again, we're going to plot W versus our loss L of W here. And when Q is a positive number, then this loss function is going to look like a simple quadratic like that. And so this is a setting where we can take this, compute its derivative, set it equal to zero, and find a minimizer. But in contrast, if Q was less than zero, then we are no longer in this positive definite setting.

And now if I make a plot again w and l of w then all of a sudden this loss function it looks like a quadratic but it is flipped to the other way. So now in this setting if I were to take the derivative and set it equal to zero I would find a maximizer not a minimizer. Yes. So in this example, I am just just to kind of illustrate the concepts, right? I'm thinking about P is equal to one. So I'm still thinking about Q as being a P by P matrix.

Nobody really worries about positive definite scalers. I'm just trying to connect this notion of positive definitess to things that you're already familiar with in calculus where you're trying to find extreme values of functions in one dimension because hopefully I'll make the concepts in higher dimensions a little bit more accessible. So I'm just trying to say well what this notion of positive definitess what that special case looks like when P is equal to one and what effect that has on the loss function we're trying to minimize in this special toy setting yes >> are we allowed to say wqw= qw >> in general you cannot >> in general this would not be true but when we're in P equals 1 when everything is a scalar then these two things are equivalent and only then otherwise we can't do it right any other questions okay so another way of saying this is that and this is going to generally be true when Q is positive definite then things are easy to minimize for this loss function and over here when Q is not positive definite then things are hard to minimize.

Okay. Okay, so this notion of positive definitess is related to our ability to minimize different functions at least using the different techniques that we've been describing so far. All right, so now let's move to higher dimensions and see how these ideas manifest there. [Music] Okay, [Music] so now we're going to have P is equal to two. So our weight vectors have two dimensions and so W is in R2 and Q is in R2X 2. It's a 2x two matrix.

And now we could imagine trying to minimize L of W is equal to Wranspose QW. So for instance we could have Q being equal to 1 0 0 1 just an identity matrix. And so for this case Wranspose qw is simply going to be wrpose w or um w1 2ar + w2 2. So remember our definition of positive definitess said that this matrix Q is positive definite whenever this product Wrpose qW is positive for any W that's non zero. So in this case in our example here for this particular Q wranspose qw has this form here.

When is this positive? Yeah, for any w not equal to zero, this is going to be positive. And so as a result, we can infer that this Q is positive definite. And like we were doing in the 1D case, we can try to make a plot. So this axis is my W1 axis. vertical is L of W and then I've got my W2 axis here. And in this case, the function that we are trying to minimize is going to look like a bowl. And I don't know, imagine that there's some contour lines here.

So, we've got a nice sort of bowlshaped function here. And so you can imagine then if we were to take a function like this and compute its gradient and set its gradient equal to zero. What does that mean? It means finding a point where I look and see how much the function is changing in the w1 and w2 directions and figuring out where there's no change where the function is not um yeah where where the derivative is zero in all directions which is right here at the bottom of the bowl.

So the fact that Q here is positive definite is correlating with a loss function that is nice and convex or B-shaped and easy for us to minimize using this technique of taking the gradient and setting it equal to zero. Now in contrast we could consider a different Q matrix which was here we go 1 0 0 1. So in this case if we were to look at w transpose qw and try to write out in long form what we get. This is going to equal w1^2us w2^2.

[Music] Is this always positive? No. Right? If I were to take some w not equal to zero, I square the two values, I get two positive numbers, but I multiply them by negative 1. I'm going to get something negative. This is less than zero for w not equal to zero. If I were to try to make a plot of a loss function of this form wranspose qw then what I'm going to see is something that looks like an upside down bowl. So similar to the other one but now just upside down.

And so here the fact that Q is not positive definite. So here Q is not positive definite is corresponding to a loss function where if we were to take the gradient and set it equal to zero, we're going to find a maximizer instead of a minimizer. >> Yes. some dimension for example. This is a great question. In fact, that corresponds exactly to my next example. It's almost as if all the lecture notes are online. I'm just teasing.

It's fine. This is a great question. Okay, so my next example is where this we've got the same two-dimensional setting, but Q is equal to 1 0 01, right? And so now if we were to look at what does Wrpose qw look like and spell it all out, we get W1^ 2us W2. And so for some W vectors this will be positive and for some W vectors this will be negative. But in order for Q to be positive definite it always has to be positive.

And so in this case Q is not positive definite. And if we were to plot this function or the loss associated with this Q, then we get something that in the W1 direction looks Bshaped, but in the W2 direction looks upside down B-shaped. And so I'm getting these contours where if I were to hold W1 fixed and try to vary I'm sorry. If I were to hold W2 fixed and try to vary, let me get this right. If I hold one fixed and keep the and and vary the other, then I get a nice convex function where the minimum corresponds to where the derivative is zero.

But if I were to look at a different direction, I get this upside down bowl shape. And so the place where the derivative is equal to zero might be a maximum. And so if I look at a place where the derivative with respect to both w1 and w2 is equal to zero where the gradient is equal to zero then I guess in this example it's right here at the origin. It's called a saddle point. So it's a minimizer in one direction but a maximizer in another direction.

So if you think about the literal shape of a saddle when someone's riding horseback, it's corresponding to this point where you have like the the minimum um with with respect to one direction and maximum with respect to another direction. Okay, so this is another setting where if we just look for the place where the gradient is equal to zero, we will not have a minimizer of our loss function. Fantastic question. And we can do more complicated um Q matrices um that are um that that also connect to these concepts.

Okay. So within the notes there's a number of different properties of semidefinite matrices and we're not going to go through all of them here in the lecture but there's one that I really want to emphasize because it's super important for this class um which is for any matrix X if we were to compute Q is X transpose X so now Q is a square matrix mat then um that matrix is positive semidefinite and similarly um I don't know q tilda some other q that's equal to xxrpose that's also positive semidefinite and so now the real question is um well okay and I derived this in the notes but we aren't going to have time to do it today If the columns of X are linearly independent, then if we were to compute Q as being Xrpose X, then it is positive definite.

And as we said before, this implies that it is invertible. And so when the columns of our matrix of features X are linearly independent, then this gram matrix that shows up in our optimization formulation and in the set of equations that we derived from the geometric perspective in that setting that matrix is positive definite and it is invertible. So we can use the formula for le squares that we've been using. And in this setting, this notion of positive definitess is telling us when the function that we are trying to minimize when this loss function is convex where we don't have to worry about it finding a maximizer or a saddle point, but rather the place where the gradient is equal to zero is in fact a minimizer of our loss function.

Any last questions? Yes. So in this for any x and that right side are all these conditions to that last line that you're saying are the first two lines conditions too if the columns of x independent then >> I was just trying to make two separate statements here um but here I think yeah for any x of real numbers where you've got linearly independent columns and the number of rows is bigger than or um equal to the number of columns then we would have this property and we can use all of the le squares formulas we derived.

Great. Thank you very much and I'll see you next week. [Music]