Lecture 10 Fall 2025: Data Leakage and Matrix Completion transcript

Hi everybody. For the past several days, we've been talking about the singular value decomposition. And today we're going to talk about different ways in which it is used in machine learning. So the singular value decomposition in machine learning. So first of all um what we will talk about today is something called principal components crime. So this is an issue that can arise in many practical machine learning scenarios that you should all be aware of and know how to avoid moving forward.

Second, we are going to finally finally talk about the real Netflix problem in the context of matrix completion. So in the past we have t referred to the Netflix problem as think a way to think about a matrix with low rank. Right? We've got a giant matrix with a huge number of movies and an even bigger number of customers. But we say most customers movie ratings can be thought of as a weighted sum of a small number of representative movie watchers.

But of course in real life we don't have that full matrix because we don't know the rating of every person for every movie. And so matrix completion is about taking a subset of the entries of this matrix and using the SVD and related ideas to figure out what those representative movie watchers are and figure out how to use that information to fill in the missing entries. Now this is what we are going to cover today. But in subsequent lectures we are going to see other things that might be of broad interest.

So we are going to talk about page rank which is the algorithm that Google used to figure out how to uh return search results ranking different web pages based on their relative importance so that when you search for a term it's returning things that match your search but also are widely popular and uh useful websites. Uh and we'll also be talking about other aspects of the singular value um decomposition in machine learning including as we start finally talking about regularization and this is related to ideas like weight decay in neural networks which you maybe have seen previously but which we can think of in much more much broader contexts but for today we are going to focus on principal components crime and matrix completion.

So the first thing I want to do is to draw out a scenario of how people perform machine learning in real world contexts um and what this process might look like. So the first thing I want to do is to talk about principal components prime. So let's imagine a scenario in which a company is trying to perform machine learning using some data and they adopt the following process. So in the first step they collect data and then they do some pre-processing and cleaning and in particular through that process they are going to try to reduce the dimensionality of the data.

So they're going to run PCA and reduce the dimensionality and in particular the dimension of the feature vectors. So when I say this, what I mean specifically is the following setup. We're going to have X be equal to the matrix with n rows and P columns of all of our training feature vectors. Then they are going to use the singular value decomposition and principal component analysis to compute VK where VK is the matrix of the first K principal component vectors. and in particular corresponds to the first K columns of V where if we take our matrix X and compute the singular value decomposition we get the decomposition U sigma VRpose.

Once we have those principal components then we can do um dimensionality reduction. So in particular we would map each of our feature vectors x i which is in our original pd dimensional space to a corresponding vector zi and we would do that by now we can think about dimensions here this vk matrix is a matrix that is um p by k and So if we were to compute vk transpose * x i then this is going to give us a new feature vector that is kd dimensional and this is exactly how we approached dimensionality reduction when we talked about it last week and we do this for each of our samples for i = 1 all the way to n.

After this, we would split the data into um a training set with I'm going to say in train samples and a test set with n test which is equal to n minus n train samples. So just all of the samples that are not in the training set. Once we've done this splitting then what we can do is we can train an ML model on the training set. And once we have that learned model, then what we can you do is use our test set to measure the model accuracy on the test set.

Okay. So what we'd like to know is if we're given a new sample, how well is the prediction represented by our machine learning model going to perform? And so these test samples were not used for training the ML model. And so we can see how well it performs on these other samples. Okay. If you were to adopt this procedure, then all of a sudden you will get an inflated estimate of your model accuracy. Okay. So you hope that when you run your model on your test set and you see for instance 90% accuracy that then if you take that model and deploy it in the real world you also see 90% accuracy.

But if you adopt this procedure, the risk that you have is that you measure your model accuracy on the test set, see like 90% accuracy, and then deploy it in the wild and start to see 60% accuracy in the real world. And so there's a very specific reason why this can occur using the procedure that I just outlined for you. So just to be super clear, this is bad. Do not do this. This is something you want to avoid. So what do we see here as the key problem?

Where did we make a mistake? So the key issue is that when we did our principal components analysis, when we figured out what this matrix VK is that we used to reduce the dimension of all of our samples, we used both the train set and the test set. All of those samples were used together to find those first k principal components and were used to reduce the dimension of the data. So you can think about it in sort of a handwavy way as this matrix VK is containing information about the testing samples.

So then when we use that information to reduce our dimensionality, all of a sudden our new training samples in this lower dimensional space have some information about the test samples embedded in them. And we can even see this pictorially. So in particular, let's just imagine that I'll make a plot uh over here. So I'll just make a plot over here. So imagine that we have all of our samples in two dimensions. So P is equal to two. and I first plot all of my training samples.

And let's just say, and I'm doing this in an exaggerated way just to drive the point home, but let's imagine that our the test samples are slightly different in a slightly different distribution. Now, in general, we want our test data and our train data to have the same distribution. So this is not the kind of scenario that you would want in practice, but I just want to produce a visualization here of how this matrix VK can reflect information about the test data.

Because if I were to use only these training samples in order to perform PCA, then what I'm doing is I'm finding in this case the best 1D subspace fit to the yellow dots. and it would look something like this. But if I were to take the combination of the yellow dots and the red dots, put them all together and find the best 1D subspace to fit, then I might end up with a very different matrix. So when we're doing dimensionality reduction [cough] in this scenario that I mapped out on the other board, what we're doing is we are projecting each one of our points onto I should try it more accurately onto this subspace that contains information about the distribution of both the red and the yellow dots.

So both the training data and the testing data together. In contrast, if I had run PCA only on the yellow dots, then I would get a different 1D subspace. And so when I'm projecting my samples onto that different 1D subspace, I'm getting a different projection, certainly a different ZI, but also I'm getting something a projection that no way depends on any of the red dots. And so this approach that I described on the other board is what I'm referring to as principal components crime.

And so now what I want to present is an alternative approach that avoids this issue and helps prevent having an inflated estimate of the accuracy of your machine learning model. Okay. So, here is the alternative. And again, I just want to be really clear. What I'm about to describe is a good way of handling this. So, the first thing we do is well, of course, collect our data. But then as soon as we collect it, collect it, we split into the training and test sets.

So again, we're going to have n training samples and n test, which is n minus n train test samples. We're doing the same kind of split, but we're doing it right off the bat before we do any kind of principal components or dimensionality reduction. So our next step here is to run PCA [snorts] on the endrain training samples. um to get VK which in this case is the first K columns of V where X now I'm going to write X train is equal to U sigma VRpose so now I'm taking the singular value decomposition ition of just the X train matrix.

And to be clear about what I mean here, what I'm saying is that we could have our full X matrix here X which is N by P and we could just take the first say in a train rows and this is what I'm calling X train. So we take just the submatrix that corresponds to our training samples and we compute the singular value decomposition of that. This gives us new principal components or different principal components than we had in the the bad setting and then we can proceed similarly to how we did before.

So we are going to map each x i which is a point in our p to a new zi which I'm going to compute as v k transpose x i to get something that is kd dimensional. Now we're going to do this for all of our samples all the way up to n. So we're doing the dimensionality reduction still on the testing samples. But the key point here is that this matrix VK that we are using to do principal components analysis or that we are using to reduce the dimensionality of our data.

That VK only contains information about the training samples does not contain any information about the samples that we will ultimately test on. So once we've done this, now we can um split um train a minute, excuse me, train an ML model on the training set. And once we've done that, then we can measure the accuracy on the test set. And so now because we don't have this data leakage because nothing in our training data depends at all on our test data then what we can hope for and expect is that our accuracy on the test set is representative of the accuracy that we will have in the real world.

Right? So if we see 90% accuracy on the test set then we have a reasonable expectation that we should see 90% accuracy in the real world assuming that real world data is collected under the same conditions that our training and testing data was collected under. Okay. So always always if you're going to do PCA or some other kind of dimensionality reduction, it's extremely important to do your train test splits first and use only the training data to figure out the mechanism of dimensionality reduction.

In this case, the VK. Once you've got that mechanism in place, then you can say, "All right, I'm going to fix that. I'm going to fix the VK and I'm going to apply it to all of my data, training data, test data, real world data after deployment, but I'm holding that fixed because it's only dependent on my training data. So throughout the quarter, I think from the very first lecture, we have talked about Netflix matrix um as being a motivating sort of example for many different concepts.

So what we haven't talked about is that in reality this matrix of movie ratings for customers and movies that Netflix has is incomplete. So remember that our setup is that we have a matrix X that is N by P where N would be in this say setting the number of movies and P would be the number of customers. And so I'm going to kind of draw this as a grid here. And the idea is that each entry in this grid corresponds to the rating of one customer for one movie.

But of course in reality every customer has not watched every movie. And so there are numbers in some of these blocks but there's a whole bunch of blocks where we have not made any observation. We don't know what that rating is. And what Netflix wants to do is to predict that rating. They want to say, "Oh, well, if you were to watch this movie, would you like it or not?" And if they can predict that, right rating, then they can recommend to you um a new movie to watch that they think you will like, right?

And so this is an example of a more general problem um or more general uh yeah problem setting of recommener systems. So what we're trying to do is to learn how to make good recommendations. And so what I want to talk about today is how to formally state what this problem is and some of the approaches that people take to estimating what the missing entries are. So we are completing the matrix because we are filling in the missing entries and of as you might expect all of it is intimately related to the singular value decomposition.

So this tool that we've learned which felt a little abstract at the beginning perhaps has this very real world machine learning um application. Okay. So with matrix completion, the idea is given um a subset of the entries of X. We want to estimate the missing entries. Okay. Now, if we don't make any further assumptions, this is impossible. Um, right? Like in general, I can put any numbers into these missing entries and it's still a valid matrix, right?

And so in order for this to really be viable, we need to make assumptions. And the core assumption is that um X is low rank and more precisely the rank of X which we are just going to call R is much less than the minimum of N and P. And this sounds like an abstract assumption, but as we've talked about throughout this quarter, this corresponds exactly to this notion of there being our representative movie watchers. So the idea is that if I know that you are a horror movie lover, especially around Halloween, and I can look around and look at all the other customers who also seem to like horror movies, then I should be able to use that information to accurately predict how much you're going to like some new horror movie based on what other people who have watched that movie and have similar tastes to you have liked. a very intuitive idea and it corresponds exactly to this notion that this matrix X if we knew all the missing entries has low rank.

And so from here we can now posit the matrix completion problem ma mathematically and a little bit more formally. Okay. So what we're going to do is um we're going to let omega be the set of all the different locations in the matrix um where we observe xig. Okay. So omega is all of the entries. Omega is the set of all the kind of movie customer pairs where we have an observation and its complement corresponds to all the different missing entries that we're trying to fill in.

And so now what we can do is we can say all right my estimate of this matrix X is going to correspond to the following. What I'm going to do is I am going to search over all matrices M that have that that are the same size as X. So they are all going to be N by P and we are going to try to find the matrix M that has the smallest possible rank. So we are going to minimize the rank and we're interested in the argument or the matrix M that achieves this smallest rank subject to the condition that if I were to look at the J entry of M, it matches what I actually observe Xig J for all of the um I J pairs that are in this set omega.

So everywhere where I have an observation where I've recorded someone's movie reading, I want the matrix M that I'm searching over, I want it to match my actual observations, I want to be consistent with my observed matrix. And then if I think about all the different matrices that are consistent with my observations, all the different ways that I could fill in the missing entries, I want to choose the one that gives me the lowest rank, which conceptually corresponds to trying to find the representation of my observations where I can represent each movie watcher as a weighted sum of some representative movie watchers.

And I want to keep the number of representative movie watchers as small as possible. I don't want a million representative movie watchers. If I can get away with 10, I'd like to. >> Does this make sense? Yeah. >> So the set of J is all the like all the entries in X that are not empty. Like that's is that what we mean by observe? >> Yeah, exactly right. So if we go back over here to my little picture, then I'm talking about all of these entries where I haven't filled it in throughout it.

This is my set omega. These are the area uh the entries where I have an observation. And then these other ones where I've kind of scribbled in them, those are the entries that I want to fill in. And that's omega complement. Any other questions? Yeah. >> So, um the question is is this similar to finding a basis for a subspace? And yes and no. Um, it's different than the way that we've framed finding a basis before because when we talked about it before, we had a bunch of samples that were on or near that subspace, but we knew all the entries of those samples.

Nothing was really hidden or missing. And so then we could use methods like Graham Schmidt or the SVD to find that basis. Here we're trying to fill in missing entries. Now that said, your question is very insightful because when we are minimizing the rank, I said we are effectively trying to minimize the number of representative movie watchers and we can think about that as being a basis. So we can think about minimizing the rank here as like minimizing the subspace dimension that represents all my movie watchers and similarly minimizing the number of basis vectors.

I would need to represent them. So you're right that we can think about this as related to finding a basis but it is not the same formulation as sort of the finding a basis stuff that we did in the past lectures. Yeah. Great. Any other questions? Okay. So um don't hesitate to stop me uh uh if you've got questions later. Now this is great if we want to really insist that we have a perfect match to all the samples but there are alternatives like in real life data is messy there are errors maybe people like hit the wrong thing or in Netflix in particular right the measurements are quantized right you're only allowed to give ratings you know in the old days one through five now it's either like or dislike and so you might not be able to match your data exactly and you want to give yourself a little bit of wiggle room.

And so an alternative that you could consider would be to say, I still want to search over all matrices M that are the same size as X and I still want to minimize my rank. But now I'm going to be a little bit more relaxed and say that I want to look at on average. So I'm going to look at all the J pairs in omega and for each one I'm going to look at how far mig is from xig and square those errors and say I want this to be less than some tolerance epsilon.

So instead of requiring me to match my observed data exactly, I just want to be close within some epsilon here. Um, and so in many real world settings, this is more the the the setting that we're interested in. And we'll talk more about how to choose parameters like epsilon um next week. But for now, you can just think about this as a userdefined tolerance level. How much error you're willing to tolerate. Okay, so this all sounds well and good, closely related to concepts we have been talking about all quarter.

Um, intuitive and interesting. But now we have to think about how do we actually solve this optimization problem. And the problem that comes up is that the way I've written this okay besides not having enough space on the board is that this is just totally computationally intractable. So the rank of a matrix is this discrete quantity in the sense that I could take a matrix that's say rank two and just make a tiny little change to one entry and it's possible that suddenly it becomes rank three, right?

It can jump very quickly. The rank can jump very quickly even when I make very tiny changes to the matrix M. And so that's kind of one intuitive explanation for why trying to minimize the rank like this can be a very challenging search problem. And so what we're going to consider is an alternative sort of relaxed version of this optimization problem that is computationally tractable. Okay. Oh well, okay. Before we get to that, I want to give an illustration just so that we're all on the same page.

So I am going to have sort of my say um observed matrix X and in my example here did not think about drawing this on the board when I wrote my example. I have got six different movies and five different customers. And in here, my first movie has ratings one, one, um, two, zero, and then something is missing. Then I've got a missing entry. 2 3 1 3. And then in my second one, I've got one, three missing, two, three. And then I've got one missing 31 missing missing three and missing four five 33.

Okay. So imagine that I now want to fill in the missing entries. So I want to drive home the point that there's infinitely many ways I could fill this in, right? I could create a matrix X exactly the same size that's consistent with the observations I just showed you. One 1 2 0 6 9 2 3 1 3 1 3 0 2 3 1 3 1 2 5 6 Okay, I've just like filled in totally arbitrary values. I now have a matrix here. Let's call this a bad x hat where the rank is equal to five.

Right? I have produced no structure in this matrix. I've just filled in totally arbitrary guesses for these missing ratings. But alternatively, I could try to find a good x hat that has rank equal to two. And so, let me show you what that might look like. Okay. One, one, one, one, one, one, one, two, three, two, five, four. 2 3 4 3 6 0 1 2 1 4 3 and 3 3. Okay, so maybe even by inspection you can look at this and say, "Oh yeah, I can believe that this is rank two.

I've got two columns here that are just weighted versions of one another. If I look at the third column, it's just the sum of the first two columns. And if I look at this fourth column, it's the difference of the first two columns. So I can write every column in this matrix as a weighted combination of the first two columns. It's rank two. And it's also completely consistent with my observations. And so this is our goal.

Our goal is to say take a matrix like this where we've got a ton of missing entries and find a matrix that has low rank and is consistent with those entries. And in the context of you know this sort of conceptual understanding we've been building up the idea is that these two columns could represent our two representative movie watchers taste and I can think about every other customer in my customer base as being some sort of combination of those two. >> Yes.

Is there ever a case where we want to change the customer data like for this sake of getting a smaller rank by changing like let's say a rating from two to three it's not that significant of a change but then maybe >> right so the question is would we ever want to maybe like change the customer data to get an even lower rank like maybe I can just alter some of these um entries and end up with a matrix that's even lower rank.

So, I'm going to be really picky about vocabulary here. We never ever ever talk about changing the data because that can suggest something that's fraudulent. But what we but the conceptually I think you're 100% right and that is what I was trying to get at here. So if we go to the top and we say we want to ma match our data exactly then we're very constrained to um uh what kinds of matrices we can consider but here I'm giving myself a lot more latitude.

So I am saying here like let's just say epsilon is one then what I could do is I could say yeah I'm going to allow one of those entries to have a rating that's in m to have a rating that's one off from the entry in x. So now I am changing my estimate and I'm giving myself more latitude in my estimate but never changing the data. Yeah. Yes. >> Like an identify if you quantify that somehow like if you had a less sparse initial matrix more certain.

Okay, this is an amazing question, really insightful. So the question was, if you didn't hear it, is there an identifiability issue? So in particular, for instance, could there be multiple different matrices that are consistent with this and have let's say rank two and so that I can't really figure out which one is the right one. And I think when we first started having this matrix completion literature, a lot of attention was devoted to exactly that question.

Under what conditions is there a unique solution and does minimizing the rank give me what I think of as right? And the answer's a little bit complicated um and we're not going to be able to go through it in this class. But it will depend there in order to ensure that there is a unique solution. um we would have to make assumptions about where the missing entries are. So for instance, if I had an entire column that was missing, there's no way I could really recover that because I have no information about that, let's say, customer, right?

If you come in as a new customer to Netflix and I know nothing about you, there's no way I can make a predictions about what movies you're going to like. Um so we start to have to make assumptions about how many missing entries there are and how they are distributed, where they're located. And at the same time, we're going to have to make assumptions about if I if I think about these columns as spanning a subspace, what that subspace is.

Um so, um you know, for instance, here's a rank one matrix. That's kind of nasty, right? I've got a one up here and everything else in the matrix is zero, right? So this is a rank one matrix, but it's also very hard to do matrix completion on this and to find a unique solution. So I need to start making assumptions about sort of the orientation of that subspace that's spanned by the basis um represented by the columns of the matrix.

So all of that's to say this is an amazing question. There's a deep literature about it. If you want pointers to papers, I'm happy to provide them, but it's a little beyond the scope of what we'll do here. >> Yeah. >> So, if we have like less like empty empty like positions, then it is less likely for us to find a lower brand. So, like for example, for this observation, if we only have one empty tree, then like what if we can't find like a rank smaller than five?

So, um, the question is, imagine that instead of having a bunch of missing entries, I only had one missing entry, just one entry that I'm trying to fill in. Um, so first of all, people wouldn't spend nearly as much money on that problem. But that said, um, you're saying, okay, well, what if there's just nothing I can fill in there that gives me a rank that's less than five? Um, and that's entirely possible. Um, so I think what we're saying here is let's assume that the true X is low rank and then how can we find that low rank matrix?

If the true matrix is not low rank then there's not going to we're not these methods are not going to work. So we're saying under the condition that this low rank model is a good model then how can we actually find that low rank matrix fit? Yeah. So right now we're trying to minimize rank and the problem with that is it's quantized. It would be possible to instead have some function like that takes all the sigas like sigma 1, sigma 2, sigma 3 from the sp and then tries to make it apply some kind of function so that it tries to make the uh later sigas as small as possible. >> That's fantastic.

That's exactly right. We already said that the rank of a matrix corresponds to the number of nonzero singular values. And so when you say, well, is there something else that we could do with the singular values that's going to make things more computationally tractable? That's 100% right. It's the next thing next board that I'm going to write. I'm just answering questions first. But great insight. Yeah. when we talk about like representative customers likely >> the way I've been stating this the um customers are columns but I don't know I mean it doesn't matter a lot >> but it doesn't matter because both >> that's right the rank of the like if I think about the columns spanning a subspace and the rows spanning a different subspace um the dimension of those two subspaces are always the same and equal to the rank.

So we can think about a number of minimum number of representative movie watchers. But if we wanted to, we could flip that on its side and we could say, well, what's a representative set of movies where, you know, I can think about each movie across customers as representing how I would predict how other movies um uh will be liked by my customers. I I find that a little less intuitive, but it's it's certainly a valid interpretation.

Okay, so let's talk about an alternative to this rank minimization problem that's going to be computationally tractable. So first I'll talk about the basic concept. Um yeah and then we'll talk about a specific algorithm that you can implement. Okay. So to start I want to define um the trace or nuclear norm of a matrix. So in particular I'm going to take my matrix X. I'm going to have this norm symbol like we've had for other norms.

And then I'm just going to have a little star subscript for it. And this is going to be equal to the sum over all the singular values. So from one to the minimum of n and p of the sigma i's. Okay. So I'm just adding up the singular values. Um I do want to just as a reminder recall some other aspects of matrices that we've looked at. So in particular the rank of a matrix X was equal to the number of nonzero sigma I's which I could write equivalently as summing from I = 1 to the minimum of N and P and then just having a one whenever sigma I is greater than zero.

So now I can contrast the nuclear norm with the rank. So with the rank I'm looking at all the singular values and I'm just adding in a one every time the singular value is non zero and a zero otherwise. And here I am just adding up the raw values of the singular values. And so this is helpful because for instance with a very small change in my matrix entries I could have a singular value go from non zero to zero or vice versa with just a small change because this is always going this rank is always going to be integer valued.

But if I were to make a small change in my matrix resulting in a small change in one of the sigas that'll have a relatively small effect on this nuclear norm. And so it's going to be easier now for us to search among matrices that have small nuclear norm instead of searching among matrices that have small rank. I also just want as a reminder to try to connect different um ideas that we've been covering in this class.

We've also talked about the probinius norm of a matrix. Um and we aren't really going to need this today, but just to have this all in one place. For the fbinius norm, I would also sum over all singular um entries in the singular value matrix. So from i from one to the minimum of n and p and here I would have the sigma i's squared and then at the end I take the square root. So all of these different matrix norms as well as the rank can be expressed in terms of my singular values.

Okay. But in the context of matrix completion then what we are going to do is the following. I'm going to say that my x hat is the matrix argument that minimizes. So again I'm searching over matrices m that are the same size n by p as x. But now instead of minimizing the rank, I'm going to try to minimize the nuclear norm of M. And again I can say this is subject to Xig is equal to MIG for all I J in this set omega. So we've got something totally analogous to what we did over here with the only difference being instead of minimizing the rank, we are now minimizing this nuclear norm using that as a proxy for the rank that's going to allow us to have a computational computationally efficient algorithm.

Similarly, I could have my x hat be the argument over all matrices of the right size of the nuclear norm subject to the sum over allig pairs in omega of mig - xig. J squar being less than epsilon. So I can give myself this extra latitude in terms of matching the data that we had when we were doing rank minimization. And then there's one final variant that I want to talk about um very briefly where I could say my xhat is the argument ment that minimizes when I search over all matrices of the right size.

Um, and now I'm going to have this nuclear norm. And instead of having this constraint that my entries have to match my observations, I'm going to write it a little bit differently where I'm saying I want to minimize two the sum of two things. One is the nuclear norm and the other is going to be the errors when I try to fit my data. So I sum over i and j in omega and I look at xig j minus m i j squared. So now what I want to do is I want to find a matrix m that is minimizing my sum of squared errors and simultaneously this nuclear norm or at least minimizing their sum.

These things can be on different scales or I might want to have different levels of error tolerance. And so typically what people will do is they will multiply the sum of squared errors by a parameter lambda that users need to use data to figure out what the best value is. Again, we're going to talk later about how to choose values for parameters like lambda or epsilon, but for now, imagine that you have a good value.

So this allows us to say instead of having these kind of hard constraints that we need to satisfy, I instead just want to minimize the sum of these two measures of um I don't know error and uh proxy for rank. >> Yeah. >> So for the trace we talk about the trace I heard of is the sum of the diagonal terms of the matrix. Is that the same trace as this trace? So this is the trace norm, not the trace of a matrix. And the trace norm is this sum of singular values.

Yeah. Okay. So now let's talk about one specific algorithm that you can use that is um Okay. So now let's talk about one specific algorithm that you can use to solve this optimization problem and it is called singular value thresholding. Now there are many algorithms for solving this problem and depending on how big N and P are. This might not be the best choice but I think it is particularly simple and evocative and it uses the singular value decomposition in order to form form this minimization in a way that I think really illustrates the usefulness and importance of the singular value decomposition.

So the input of this method is going to be x omega. So I am inputting all of the entries of x where I have an observation and I have knowledge of what omega is where where I have an um observation. I'm also going to have a threshold towel and a um stopping parameter epsilon. So tow and epsilon are both scalar values greater than zero. So the first thing I'm going to do is initialize. So my initial matrix Xhat is going well Xhat in general is going to be my running estimate.

And when I initialize I'm going to set the J entry of Xhat as follows. If I J is one of the entries that I observe, then I'm just going to fill in the actual observation. And for everything else, I'm just going to fill in zero. Now to set up some notation that's going to simplify the presentation of the algorithm in just a second. I'm going to equivalently write this initialization procedure as follows in two steps. First I'm going to say xhat is just going to be a matrix of zeros of the right size.

So n by p. Oops, excuse me. And then I've got a semicolon here. And then after that I am going to fill in all of the entries that I observe. And so I'm going to write this like this. And what this means is I'm going to take all the observed entries of X in those omega locations and I'm going to fill in the corresponding entries of Xhat in the same locations. So the result of these two steps starting with all zeros and then mapping all the ox omegas all the observed entries to the corresponding locations in xhat that yields exactly what I'm describing in the earlier line but we're going to use this notation for simplicity in just a second.

Okay. So the way that this method is going to work is the following. while not converged we are going to do the following. So first we are going to keep track of our estimate from the previous iteration. So I'm just going to call that x old. We're going to do this so we can figure out whether we have converged to a good solution or not at the end of our loop here. Once we've done that, we are going to um compute U and sigma and V transpose by taking the singular value decomposition of our current estimate Xhat.

Once we do that, as you might guess from the title of the algorithm, we are going to threshold some of the singular values. So in particular we could say well for j = 1 2 however many singular values we have a minimum of n and p we are going to have a new sigma hat i j or i i because we're only working with the diagonal values and that's going to be equal to either sigma ii whenever whenever sigma i is greater than my threshold tow and otherwise for all of the small singular values I'm just going to set them equal to zero.

Once I've done this for each one of my singular values, then I can um reformulate or reconstitute my x hat by looking at u sigma hat vranspose. And so now I'm using the same left and right singular vectors. All I've done is I've thresholded or set to zero the small singular values. So my original xhat here might not have been low rank, but by doing this thresholding I have reduced the rank of the product. And so my new x hat here is low rank.

But through this process, I have now changed all of the entries perhaps just by a little bit. But I might no longer be fitting my data. And so now what I'm going to do is I am going to use the shorthand we established. I'm going to take all of the entries in omega where I have an observation and map them into the corresponding entries of xhat. And then finally if xhat and xhat old are very close to each other. So for instance, if the frobinius norm is less than my stopping parameter epsilon, then I am going to stop.

So I just keep on iterating until I have completed this process to the point where I've converged to something where from one iteration to the next I've barely changed my estimate at all. And so what's happening here is that in the um in this step I am mapping my estimate to something lower rank than I had before by thresholding these singular values. And then I am updating my estimate to be closer to the data. And I'm going back and forth between these steps pushing myself to my estimate to being a little bit more low rank and then pushing it to fit the data again. then pushing it again to be a little bit more low rank and then pushing it um to fit my data again.

Um I would mention though that this singular value thresholding method is very easy to implement. You can see it's just sort of a few lines of pseudo code. And personally, I think it's illuminating to just try it out on some toy matrix and to look at every iteration what happens at both steps. Right? So you start with your zerofilled matrix. You do this singular value thresholding and see how much that changes your original zerofilled matrix and then of course you fill in your entries.

And you can just like look at these matrices across your different iterations and see how they're gradually getting something that's lower and lower rank and you're getting away from this zero field initialization. Um, super easy to play around with on numpy or python. Any other questions? All right, have a great weekend and I will see you all on Tuesday. Hi, may I ask you just a quick