Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
[SIDE CONVERSATION] GIREEJA RANADE: Okay, let's get started with lecture.
Welcome back from Thanksgiving break. I hope you all took the time to rest up, and relax, and get some sleep in.
So we're now at lecture six for module 3. And today's lecture is going to be building on what we talked about last time.
We're going to be continuing our discussion of the orthogonal matching pursuit algorithm.
And this is basically allowing us to touch upon different concepts from machine learning that you'll be able to explore if you take upper division classes in the department.
The next lecture will continue to build on and introduce you to some different ideas from machine learning.
And you should really think about these last three lectures as kind of bringing together everything we've been talking about from the entire semester.
OMP and these kinds of algorithms really are thinking about, well, let's take a real world problem, let's model it mathematically, let's understand how that mathematization brings out the properties of the real world problem that we're trying to solve.
Then, let's put our design caps on and let's think about how we can design algorithms using these mathematical models to actually achieve the outcome that we want to do.
And now, once you have algorithms, once you have data, this final bit of machine learning is saying, well, if I have a bunch of data that I've somehow collected from the real world, how do I understand what is the right model for it?
How do I understand how to process this data? And OMP is kind of right in the middle of this, right?
It's thinking about, how can we design a system that will actually allow me to identify what are the devices that are transmitting?
So today, we're going to talk — continue talking — about orthogonal matching pursuit, or OMP.
And just as a reminder, the last homework was released today. So you're basically done. This homework will be due in exactly a week.
So you have a week to do it, not just four days. It'll cover primarily OMP as well as some — touching upon some more machine learning ideas.
The problems have a lot of description to them because they're trying to give you some context around what's going on.
But a lot of it involves really understanding how some of these algorithms are actually implemented and run. So there's a heavy IPython component to some of the problems.
And hopefully that will give you a sense of how all of the mathematical tools that we are developing can actually be used and implemented in real algorithms. So hope you enjoy the homework.
There's some — quite a few fun problems on it. There's a last problem that we're doing some final tweaks on and it'll be released today.
Okay, so with that, let's get into the rest of the lecture. So what was our setup for OMP? We were talking about the internet of things, right?
And we were thinking about how we could identify, or how we can build a device that could identify different devices in your home that might be on and transmitting.
So let's say you wanted to build a smart home and you wanted to have a Home Box or a device that would collect and understand which devices are transmitting and which devices are on.
So you want your TV to talk to your Home Box, you want your light switch to talk to your Home Box, you want your light bulb to talk to your Home Box, you want your refrigerator, your toaster, your pen, your computer, whatever else.
Every single device you want to be able to get a status update on what is happening, what is the situation in each of these devices?
And so presumably, there's going to be millions, if not billions of these devices that might want to communicate.
In the home situation it might not be billions, but if you're thinking about this exact setup in the case of a smart city, where you have — you're trying to detect a number of different vehicles that are driving around, and you want to have — excuse me — further coordination with the traffic lights, the different sensors, maybe there's environmental sensors in the picture.
So we're really thinking about a situation where you have many hundreds of thousands, millions, billions of devices that are actually trying to transmit, and you're trying to identify what they're saying and what's going on.
Of course, even though there might be these many, many devices around, at any given time, probably not all of them are trying to say something.
They're only trying to say something when something interesting is happening around them. So at any given time, we want to work under the assumption that, well, maybe there's a smaller number of devices.
Maybe we have a sparse signal. Sparse means that if I have, let's say, a signal, and it's zeros and ones, sparse means that the number of ones is small.
So in this case, if I have a large number of devices that are potentially transmitting, if I'm saying that my problem is sparse, or my received signal is sparse, it means that it only has inputs from a few devices.
Is everyone clear about the set up of the problem? Okay.
And we want to be able to basically use what we understand about gold codes and our different signatures to be able to solve this problem, right?
So let's say every device uses the gold code. And a gold code has a finite length, right? It has some length.
In the problems that we've been talking about, our gold codes have had length 1023.
And so let's say every device, whenever it's transmitting, whenever it's on, tries to send out its signature. So let's say you have some device, s1.
Maybe this is your TV. And it has some gold code of length of 1023 that is some long signal like this, right?
It's really long. I'm not going to draw out all of this. And maybe your other device, you have a light bulb, and this is — let me call this s1, S2.
And this has some other — these are the different gold codes of the different devices.
And so on and so forth for maybe all devices that I have. I think last lecture we use the sample number 10,000. So let's say we have 10,000 different devices.
Maybe this is your flower pot or your flower that's transmitting or something. You have all these different devices and they're transmitting.
We want to now figure out which ones are transmitting, and let's say, at what amplitude? So if I go here, can you see this?
Can people see this? Yes? Okay.
Okay.
We, our Home Box — let's call this Home Box. How you draw Home Box? Home Box is receiving a signal.
This received signal is basically, let's say, alpha 1 times s1, plus alpha 2 times S2, plus alpha 10,000 times s10,000.
Every device, whenever we receive a signal, every device could be transmitting, right? We know most of them aren't, but every device could be transmitting.
So if a device isn't transmitting, how can we model that in this setup? Well, alpha value would be choosed for a device that isn't transmitting.
STUDENT
[INAUDIBLE] GIREEJA RANADE: 0, right? Alpha 0 would represent that a device isn't transmitting. So if most of the devices are not transmitting, that means that most of these alphas are 0, right?
Great. We know this, but if we look at the problem generally, how many unknowns are there in this? I know the gold codes of every single one of these devices.
I have my received signal r, and I want to basically figure out these alphas, right? I want to figure out which device is transmitting, and maybe what's the amplitude.
How loudly is it transmitting? What is the modulation on top of that?
So my unknowns here are alpha 1, alpha 2, all the way up to alpha 10,000. Right? So I have 10,000 unknowns.
So typically, if we wanted to use techniques from module 1 to solve this problem, how many equations would we need to be able to figure this out?
STUDENT
10,000, right?
GIREEJA RANADE
10,000, right? There's 10,000 unknowns. We need at least 10,000 equations. Do we really want to be able to — we want to be in a situation where we have to collect 10,000 equations?
Probably not, right?
So what we want to try and do is we want to use the structure, use the structure of the signals to reduce number of measurements.
And we've already started to introduce structure into this problem, right? We're not having the transmitted vectors the arbitrary things. They're actually transmitting these structured gold codes, right?
And so we know that basically these gold codes have these properties, that the inner product of a gold code with itself is very large, but the inner product of a gold code with the gold code of a different gold code, or a gold code of a different device is very low.
Right? So we are putting this structure in. So that's one aspect the structure that we're putting into this system.
A second aspect of structure is the fact that we know that most of the alphas are 0. Right? We know that we only need to figure out a few of the alphas.
Everything else is going to be 0. And we want to try and use this to build up our problem.
So if we write this out, what we have, basically, is I have — I can just write this as a matrix equation where my matrix has the columns s1, S2, this is a column, this is a column.
And let me call 10,000 is capital N. So this is a matrix. What are the dimensions of this matrix?
How many rows are there in this matrix?
Okay, take a minute and figure out what the dimensions of this matrix are if the gold codes that are being transmitted are of length 1023 and we have 10,000 devices.
Talk to your neighbors and make sure you're on the same page.
[SIDE CONVERSATION] Okay, so what are the dimensions of this matrix?
How many rows are there?
STUDENT
[INAUDIBLE] GIREEJA RANADE: 1023, right? What is the length of the vector, s1? 1023, right?
Is everyone on the same page? Like, this is important that you see why this is true. How many columns are there? There's one column for every device.
Right? So there is 10,000 columns. Okay, now, let's put our unknowns.
Our unknowns are alpha 1, alpha 2, alpha 10,000. How many unknowns are there? 10,000 unknowns. Right?
What is going to be the length of our received vector?
STUDENT
[INAUDIBLE] GIREEJA RANADE: 1023, right? So we have our received vector, r.
This, again, is of length 1023 because we're adding all of these signals of the same size.
So we have the number of equations is 1023.
Number of unknowns 10,000.
So I can write this, basically, as this s, this matrix, s let me call this matrix s [INAUDIBLE] times vector alpha is equal to vector r.
But s is not a square matrix. So it can we invert x? Can we invert s? No, right?
Cannot invert s. So now what do we do?
Right, we have this received signal. We know that this structure exists in this received vector, r. But we can't invert it. It's not a square matrix.
So what do we do in this situation?
Any thoughts? Any ideas on how we could go about doing this? Yeah?
STUDENT
[INAUDIBLE] GIREEJA RANADE: Can you speak up a little?
STUDENT
[INAUDIBLE] and like, we assume that they're [INAUDIBLE].
GIREEJA RANADE
So can we reduce the number of signals so that it becomes a square matrix? That's an interesting idea, except we wouldn't know how to reduce them, right?
Because we might remove some of these signals, but that device might actually be the device that's transmitting.
So if we could do that, ideally, we want to somehow stay one-by-one by the process of elimination that, well, this device is more likely to transmit, and this device is less likely to transmit.
And in that way, we're going to build exactly on that idea in spirit.
STUDENT
This is just an idea, but I know that if you did s transpose s you would get a square matrix.
GIREEJA RANADE
If you did s transpose s you would get a square matrix. That's an interesting idea. We could try and do at least squares approach here.
But what you'll find out is that s transpose s will not be invertible. It will have a non-trivial null space.
So it's something that's worth doing out, but what you'll see is that you basically have a lot more empty dimensions than you have full dimensions.
So even though the matrix is square, it turns out to be not invertible. And that's why the least squares technique does not work.
But it's a good idea, and this idea is used in other algorithms that you might come across in the future. We're just not going to use it right now.
Yeah?
STUDENT
[INAUDIBLE] column of, like, your s matrix with the the r [INAUDIBLE] wanted to know which one is [INAUDIBLE]..
GIREEJA RANADE
Great idea. This is the idea that we want to really use, which the idea is saying, well, if, let's say s1 is present in r.
If this alpha 1 is equal to 1, what's going to happen when I take the inner product of s1 and r?
If alpha 1 is equal to 0, what is this going to be?
This is going to be, basically, this s1 is going to disappear because alpha 1 is 0. And what are the inner products of s1 and s2, s1 and s3, s1 and s10,000?
They're all pretty small, right? They're not very large values. So the inner product of s1 and r, if alpha 1 is 0, is going to be pretty small.
On the other hand, if alpha 1 is not equal to 0, we're going to have all these small numbers because of these guys. Whoops.
We're going to have all these small numbers because of these guys, but we're going to have this non-0, big non-0, because of s1.
If we do this out we're going to have s1 in our product.
Let's say, alpha 1, s1, alpha 2, s2, alpha 10,000, s10,000.
And this is equal to basically — this is equal to alpha 1, s1, inner product s1 plus alpha 2, s1, inner product s2, plus all this other stuff.
And all of this stuff is going to be small, but this is going to be very large.
And as a result, this inner product is going to be large.
Yes, question.
STUDENT
Is this reliant on having a lot of the devices off? Because if they're all on, won't the small gold codes add up to [INAUDIBLE]?
GIREEJA RANADE
Good question. The question was, does this rely on a lot of the devices being off? Because if they weren't off, would all of these small things add up to something big?
It turns out that gold codes are designed strategically enough that even if you had a lot of the devices on, it still wouldn't be so much that it would overpower the correlation, or the inner product of s1 with itself.
But it's exactly important to design signature so that this does not happen.
So in a generic case, you might indeed end up with this problem, which is why it's important to have these signals be well-designed. Yep. Good question. Other question, yeah.
STUDENT
Why is it that we're taking the inner product instead of circularly correlating the other vectors?
GIREEJA RANADE
Why is it that we're taking the inner product instead of circularly correlating the other vectors? Circular correlation is not in scope for the semester.
And so there are many different ways to solve this problem. We will talk a little bit about how we can connect this to circular correlation later in the lecture.
But effectively, they're doing the same thing. If you want to read about circular correlation you can in the notes, but you don't need to worry about it.
STUDENT
So are we assuming that the rest are small because they're all 0s?
GIREEJA RANADE
Are we assuming that the rest are small? No, we're not assuming that the rest are small because they're all 0s. We're not assuming anything about the alphas. What do we know about gold codes?
We know about gold codes — this is true for any gold codes — that inner product of s1, s1 is large, and inner product of s1 with s2 is small.
Right? This is exactly what you saw in the homework where you did the GPS receivers, right? Do you remember that from that homework problem? So we're relying on that property.
Yeah.
Yes?
STUDENT
Why is the first one small again? The alpha 1 is 0?
GIREEJA RANADE
If alpha 1 is 0, we basically have inner product of s1r is equal to alpha 2, s2, plus is equal to inner product of s2 with alpha 2, s2 and so on.
There is no s1 component for something large to pop up because alpha 1 is 0.
Okay. Everyone with me here?
Other questions? These are all good questions. Okay.
So the idea that was proposed and that we're implementing, is saying that, well, let's see which of the signals are present by doing this inner product. Right?
And by doing this, we will see that if we get these large correlation peaks like in the GPS homework, then we can identify that that device is transmitting.
If everything's kind of at the noise level, then we're going to say that the device isn't transmitting. So great. Let's say we did this, right? We do the following.
We take our received signal r and we consider all of the inner products.
rs1, rs2, all the way up to rs10,000.
Okay? So some of these will be large and some of these will be small. What should we do now?
What we want to do to be able to pick out, now, which device is transmitting, is we're going to say, well, maybe let's see which of these is the largest.
And the one that has the largest absolute value — remember the alphas can be positive or negative. So the inner products can be large but have positive or negative sign.
And we want to say, well, we'll find the one that is the largest. And say I declare that this signal is present.
One-by-one, our strategy is to say, one-by-one, let's kind of say which devices we think are there and rule out the others.
So if we say, let's look at, now, find that signature with max inner product.
Declare the device is present.
So let's pretend that we actually computed all of these for sum r, and we got that inner product of rs2 was the largest.
Okay?
Let's say we did this. We now declare that device 2 is present. Right?
If we see this, we declare device 2 is present.
Because we got this large correlation, the only way for this large correlation to show up is if there was something, some transmission from this device 2. Otherwise, everything's going to be really, really small.
So great. We're very happy. What do we do next? We have one device.
Are we happy? Do we go home? There might be just one device transmitting, but there might be a few more, right? We might want to figure out, what are the other devices transmitting?
Let's say you were told that at any given time, four devices are transmitting. You want to find four devices that are the most likely to be transmitting. Okay?
So I want to now try and understand the relationship between r and s2.
The question I want to ask is, how much of r is explained by s2?
Right, you've seen that one device is present and you're saying, well, how do I find the next one?
If you think about it, let's say you have a lot of people talking in the room and there is one really loud voice.
There's one person who's talking really loudly and there's another person who's trying to say something but is whispering something really, really quietly.
Both of the people are talking to you, but if this one person is talking really loudly, can you always hear the other person who's talking quietly? You can't, right?
So if you wanted to somehow figure out what the quiet person was saying, what could you do? You would want to somehow have this other device stop, right?
So let's try and do that. Let's try and remove the contribution in your received signal off this loudest device that you've just identified.
Does everyone see how we're trying to think through what the next step might be? This is exactly the kind of — this is a design thinking process for an algorithm.
We're not designing a circuit here, or a device here. But we are thinking step-by-step. We have a goal.
What are the tools that are at our disposal and how can we use them to progress forward in our task? So how much of r is explained by s2?
We want to understand this. And if we think about it in a vector perspective, well, let's say I have my vector s2 here. I have my vector r here.
This is the same question as saying, well what component of r is along s2? How much, how close can I get to r by walking along s2?
Basically, I want to figure out if I have r, r I want to say is approximately equal to alpha 2 times s2.
And there's plus some other stuff, right? That's why I'm writing this approximately equal to sign here.
How do I figure out how close I can get to r by using just s2? This is a problem we've solved before, right? What's the answer here?
STUDENT
[INAUDIBLE] GIREEJA RANADE: Projections, right?
So we project r onto s2. This gives us alpha 2 hat, which is our estimate of this constant alpha 2.
And this is basically, we know from our derivations in the earlier lecture, that this is r2s2 divided by s2 squared.
Right? This is basically this point where, how much do I walk along s2? This is alpha s2.
So we know that we can explain this component of r by s2. What remains to be explained?
Is there a vector in this drawing that is the error or the remainder part?
It's the vertical line, right? This vector plus this vector gives me r.
So if I think about this vector here, and I call this vector vector e, then alpha 2 s2 plus e gives me r.
So now I want to say, well, let me look at this error. Let me look at this residual. Let me look at e and say, well, what are the other devices present in e?
Right, I've already figured out the devices that are, like, I figured out the one device that made the loudest noise. I put that away. Let me look at the next one.
So now you say what's left?
What's left is e, which is basically r minus alpha 2 hat, s2.
Now, what do you want to do? Once you have this residual, this error — we call this the error, or the residual.
You, again, have this library of devices and their signatures. How are you going to figure out what is the next loudest device?
STUDENT
[INAUDIBLE] GIREEJA RANADE: Rinse and repeat, right? Do the exact same thing.
We can, again, now say, okay, let's consider the inner products of, again, do we want to consider inner products of r and s1, r and s2?
STUDENT
[INAUDIBLE] GIREEJA RANADE: No. We want to now consider e and s1, e and s2, e and s10,000, right?
So now consider inner products.
Okay? I'm going to pause here. Questions?
STUDENT
So when we do inner product of e and s2 again, don't we already know that s2 is present?
Is there — GIREEJA RANADE: Yes, we will know that e and s2, that the inner product of e and s2 is present. I'll get to that in just a second.
Yes?
STUDENT
[INAUDIBLE] GIREEJA RANADE: Yes. The question is about the minimum threshold that we want to look at for these inner products. And I'm guessing you're getting to how to stop.
We'll talk about that in just a minute. Good questions.
But before we get to these kind of next step questions, I want to make sure everyone's with me on the steps that we've done so far.
Does everyone understand how we've arrived at where we've gotten to? We're good to move on? Yes? No?
STUDENT
[INAUDIBLE] GIREEJA RANADE: Okay, ask your neighbor a question. I feel like there are people who are confused, potentially. So I'll pause. Ask your neighbors questions.
[SIDE CONVERSATION] Okay, any questions for me?
Yes?
Sorry, speak up. Everyone, I can't hear.
STUDENT
[INAUDIBLE] GIREEJA RANADE: Great question. Can you explain why least squares doesn't work in this situation? So let's look at this matrix s, right?
s is basically what we call a wide matrix. There's lots of unknowns and very few observations. Very few equations, right?
Least squares we typically use in a situation where we have lots of equations and very few unknowns.
So if I have many, many equations and maybe there's some noise in them and I want to get rid of the impact of noise, I can use least squares in a setup like that.
In this case, I have these very few equations. And so my matrix is not the right shape for least squares.
And as a result, if I try to take s transpose s, this matrix, this will not be invertible because it will have a non-trivial null space.
Yes. Question?
STUDENT
As a follow-up to that, does that have to do [INAUDIBLE]?
GIREEJA RANADE
Yes. You can prove that basically by showing that if you have lots more columns than you have rows, you're going to have linear dependence. And so that is not going to be invertible.
Exactly the right track.
Yes?
STUDENT
Say there were three signals present in r, and then that first space when you pick out the strongest one, wouldn't there still be a peak when you take the first inner product of the second signal?
GIREEJA RANADE
What do you mean by second signal?
STUDENT
[INAUDIBLE] say like you take the largest peak, right? But wouldn't there still be a peak present?
GIREEJA RANADE
Yes. The question is, aren't there going to — if you have two devices that are transmitting, aren't you going to have two peaks? Yes, you will.
You will pick out the largest peak first, then you'll pick out the second peak the next time. And we'll see that an example in just a minute.
STUDENT
So why can't we just pick out all the peaks from the first inner product?
GIREEJA RANADE
Great question. Why can't we just pick out all of the peaks from the first inner product. The reason is, sometimes you can get spurious peaks.
Sometimes you can have — noise can distort things that will give you spurious peaks.
And doing this one-by-one allows you to make sure that you're explaining away the maximum component.
It's not wrong to do that, but you will see, also, in some examples, that sometimes even when there's two devices transmitting, the second peak is so small that you won't see it at all.
You won't be able to distinguish the second peak from the noise. So an example will clear that up, hopefully. We'll do it in just a minute.
Okay, so now we're on to — we've understood this part, we're now considering these inner products with e with s1, e with s2, so on and so forth.
And there was a question of, well, do we really need to compute this inner product of e and s2 again? What is e? e is, remember, equal to r minus alpha 2 hat, s2.
So if I consider the inner product of e and s2, this is equal to the inner product of r minus alpha 2 hat, s2 and s2.
I'm just substituting what e is. This is equal to the inner product of r and s2 minus alpha 2 times the inner product of s2 with s2.
Everyone following me here? Just algebra. But what is this alpha 2 hat? This alpha 2 hat, we know is the projection, right?
We know it is the scalar that comes from the projection.
So if I substitute that in — minus r s2, s2 squared.
What is the inner product of s2 with itself?
STUDENT
[INAUDIBLE] GIREEJA RANADE: The norm squared, right?
What is this equal to?
STUDENT
0.
GIREEJA RANADE
0. So we can technically do 9,999 inner products instead of doing 10,000 inner products if we really wanted to because we know the answer to 1.
Right? We know that because we just subtracted this part out, that the inner product of e with s2 will always be exactly 0. Does that answer your question?
Okay. So we do this, we find all these inner products, and we see that, basically, s2 is going to be 0. But there is a bunch of others, right?
Maybe there there's another peak, maybe there isn't. So let's say the next peak, what device you want it to be?
4? Something. Okay, say peak, next max was s4.
The question is, what do we do now? There was a question in the front row. Yeah?
STUDENT
We might be getting this eventually anyway, but I was going to ask, so after we do a couple iterations of this, like the next couple of [INAUDIBLE],, will the new error with s2 inner products, they'll be 0 every time?
GIREEJA RANADE
Yes.
You'll see as this works up. Yep. Okay. So now let's say the next max was s4.
And this is where stuff starts to get even more interesting. Now what do we do? So what seems like the right next step here?
We now know that r has some component of s2, and we are also declaring that it has some component of s4.
Right? Both of these are now present.
So I know that basically r is equal to sum alpha 2 times s2, plus sum alpha 4 times s4, plus some other stuff.
I've already projected r along s2. And I removed that contribution.
One choice I have would be to say, well, let me now project — do the exact same thing. Project e onto s4.
And that would be just basically doing exactly what I did here. But let's think about this a little bit.
Let's say I have, now, my vectors s2, and s4.
Okay? And let's say that plane is the column space of s2 and s4. Okay?
And I want to figure out how much of this r — how much of r is explained by a combination of s2 s4.
I could project r onto s2 and project r onto s4. But does that seem like the right thing to do given everything we've learned so far?
Linear combinations of s2 and s4, where do they allow me to go? Do they allow me to just be on this line and this line? No.
In fact, I can go anywhere in the plane, right? So by using combinations of s2 and s4, I can actually be anywhere here.
So saying that I'm restricted to only measuring r in terms of being exactly along this line and exactly along this line, seems suboptimal, right?
And in fact, it is suboptimal. Does everyone remember the discussion problem where we talked about orthogonal columns of the a matrix?
And what you saw there in that discussion problem — if you don't remember it, it's an important discussion. Please go back and review it.
And what it says was that basically if you want to recover a two-dimensional projection from a one-dimensional projection, you can only add two one-dimensional projections together if the columns of a are underlying orthogonal.
But we don't know that s2 and s4 are exactly orthogonal. We know that they're close to orthogonal.
So what we want to do given that we know that we can be anywhere in this plane, is we don't want to project e onto s4.
If we projected r onto s2, we have this e here. Like, this is really complex — I don't know, this is the plane. This is r, this is s2, this would be e, right?
Does everyone see that?
And then, if I had some s4 over here, I could project this e onto that s4, but it would make more sense to just project this r onto this plane here.
Hopefully people can visualize that. But what we're trying to do is basically do exactly a projection. How close can we get to r while moving in this plane?
this is a problem that we've, again, solved. So we're going to say project r on to column space defined by s2 and s4.
So this, again, if I say, let me call this matrix s, let me call s. Make one column of it s2, make the other column s4.
I can write this equation, again, in terms of this matrix, s, right? I can say s times alpha 2, alpha 4 is equal to approximately r.
Right? Does everyone see how I got here?
And now, we can use a projection, or essentially a least squares, right?
Now, we basically have a situation where we're not — we don't have fewer unknowns and we don't have too many unknowns and few equations.
We actually have reduced it to saying, well, let's pick out the two devices that we think are most likely to be there.
How much of the signal can we explain using the signatures of just these two devices?
This is now a least squares problem. This we can solve. And so we can say that — we can write — let's say we write this as s vector alpha is equal to r.
We can use least squares or projection to solve this and say that our best estimate of the vector alpha is basically this matrix s transpose s, inverse, s
transpose times r. Right? So it's important to remember that, here, we're not projecting the error vector e. We're projecting r.
Okay? Question? Yeah? STUDENT: so I have a question about if you could maybe eliminate the component of s2 from s4 and then project it?
GIREEJA RANADE
Yes. The question is, could you eliminate the component of s2 from s4 and then project it? This type of — this modification in the OMP algorithm is possible.
It requires a slightly more advanced technique than we're covering in the class, but you will learn how this works in 16B. So just hang on. This is doable.
We're just not going to do it right this moment. Good question. Yes, at the back?
STUDENT
[INAUDIBLE] GIREEJA RANADE: Volume, volume.
STUDENT
Sorry. [INAUDIBLE] take the products of s transpose s if you have [INAUDIBLE]?
GIREEJA RANADE
The question is, how do you know that when you take the inner product of s transpose and s that you're going to be able to invert this?
Remember, now, s transpose has 1023, s has 1023 rows and 2 columns. So it's a tall matrix.
Which is why you know that it's invertible. And we're designing the gold code so we know that these columns are not linearly dependent.
Yes?
STUDENT
So [INAUDIBLE] s4 [INAUDIBLE] error left over after taking out [INAUDIBLE] And then from that you go back to your original r and do the compilations that you just did there?
GIREEJA RANADE
Uh-huh.
STUDENT
Okay.
GIREEJA RANADE
Yep. Perfect. Okay, so now people get a sense of this, right? What are you going to do next?
You're going to identify a third vector. you're going to now compute another error vector. You're going to do the inner product again.
You're going to identify the third vector, so on and so forth, right? So let's look at this in an example, which I think will also help clarify a bunch of people's questions.
Could I — perfect. Thank you.
Do I need to press something to have my laptop screen show?
Okay, I'll take a question while this is being figured out, if there is one.
Yeah?
STUDENT
If we took the gold code 39, so that the columns will be linearly independent?
GIREEJA RANADE
The gold?
STUDENT
Like at the — GIREEJA RANADE: Yes, the gold codes are not multiples of each other.
STUDENT
So is that like any, like, [INAUDIBLE] GIREEJA RANADE: Yes, all the gold codes are linearly independent of each other. Okay, let me try something. Does this work?
Lecture [INAUDIBLE]. Nope, [INAUDIBLE] in HDMI1. Does this work? No.
Nope.
STUDENT
[INAUDIBLE] GIREEJA RANADE: Okay, could I have at least one of the dock cams back in the meanwhile?
Okay, thank you. Okay, let's move on to something else while this is getting figured out.
Could you try to figure out the — Jason, could you try to figure out this thing? Okay, thank you. I'm fine if I can just have the full screen as the computer as well.
I'd prefer to have it split, but if not, I'll make do with the full screen. Okay. So we've talked about this algorithm assuming — yes?
STUDENT
[INAUDIBLE] Okay, so for the first section we have [INAUDIBLE]?
GIREEJA RANADE
Yes, but — the question was for the first method, do we have — for the first vector do we have to use projection and for the rest, we can use least squares?
The answer is that projection and least squares are exactly the same thing. So even if you did least squares in just the one-dimensional case, you would get the right answer.
You can use least squares every single time.
STUDENT
But [INAUDIBLE]?
GIREEJA RANADE
Sorry, there was a different s. There were two different s's. I was using the word — I overloaded s. This s is different from the s that I'm constructing.
This — let's call this — yeah, this was a different s. Sorry, let's call this matrix a.
This has all of the signals here. That one just has 2 or 1. Does that help? Okay.
Okay, so we have this — okay.
STUDENT
So I got slightly lost when you said rinse and repeat, and then you came up with a slightly different process to do the same thing.
GIREEJA RANADE
It was not slightly different. Okay, okay, okay, so when I said rinse and repeat, what did I say? Good. So you have s2.
And like you projected r onto s2.
STUDENT
[INAUDIBLE] GIREEJA RANADE: So projection onto s2 is exactly the same as doing the least squares.
Basically, you can think of this, again, as — this is also a least squares set up, right?
You can rewrite this as s2 times alpha 2 is equal to r, approximately. ax approximately b.
So this is also at least squares. So I basically take this r and I project it onto s2. I say, how much of r can be explained by s2?
Then, I have two candidates. So I say this. Now, I have come to a case where I have two candidates.
So now I say, how much of r can be explained, not by just s1 or just s2, but by the combination of s1 and s2.
STUDENT
But weren't we going to stop at the first peak [INAUDIBLE]?
GIREEJA RANADE
So we took the first peak, we removed this impact, and now we're looking at a second peak. So now we're saying we have two devices.
I wish this thing would work, in which case we could actually show this.
STUDENT
And now we have another device. If we stop that, how did we end up with two devices now that we stopped that?
GIREEJA RANADE
We picked one device, we put it in our pocket. Then we looked at all of the other devices and we said, okay, what's the next loudest one?
We picked that and we also put it. Now these two, s2 and s4, we're trying to use in a combination to explain r. So we're picking them one-by-one.
We're collecting devices one-by-one. We're not saying, let's look at all the peaks and let's collect all of the devices.
Question here?
STUDENT
So we're saying that the gold codes are designed to [INAUDIBLE]?
GIREEJA RANADE
Yes, you will have to design — there's a limit on the number of devices you can have based on the length of the gold code.
If you want more devices, you need longer gold codes.
STUDENT
[INAUDIBLE] problem you were trying to address originally, why [INAUDIBLE]?
GIREEJA RANADE
Not really. Let's take that offline. Yeah.
At the back?
STUDENT
If e has no component on s2, why don't we project e on s4?
GIREEJA RANADE
If e has no component on s2, why don't we project e onto s4?
STUDENT
[INAUDIBLE] GIREEJA RANADE: Right.
Because we want to have — because that would still — like, you can do the math out on that and you will see that the right thing to do is actually just project r onto the combination.
So you don't want to just have things explained one-by-one because you might see a change in how much the component on s1 is when you have two explanations.
So I hope this will work. This will answer your question.
STUDENT
[INAUDIBLE] GIREEJA RANADE: So when you say — when I say I know r is equal to alpha 2, s2, right? I only have an estimate on alpha 2.
It's not exact. So when I say that, actually, r is a combination of two things. The original alpha 2 that I had a calculated might not be the right alpha 2.
It might actually change. That's why you don't want to project e onto s4.
Thank you. [APPLAUSE] Yay.
Okay. So what do I have here?
This is basically a bunch of code that is not important to understand, but what I wanted to go to and show was here. So can people see this?
So what I have here, is I have three gold codes, okay? And this is my received signal.
And my three gold codes are — my received signal is basically these weights are telling me I'm taking 100 times the first gold code, 10 times the second gold code, and 1 times the third gold code.
And that's giving me my y. So what are the values of my y? My y is 91, and then minus 111, minus 89.
So that's basically the values of this y. So when I look at this y — if you had to just guess by looking which gold code was present, what guess would you make?
STUDENT
1.
GIREEJA RANADE
1, right? Would you guess that there were other codes that were also transmitting?
STUDENT
[INAUDIBLE] GIREEJA RANADE: No, right? So just by pattern matching, it seems like the right answer is 1.
So let's actually go through and take cross-correlations and taking inner products and see.
Okay, so here, what this plot is saying is this is the inner product of gold code 1 with the received signal.
Inner product of gold code 2 with the received signal, and inner product of gold code 3 with the received signal. Which is the largest inner product? 1.
So which device are we going to say is transmitting?
STUDENT
1.
GIREEJA RANADE
Great.
So what we're going to do now, is we're going to do what we did before, and we're going to project the received signal onto the gold code of device 1, and we're going to say, well, how much can we explain of the received signal
by looking at just the gold code of device 1?
And what we see is that when we do this projection, we see that we basically have these orange peaks are what our reconstruction says.
So this is the alpha 2, this is the alpha times the signature. And the blue is the actual received signature. So here, this alpha calculation — I'm doing the projection calculation.
And remember, our original weight was 100, right, on the first signal. But what do we get as the actual weight? What is our best guess? We get 98.2.
So it's not perfect. There's this error, because there are these other signals that are mixed in. Okay?
So we're going to say, okay, well, we'll take everything that we can explain about the first signal and about the received signal from the first signal and remove that.
And this is now the error vector. I look at this error vector and I'm going to compare it now to my three gold codes.
What do you think is the next loudest device that's transmitting?
STUDENT
2.
GIREEJA RANADE
2. Okay, so let's again do this. And let's look at the actual inner products. This is the inner product with device 1.
As predicted, it's exactly 0. Inner product with device 2 is very large. Inner product to device 3 is fairly small, but it's not 0, right? It's not 0.
Okay, so let's now try and explain the received signal. This blue is, again, the original received signal.
What the orange is doing is it saying, let me now use combinations of the first two gold codes to explain. I'm not saying, let me just explain one-by-one.
And now if you look at the least squares weights that I'm getting, what am I getting? I'm getting 100.1 and 9.8.
So I've improved my estimates on the weights of these different alphas is actually better because I'm doing a simultaneous projection onto the column space of both of these vectors as opposed to just one.
And now if I looked at my area vector, it's much, much smaller.
Is everyone with me here? And now, again, I do my cross-correlation — I do my inner products, and I get, basically, 0 here, 0 here, because I've removed those components.
I expect 0s there. But now I see this 1. I see a high peak here. Okay, let me look at what's remaining.
And I basically get a perfect reconstruction. I rigged this up so that there's no noise added in the system. In reality, you would get some noise remaining afterwards, right?
Which now comes the question of, like, how do you decide when to stop in this algorithm? And basically, there's a couple of different ways.
One is you can say that I know, let's say, the sparsity level of a signal.
I know the sparsity level of a signal, and as a result, I can use the sparsity level and say, if I know how many devices are transmitting, once I've collected those many devices, I'm going to stop.
Alternatively, you can say, well, I know what the level of ambient thermal noise around it. I know it what kind of the noise is.
So I say, like, I keep looking at the norm of the error vector e.
And if the norm of this e vector — every time I kind of remove parts, once it gets small enough that it's smaller than the noise level, then I can stop.
So when to stop is really this kind of engineering design decision that depends on the specific application and the specific noises that may or may not be present in your particular system.
But does this demo help answer some of the questions that people had? So this is why you want to project onto both of the signals at once.
And this is why it doesn't really make sense to say, well, let's just look at all of the peaks at the first time, right?
If we took just all of the peaks, how do we decide what is and isn't a peak? Sometimes it's really not clear what is and isn't a peak.
In this case, it's clear that this is a peak, but it's hard to tell which of these two is a peak or isn't a peak.
In fact, here, this is actually smaller than the correlation with device 3, but 2 is actually the louder device. So that's why we have to do this peeling off one-by-one.
Yes, red jacket?
STUDENT
Why was it necessary for us to do this with the loudest device [INAUDIBLE] Wouldn't it have done the same thing if [INAUDIBLE] GIREEJA RANADE: The question was, why did we do this with the loudest device each time?
So when we had — we did the correlations — we had this correlation with device 1, this correlation with device 2, this correlation with device 3.
If we had chosen to subtract off a different signal, we wouldn't have, like, basically, if you have — think about the analogy with the two people talking.
There's one person that's really loud and one person that's really quiet. Let's say there's two people that are really quiet and one person that's really loud.
Even if you remove one the quiet people, and you kept the one loud person and the one quiet person, you still wouldn't be able to hear the second quiet person.
So to be able to hear the quieter voices, you need to take the biggest one out first. That's why you start with the loudest. Yep?
STUDENT
Wouldn't that just take out [INAUDIBLE] GIREEJA RANADE: You would not get the right answers if you didn't do this. Yeah.
STUDENT
Okay, so if you had a large number, or a larger number of vectors, or [INAUDIBLE] GIREEJA RANADE: So every time — good question — every time you basically just pick out
the one next loud peak. You don't add 2, and 4 — every time you just add 1.
STUDENT
So like, so if you had, so [INAUDIBLE] GIREEJA RANADE: Onto the column space of 3.
Great question. So now if I have three signals, how do I do this least squares? What is being done here?
So when I do this final signal, when I'm doing the final signal, the least squares that's being done here, this least squares is now the s matrix there has three columns.
So the dimensions of s keep increasing. So you keep stacking these columns on, one after the other. There's a question here somewhere. No.
Okay, question in the back.
STUDENT
[INAUDIBLE] GIREEJA RANADE: 1023.
If I have a gold code of 1023, I can encode far more than 1023 devices.
I can, in fact, encode approximately 2 to the 1023 devices using, not exactly to that exact calculations completely out of scope for this class, but you can actually encode far more.
Okay. Question?
STUDENT
Does the noise vector ever [INAUDIBLE] GIREEJA RANADE: Does the noise vector — STUDENT: Can the noise vector ever be louder than, like, [INAUDIBLE]?
GIREEJA RANADE
The question was, what if the noise vector is louder? If the noise vector is much, much louder than the signals that are transmitting, your toasted. Nothing you can do.
The thing is, reality is that you will design your alphas so that what you're saying is actually louder than the noise vector.
Okay, so I'm going to move on just because there's one more thing that I want to get to.
So we've talked about, now, this OMP algorithm and the implicit assumption that we made when we were doing this was that every device wakes up and decides whether or not it's going to transmit, right?
And everyone just talks at the same time. We didn't really incorporate any kind of delays in this picture. But what would happen if we did have delays in the situation?
What if there was some transmission delay between my device and my receiver?
Just like in the GPS setting, where there is a transmission delay, and this also carries some kind of information.
If you think about it, there's actually not that much different that we need to do. So we want to think about delays in transmission.
And what happens is, let's say I have some gold code s1 of n, and this is the following.
Let's say it's just of length 3012, but when it arrives at the received signal, it is actually — it arrives with a delay of 1.
So this is now s1 of n delayed by 1. We've already seen this kind of delays in signature arrivals in the GPS setting.
This is not something new that you're seeing for the first time, the question is, if we have these delays, is there something that we can do nonetheless?
In reality, what will happen is that these devices will not be just waking up transmitting just exactly one gold code and then going to sleep, right?
We pretended that for the development of our algorithm, but in reality, what's probably going to be the case is that your gold code is going to be constantly transmitted.
So it's going to be like this.
0, 1, 2, 0, 3, 4, 5, minus 1, minus 2, minus 3. So on and so forth, right?
The device is constantly transmitting its gold code. And maybe you received a delayed version of this.
So you receive instead of 0, 1, 2, 3. Sorry.
I messed that up.
So I receive this at 1, 2, 3. This is 0. 4, 5, 6. So on and so forth.
This is — okay? What if you have these kind of delayed situations?
What you would do in this case is actually not that different from what you are already doing. What is the property of gold codes that you know?
There's two properties of gold codes that are useful, right? One is that gold code s1 inner product with itself is large.
Gold code of s1 with the gold code of a second device is small.
But if I take gold code s1 with delayed s1, this is also small.
So now, given that we want to figure out which devices are transmitting and there might be some delays.
They might not all exactly start transmitting exactly at time 0, what might you be able to do?
Any ideas? Someone who hasn't spoken yet, maybe? Yeah.
STUDENT
[INAUDIBLE] GIREEJA RANADE: Could we use the same cross-correlation procedure as before? And the answer is, essentially, yes. Because let's say I have my received signal.
I have my received signal r, and I used to take just the inner product of the received signal with my s1, right? I would take these inner products one-by-one.
But instead, I can take inner product of r and s1, and I could take inner product of r and s1, let's say, delayed by 1.
So this notation, s2 of 1 means s1 delayed by 1.
And I could consider inner our product of rs2 — or s1 delayed by 2.
I could consider inner product of rs1 delayed by 3, and so on. How many delays do I need to consider if my gold code is of length 1023?
1023, right? Because I cannot disambiguate beyond that. We already know that. So I can consider all of these delays.
So instead of considering just r1 inner product s1, I'm going to consider all of this. What else am I going to consider?
I'm going to consider r1 inner product s2, and r1, or r inner product s1 delayed by 1, r inner product s2 delayed by 2, and so on.
So I'm going to consider inner products with all the different gold codes at all the different delays.
Now, I'm going to say, which is the maximum? Then I'm going to say, well, whatever that maximum is, let's say that device 2, again, was the maximum.
I will say, well, what is the delay at which it is the maximum?
So s2 at delay 3, let's say, was the maximum. Then I say that, well, I know now that s2 delayed by 3 is the signal that I'm going to try and remove.
Right? So instead of now just computing 1023, I would compute a lot more inner products. But effectively, I'm doing exactly the same thing.
And I'm going to basically peel things off one-by-one in exactly the same way. So there is nothing really that is going to change very much.
But what you can now do is you can basically incorporate the idea that, oh, in fact, there might be a little bit of delay in the system as well.
So with that, I'll end, and the last lecture is on Thursday. [APPLAUSE]
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.