The Bold Blueprint Podcast
The Bold Blueprint Avideh Zakhor To unlock your true potential
Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. I'm Victoria Cash. Thanks for calling the Lucky Land Hotline. If you feel like you do the same thing every day, press 1. If you're ready to have some serious fun for the chance to redeem some serious prizes, press 2. We heard you loud and clear so go to luckylandslots.com right now and play over a hundred social casino style games for free. Get lucky today at luckylandslots.com. No purchase necessary. VGW Group, void rep prohibited by law. 18 plus. Terms of condition supply. Okay so first announcement is you got to download the first chapter of the book off of our webpage. Is there some more obvious? In the handout section of our webpage. So that's the first chapter. We're going to remove it at the end of the day just so that we don't get into issues. There's a homework deal. It's a written assignment next week, next Friday and let's see. Wednesday is February 1, 2, 3. So that will be February 3 and it's from chapter 1 of Jay Lim, 128, 130, 133, 134 and 135. Just a little bit of warning. This assignment is pretty long. It's probably the longest or perhaps the time consuming homework. You'll have this semester I think. The lab assignments are probably shorter than this. So don't leave it to Thursday night and Cindy has office hours, Tuesdays and Thursdays and so you're going on it a little bit earlier than you would otherwise. Then just so that you know, the next assignment is going to be on tomography. And we got started a little bit late simply because although not compared to the last time I taught the course, simply because the book wasn't available at the beginning of the semester. So let me begin by asking if there's any questions or comments. Okay. What I'm going to talk, let me number my pages so that we're all numbered. What we're going to talk about in today's class is reconstruction of signals in general but most specifically images from partial information. In particular, partial Fourier information. So last time, last time's lecture was a special case of that. We talked about reconstructions of signals from their projections. You get projection in time domain and you use that in order to, I mean you get the projection in the space domain and you use that to reconstruct the entire image. And today what we're going to talk about is two classes of reconstructions. One of them is reconstruction of signals, discrete time signals, two-dimensional in particular from their Fourier transform magnitude. And then we also talk about reconstructions of signals from their Fourier transform phase. And then we wrap up by talking about reconstructions of signals or images from their level crossings. In particular, just zero crossing. And then move on to reconstructing signals or images from multiple level crossings. Which happens to be my PhD thesis many years ago. So I'll start with some motivation. Why do we care about, why do we care about the problem of reconstruction from Fourier transform magnitude? If you can zoom in here. Well it has a lot of, I'll define exactly what I mean by magnitude and get mathematical in just a second. But for now you can think of it as I have some signal X of n and it's the discrete time Fourier transform is X of omega. It's summation of X of n times e to the minus j omega n. And suppose and that X of omega is a function of continuous variable omega, right, in the frequency domain. And suppose I knew X of omega magnitude of it everywhere. Or a lot of places. Not just at n points, if I'm having an n point signal. But suppose I knew X of omega at 2 and 3 and 5. I had arbitrary number of points. And the question is knowing the magnitude only of Fourier transform. Can I get back the original signal? That's what the problem of reconstruction from Fourier transform magnitude means. And I'll write these things down when we get to the analysis part. So it becomes a little bit more clear. But just so that you know you know what the applications are. There's great many applications where it's easy to capture Fourier transform magnitude. But computing phase or not computing. Capturing phase or measuring phase is very difficult. Especially at very high frequencies like at optical frequencies. So this problem has applications in like electron microscopy, crystallography, optical astronomy. And as I said the motivation is that in a great level of applications you just don't have a phase information at very high frequencies. And sort of a bit of a history of who did what in this field. What I'm going to show in just two minutes or five minutes is that if you have a n point finite support one dimensional discrete time signal you can show that there's two to the n sequences that have the same Fourier transform magnitude as that signal. So even if you had the Fourier transform magnitude of that one dimensional signal from that you couldn't uniquely recover that signal. There's an ambiguity factor of two to the n. I'll show that in just a second. And people have known that for many years 30, 40, 50 years. But what Monte Hays in 1982 showed was that you could reconstruct multi-dimensional signals just from their Fourier transform magnitudes. So theoretically if you knew the magnitude you could be able to up to a factor of two and the beauty factor of two reconstruct the signal. And I'll show that result in just a second as well mathematically. And there is a bunch of algorithms that people have proposed. One of them is the error reduction algorithm by Gertzberg and Saxton. Hybrid input algorithm by Fennep at Erem who at the time was at Erem. And also a non-intuitive algorithm by Davis Relevitz that appeared in 1988. However even though mathematically Hays showed that you can do unique reconstruction from a practical point of view all of these techniques and non-iterative techniques could only be applied to small signals. That means signals with a small regional support. I don't know, 10 by 10, 20 by 20 but not 512 by 512. And furthermore the iterative algorithms generally stagnates. So in general this problem of reconstruction from Fourier transform magnitude even though theoretically has been shown to have a unique answer or almost a unique answer factor of two ambiguity in practice this is supposed to be an ill-conditioned problem for large sequences. And I'll spend a bunch of either today's lecture or Wednesday's lecture to explain to you what ill-conditioned means. There's a notion of ill-conditioned problems and then there's a notion of ill-conditioned algorithms. How many of you have heard of this word? One, two. Okay. And what that means is that if you perturb the Fourier transform magnitude just a little bit that results in a very large change in the recovered discrete time sequence. That's going to what ill-conditioned means. And so you might say well where do these perturbations come from? What are you talking about? Well perturbations come in as soon as you enter your data into the computer. Because the computer doesn't have infinite precision, plus your arithmetic operations inside the computer doesn't have infinite precision. So every time you act two numbers, be it imploding point or fixed point or whatever, there's a little bit of round-off ever introduced and that's the perturbation. And it's those perturbations that make the problem of ill-conditioned. And it would mean that the Fourier transform magnitude has to be specified with a great deal of precision and you have to have a great deal of precision and computation in order to get answers. What's in general, what's another example of a problem that's very ill-conditioned in real life? Forgive us signal processing all of that. We almost deal with it on a daily basis. You watch the news like if you're up at between 6 and 7 a.m. and watch the news you hear about it like a hundred times on all the channels. The weather, right? You can't predict the weather more than accurately, more than five or six days ahead, simply because it's an ill-conditioned problem, you need to know the initial conditions of the current pressure, temperature, etc. To infinite precision, if you want to apply mathematical modeling and predict it for many days ahead, that's why we can't tell you what the weather would be like exactly a year from now today. Simply because it's an ill-conditioned problem and you need to have very very precise input, extremely precise calculations, infinite precision, so that's another example of an ill-conditioned problem. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, a plenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. Hey guys, it is Ryan. I'm not sure if you know this about me, but I'm a bit of a fun fanatic when I can. I like to work, but I like fun too. And now I can tell you about my favorite place to have fun. Chumba Casino. They have hundreds of social casino style games to choose from with new games released each week. You can play for free and each day brings a new chance to collect daily bonuses. So join me in the fun. Sign up now at ChumbaCasino.com. Sponsored by Chumba Casino, no purchase necessary, VGW Group, board where prohibited by law, 18 plus terms and conditions apply. Talk about your condition problems and algorithms in today's lecture. So just I'll just wrap up by saying that in 1990 I did some work where I showed that if you have the four-year transfer magnitude of a signal, and as well as that, if you're just one bit of space domain information, just cross a signal in the time domain with space domain with a threshold and just tell me which pixels are above and which pixels are below. Those two to get the knowledge of those two can make the problem well-conditioned and can result in successful reconstructional signals. So let me now try to more formally introduce this problem and instead of waving my hands. So what we're going to talk about today in general is reconstruction of 2D signals from partial four-year information. And again why four-year because in great many physical applications, a four-year transform of signal is what you capture, is what you automatically get from your measurement system or from your data acquisition system. Four-year transform occurs in many applications in nature, okay. So the motivation is really that there's lots of applications like electron microscopy and astronomy, crystallography, et cetera, optical astronomy, crystallography, okay. And we're going to consider three distinct problems in this space. One of them is from four-year transform magnitude FTM, magnitude of the four-year transform. The other one is phase reconstruction from phase of the four-year transform. And the third one is reconstruction from level crossings of a signal in the space domain, okay. So let me begin from four-year transform magnitude case and talk about reconstructing signals from one-dimensional signals from from their four-year transform magnitude. Can you roll up just a little bit please, thank you. So recon from four-year transform magnitude and we're going to consider the one-dimensional case. So what we want to consider is a signal, a discrete time signal, this is a x of n, discrete time, that means this n takes on energy values, it's one-dimensional signal, it has n plus one, non-zero points, and it's non-zero specifically for, in this is zero all the way to n, okay. And what do I mean by reconstruction from four-year transform magnitude, but what I mean is we're going to, we know the discrete time four-year transform of x of n, which is x of omega, which is this summation n equals zero to n of x of n e to the minus j omega n. And this is, this is four-year transform magnitude and what I mean by reconstruction from four-year transform magnitude is that we know the magnitude of x of omega, we know this guy, okay. And remember this omega guy is a continuous variable. So if I were to plot a magnitude of x of omega for some signal, it would look like that. If this is the guy that's periodic with period two pi and it repeats itself here and here, but, but it's as a function of omega, this omega is a continuous variable. This is not a discrete, this is not a discrete signal or function, this is a function of a continuous variable, okay. So the question that we want to ask is if we know x of omega, can we get x of n back, okay. So the first thing that you're going to start asking me is that, well, in real life, even though x of omega is a function of a continuous variable, omega in real life, we don't know it at infinitely many samples of omega. We only know it at finally many, right? At the end of the day, when Bernard Boser puts his A to D's in, I don't know, x-ray detectors or various systems, he samples at discrete locations. He can't put infinite number of A to D's there or else his budget will go through the roof and nothing will work properly. So the first question I asked you, and I think the answer to this is pretty obvious. If I sample this x of omega, I'm magnitude of x of omega at n plus 1 points, suppose I knew the samples at n plus 1 points, can I then uniquely recover x of n? I'm saying magnitude of x of omega, not x of omega. Generally speaking, if you look at this equation, if I knew samples of x of omega at n plus 1 points, this is the one dimensional polynomial in x of n, and I can just find the coefficients of that polynomial, solve a linear system of equations and find x of n, right? Is that clear by just looking at this for everyone? But that's not what I said. I asked if I knew the magnitude of these guys, suppose instead of knowing x of omega itself at n plus 1 points, which would have enabled me to solve the linear system of equations to get x of n back, suppose I gave you the magnitude of it, can I then get back x of n? I see some nose, okay, that's correct, and why? It's very simple, because the phase can be anything, because I can assign some phase and solve a linear system equation to get one value for x of n, and then I can assign another phase values to those n plus 1 samples and get another x of n, and as many phases of x of omega, I can cook up for those n plus 1 samples of x of omega, I can reconstruct x of n that many different ways. Is that clear everyone? First of all, does everybody know about linear system of equations and stuff like that, right? So when I say I know x of omega at n plus 1 points, and x of n is related in a linear system of equations, if somebody doesn't know it, let me explain it now, so that we don't get into trouble like towards the end of the lecture. Is that clear or shall I quickly give a, yeah, I mean basically what's happening is, is this, is you have a matrix equation of x of 0 all the way to x of n, and here this is equal to x of omega 1, x of omega 2, or 0, x of omega 1, all the way to x of omega n plus 1, all I'm saying, and then there's a matrix here, which would be e to the minus j omega 0 times x of 0, times 0 times, and then e to the minus j 1 times omega 1 times x of 1, e to the minus j 2 times omega 2, all the way, and then the next row, sorry, these are all omega 0, omega 0, and then the next row is e to the minus 0 times j times omega 1, e to the minus j 1 times omega 1, e to the minus j 2 times omega 1, all the way, e to the minus j 2 times omega n, this is n. And the last row would be e to the minus j, e to the minus 0 times j omega n, e to the minus, sorry, this is omega 1 again. God, that makes so many mistakes, e to the minus j 1 times omega n, e to the minus j 2 times omega n, e to the minus j, n times omega n. So is everybody clear about this? So I multiplied this row by this column, I get this. So suppose, suppose that I had, suppose I had n plus 1 samples of x of omega, I knew that x of omega naught, I knew that omega 1, all the way up to omega n, then using this, I can just expand this equation for different values of omega naught. So for omega, for different values of omega, so this row corresponds to omega naught, this row corresponds to omega 1, this row corresponds to omega n. But this times that plus, this times that plus, this times that dot other plus, this times that equals this. So this is a matrix, this matrix times this vector. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty, and more. Come back for new deals rotating every week. Don't miss out on savings. Shop prime exclusive deals at Amazon Fresh. Select varieties. It's time for today's Lucky Land horoscope with Victoria Cash. Life's gotten mundane, so shake up the daily routine and be adventurous with a trip to Lucky Land. You know what they say, your chance to win starts with a spin, so go to LuckyLandslots.com to play over a hundred social casino style games for free for your chance to redeem some serious prizes. Get lucky today at LuckyLandslots.com. No purchase necessary, BGW group void were prohibited by law, 18 plus terms of condition supply. It equals this vector, this is a linear system of equations. It's called linear because our unknowns, in this case x of 0, x of 1, are entering the equations in a linear fashion. There's no square, there's no x of 0 squared, there's no cross terms, there's nothing like x of 0 times x of 1. There's no square root of x of 0, there's no 1 over x of 0. I mean, we all know what linear means, right? The linear system of equations, matrix time vector equals vector, and can we solve that or not? What do we know about solving linear system equations from linear algebra? We can solve this if it's inverse exists. Or other words, if it is, it's determinant is non-zero. And can we say something about determinant of this matrix? This is at the end of the more matrix, and the end of the more matrix is a special kind of matrix where you have, if you think of e to the j, for example, omega naught as variable, I don't know, p. So this is p to the 0, p to the 1, p to the 2, all the way p to the n. And think of this guy, e to the j omega 1 as q. So you have q to the 0, q to the 1, q to the 2, all the way q to the n. So this matrix has a special structure because it's of this form of each row being something to the power of 0, something to the power of 1, something to the power of 2, et cetera. That's called the vanema and matrix. And vanema and matrices have non-zero determinants. Provided, p is not equal to q. Provided that this, in other words, provided these omegas are distinct from each other. All right? And we do that already. I mean, where else have you seen a matrix like that? When you do DFTs, right? When I'm computing DFT, I'm just taking equally spaced samples of x of omega. And of course, we know the DFT matrix is definitely non-singular. You might have thought, well, it's non-singular because I'm taking equal samples, equally spaced samples of x of omega. But the answer is, it need not be. And in fact, what other reason do we have to believe that this is a non-zero, non-zero determinant matrix? Because we already went over this in the first lecture, or I forgot the second lecture, which is, this is a polynomial, right? These are the coefficients of polynomial. If I let e to the j omega be x, okay, then this thing can be written as summation from n equals zero to n of, oh, I only have x. Jesus, let's just call it y. x of n times y to, let's call y to the n. So this is a polynomial in y. And we already know that if you have a one-dimensional polynomial, if you sample it at n arbitrary points, you can uniquely recover the coefficients of that polynomial. Why? Because of the fundamental theorem of algebra, because it has, because you can factor it into simple terms, and, and because you can write the random one matrix. I mean, all of these things are related to each other, right? So we already know that sampling a, a one-dimensional polynomial at arbitrary points, polynomial of degree n, at, at, at n arbitrary points, results in unique reconstruction of the polynomial. And, and we know that because, because of all, because it, because you can form this random one matrix, and you know, random one makes it non-zero determinants, all those things. Is that clear to everyone? Yep. Okay, so now coming back here, so how do we get distracted to that? Well, staring at this, if I sampled x of omega at, at n plus one points, I could easily solve this linear sum equations. This is, has a non-zero determinant, and find these coefficients and I'm done. But my question was something different. I was asking, what if we know the magnitude of these guys only? And the answer is, well, if you know the magnitude, the phase for this--in order for me to recover x of 0, I would have to know the phase for this, the phase for all of these things in order to solve the linear system equation successfully and figure out what the x's are, right? And I can cook up any phase for this one, this one, this one, this one, this one, and depending on how I cook up and what I cook up, I get a different x signal, right? So indeed, if I sample this x of omega guy at n plus 1 points, the magnitude of it, I definitely can't reconstruct the signal, the x of n, right? Because I have a--I have a linear system of equations but I only know the magnitude at the right-hand side and the phase could be, you know, anything ambiguity on the phase, right? So coming back here--so coming back here, let's write this down. So if I know the magnitude of x of omega at n plus 1 points, I definitely cannot reconstruct the signal. In fact, the beauty factor is infinity. I can--there's infinitely many ways I can assign phase to these guys on each one and I get a different signal altogether. But the more interesting questions and that's why we even bother talking about reconstruction from Fourier transform magnitude is, what if I oversample in the frequency domain? What if instead of sampling at the magnitude at just n plus 1 points, I sample it at 2n, 4n, 6n, 8n, 10n? I know the value of lots of samples. In that case, it's true I've lost the phase information for the Fourier transform but I'm kind of trying to compensate for it by having more magnitude samples. So in the language of this linear system of equations, now I have a square matrix here and n plus 1 unknowns, n plus 1 unknowns. But what if I had just n plus 1 unknowns but on the right-hand side, I'll make it to have 2n or 4n or 8n samples? So the picture then would look something like this, would look, you know, a tall and skinny matrix times x of 0 all the way, x of n equals a tall and skinny vector which would be x of omega naught magnitude squared, magnitude of x of omega 1 squared all the way, x of omega n squared. And then here would be the usual rows. It would be e to the minus 0 times omega 0 e to the minus j 1 omega 0 dada dada e to the minus 0 j omega 1 e to the minus 0 j omega n e to the minus j 1 omega n dada dada et cetera. The same kind of matrix but this would be tall and skinny. So let's say this would be 4n and this would be 4n and this is just n or roughly n. So the fact that we have, we've lost phase but now we have more of these samples, can we reconstruct? Okay. And so question is can we reconstruct, can we uniquely reconstruct if we oversampled in the Fourier domain? And the answer here is that for one dimensional signals, it doesn't even matter that you oversample. There's, there continues to be an ambiguity factor of 2 to the n and for multi-dimensional signals you're okay, you could uniquely reconstruct. So that's what I'm going to show kind of the rest of the lecture. So, so the answer is for 1d signals, no, 2 to the n ambiguity factor for md signals, multi-dimensional signals, say yes. Even though in practice the algorithms have trouble converging and various other things. Okay. So let me, if you can roll back just a tiny bit so people can, great. So to show that, I'm going to introduce, so, so I'm going to start with the 1d case. I'm going to introduce the notion of article relation function. And this discussion actually becomes a little bit technical and would require you knowing the properties of Z transforms and other things like the back of your hands. If you don't follow it, don't worry about it too much but feel free to come and ask me questions at the end of the lecture. So I'm going to introduce this thing called article relation function for a signal x of n. And you've probably seen it elsewhere. So suppose I have r of n and summation over l of x of l, x complex conjugate of l plus n. So r of n is called the article relation function of x. And it has a Fourier transform. Okay. So, um, r of omega. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. It is Ryan here and I have a question for you. What do you do when you win? Like, are you a fist pumper? A woohoo, a hand clap or a high fiver? If you want to hone in on those winning moves, check out Chumba Casino. Choose from hundreds of social casino style games for your chance to redeem serious cash prizes. There are new game releases weekly plus free daily bonuses, so don't wait. Start having the most fun ever at Chumba Casino dot com. Sponsored by Chumba Casino, no purchase necessary, VGW Group, voidware prohibited by law, 18 plus terms and conditions apply, which is the discrete time of Fourier transform of r of n, which is r of n e to the minus j omega n. It has a Fourier transform that you can show is related to the Fourier transform of x and the following where it's the Fourier transform magnitude of x squared. So what that means is that inverse Fourier transform of x of omega is just r of n. So the question I'm trying to answer is if I know magnitude of x of omega, can I get x back? Well, that's kind of, if I know magnitude of, and I'm assuming I know that arbitrary large number of points, it, 2n, 4n, 6n, pick your choice. You know, you can have as many as you want it. Let's say we've asked Bernard Bozer to build a million, a ton of these A to D sampler and things. So we can sample this guy and infinite, if we wanted to, as many numbers as we want it. So the question really becomes, because x of omega squared is the Fourier transform of r of n, the question then becomes, if we know r of n, can we get x of n? Because knowing the Fourier transform of x of omega squared is the same as knowing the signal itself. We already went over that. If you know the Fourier transform of any signal, not just its magnitude, but the whole thing. Because, because this is the whole Fourier transform of r. So if you know this, we know r. So the question is, can you, can we obtain x from r? Okay. And you can already see why I introduced its autocorrelation function because of this lucky relationship. So now I'm going to take you to the Z domain and talk about the Z transform of r of n. So Z transform of r of n, which we denote by r of z, you can show because of the way we constructed r of n, is nothing but x of z times x complex conjugate of 1 over z complex conjugate. And by definition is summation of r of n z to the minus n. And this goes from n, little n going from minus capital n to plus capital n. Okay. So because, because of the way we constructed r of n, the extent or the region of supportive r of n is from minus n to plus n. Okay. And now I'm going to introduce one more terminology, which is just a big sounding name terminology, but it's in fact very simple. And I'm going to talk about associated polynomial to r of z. So associated polynomial. Yeah, sure. So what sum you wrote on the far right of that last equation is that the definition of what the Z transform is. Yeah, generally speaking, this goes from n minus infinity to plus infinity. But the reason I've limited it is because, because x of n has finite region of support and because r of n is built from x of n in this manner, r of n also has limited support. So generally speaking, yeah, it would go from minus infinity to plus infinity. But in this case, because of the assumptions we made on the extent of x of n and therefore extent of r of n because of this relationship, this is what happens. So is that clear? Any other questions? Yeah, please. So let's say you get the magnitude of x omega. Do you need just n plus one sample to recover r of n or you need more? No, you need, because it has two n plus one unknowns. So you need to, because r of n has two n plus one samples, right? So you need to, theoretically, you need at least two n plus one samples of x of omega in order to build r of n from it, right? Because of this argument that we just went through. Okay, no problem. All right. But again, in this discussion, we're assuming that we have plenty of samples that we can have. And two n, four, and, you know, this boser guy has given us all eight of these we ever wanted. So there's no shortage. We're not stingy on the samples. And that's why this result is kind of amazing, is that even if you knew x of omega at infinitely many points, you still, you know, you still couldn't figure out what x of n is. That's what's the gist of this argument is. Okay. So we'll talk about, associated polynomial to r of z. And we define it, I put this little triangle for definition, as, as p sub r of z, which is summation from n equals zero to two n of r of capital n minus little n z to the n. I'm just, it's essentially the same polynomial up here. I'm just shifting everything so that instead of the powers of z ranging from minus capital n to plus capital n, now it ranges from zero to two to the n. Zero to two n, sorry. Okay. So it's really nothing fancy about it. And the other, there's one observation I like to make about both, about r of n is that, is that r of n is a symmetric signal. We all know that, if you start with a signal, then you take it's our correlation function, you get a symmetric function. So these coefficients are symmetric, just by the virtue of the fact that they're resulting from a correlation process. And now invoking the properties of z transform, we can say that since the coefficients of this associated polynomial are symmetric, then we can have the following property in that if z0 is a zero of pr, then so is z0 complex conjugate minus one. So since pr of z, this coefficients of pr of z are symmetric, we can conclude that if z0 is a zero of p sub r of z, so is z0 complex conjugate inverse, which means that we can write, we can factor pr of z in the following form, if you can roll up, so half of the other pages is shown. Great. Thank you. So which means that we can factor pr of z as follows, as some constant, we just call it a, a product of a bunch of zeros, which we call zi, but then because if zi is a zero, this guy is also a zero, then you have another term here, which is one minus zi complex conjugate z, which is saying that zi complex conjugate inverse is also a zero of pr of z, okay, yeah, that's right. So what is, so what does all of these things mean? Well, what that means is, for example, let's just draw the, let me do one more, well, let me draw this, that's better. So suppose I have this as a unit circle, then, for example, if this guy has a zero z0, then it has also zero z0 inverse complex conjugate. If it has a z1, then it will have another one. If it has z1 here, then it could have z1 complex conjugate minus one out there, okay. So the last thing I want to define is a definition of a mirror polynomial, mirror of a polynomial rather, okay. So, and this is the last definition we need before we conclude this discussion, and it goes like this, associated with any polynomial, there is a mirror polynomial that consisting of the coefficients of the same one, but in reverse order and conjugate it. So, associated with any polynomial, there is a mirror polynomial consisting, hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh. Shop Prime exclusive deals and save up to 50% on weekly grocery favorites, plus save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty, and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. It is Ryan Seacrest here. There was a recent social media trend which consisted of flying on a plane with no music, no movies, no entertainment, but a better trend would be going to Chumbakacino.com. It's like having a mini social casino in your pocket. Chumbakacino has over 100 online casino style games, all absolutely free. It's the most fun you can have online and on a plane. So, grab your free welcome bonus now at Chumbakacino.com. Sponsored by Chumbakacino. No purchase necessary. VGW Group. Void where prohibited by law. 18 plus terms and conditions applied. Of coefficients in reverse order and conjugated. So, if I have P of Z, a polynomial that, for example, goes from N equals zero to capital N, P sub N Z to the N, then its mirror is given by P tilde of Z as summation from N equals zero to N, but now the coefficients of reverse order, that means it's P of capital N minus little N and then complex conjugate Z to the N. So, why did I introduce this mirror polynomial idea? Well, because now we can write down more generally the following thing in that if I have a, again, roll up so we can see the definition up here. So, if I assume I have a signal y of N that has autocorrelation r of N, and at this point it's not quite clear if y of N is the same as the x of N we started off with or not, but then we can write down the, it's associated polynomial P r of Z which we introduced up here, right? As a product of polynomial P y of Z and the mirror of it, P tilde y of Z. In other words, having defined what the mirror polynomial is in this kind of fashion, we can show that this associated polynomial for signal x that we came up with, which can be of this form and we diligently defined it like this, et cetera, et cetera. It's just a product of the one polynomial time it times its mirror. So, the, now the, the wider is 2 to the N possibilities becomes clear. If I come back to this picture and, and, and I've, I've put the pole zero, I've put the zeros of this polynomial in this picture right here, so there's, that's a z2 here, z2 complex conjugate minus inverse there. If I know r of N, the question was if I know r of N, can I get back x? And from this picture and from this analysis, you can immediately see that we can't. Why? Because if I know r, then I know r of Z. If I know r of Z, then I can build P r of Z, which is the associated polynomial. Now that associated polynomial has this kind of factoring, right? And what we're saying here is that, so when, when you factor this thing, all you know is there's a bunch of zeros for this thing all over the place, right? But it's very hard to know there is 2 to the N ways of associating each, for each of these zeros, let's talk about z0. You could have, let's see, there's 2 to the N ways to generate P of y given that you know P of r, okay? So if you have a signal, if you have a general signal y of N, and it has P of y and it has P y tilde, and all you know is P r of Z, which is this zero pattern that you see in this place, you don't really know, to associate with the signal, you don't really know whether this z0 is part of y as part of this, or whether z0 inverse is part of this or part of that. So for every one of these zeros, and there's N of them, right? For every one of them, either z0 could be part of this or z0 inverse can be part of that. So a tree branches in two. In either of these two conditions, either z1 is part of this or z1 complex conjugate inverse is part of this. Now we have four possibilities. Each of those four possibilities then look at z2. Either z2 is part of the signal or the complex conjugate inverse of it is part of the signal. That's now eight possibilities. So as I go through the zeros, what we're trying to say is that given P r of z, you can factor this thing two to the N possible ways. There's two to the N possible ways we can factor it. And therefore there's two to the N possible signals with two to the N combinations of zeros that could all have the same P r of z, which means they could all have the same r of z, which means they have the same r of N, which means there's the ambiguity that's going on. Is that clear? So in other words, what I'm trying to say is that there's two to the N ways depending upon whether you pick the zero to be inside, outside, each one of the zeros associated with P r of z. And yeah, when you look at P r of z, all you see, you can factor it out. You see a bunch of zeros. And you can't really distinguish to see for the original signal whether the zero, these zeros happen to be for the original signals, but all the two to the N signals that could have z0 or z0 inverse complex conjugate with zeros, z1 or z1, all of them have the same P r of z. And there's no way to know which of those two to the N signals were the original x of M were after. So I guess the missing link that I might have explained is that these z0, z1, et cetera, these are the zeros of the original signal. But we don't know, but it could be this one or it could be that, it could be this or it could be that. For every pair, it could be the original zero or it could be the one that's in-person and complex conjugate. So because of that, there's two to the N possible signals in time domain that will all have the same P r and therefore the same R. And that's what causes the ambiguity. So there's two to the N ways in order to generate P y of z. In other words, P y of z can be, let's say, square root of a, if, all right, because these two polynomials are the same, so square root of a and then the product of z minus zi and the product of another z minus z, zj, complex conjugate, but we don't really know what these indices are. i is in, the little i is in some set i and j is not in i and this i can be any subset of all the way 1 to N. So for example, I could have, if N is 5, I could have, I could pick 4 zeros here and 1 there or I could, and it could be any one of the 4 zeros and any one of the ones, I could have 2 here, 2 there, it's just a, there's 2 to the N enumeration of possible factoring of this thing that would result in 2 to the N different signals, okay? So at the N this P r, which is the same as this P y, can be factored in this, in this polynomial times this mirror but figuring out which zeros go to the polynomial and which one goes to its mirror is difficult and at the end that's kind of what prevents us from, from, from knowing which one of those signals there are. Okay, is that more or less clear? So any, I see a lot of, so you define this z transform and then it looks like you're, this associated polynomial, it's just like a shifted version of that. Right. And so, I guess I'm just confused, so the z transforms related to the transforms of the original, is the product of the transforms of the original function. R of z? Yeah, R of z is like the product of, R of z is z transform of r, right? And it has what, it has a bunch of zeros, right? And it, specifically it has two N zeros, right? And of that N of M belong to X. The zeros of R of z come in pairs, right? For each pair, let me, let me, let me write it in this sheet. So R of z has these pairs of zeros, z naught, complex conjugate inverse, z one, z one complex conjugate inverse, dar. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop prime exclusive deals and save up to 50% on weekly grocery favorites. Plus save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, a plenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop prime exclusive deals at Amazon Fresh, select varieties. Lucky Land Slots, asking people what's the weirdest place you've gotten lucky? Lucky? In line at the deli, I guess? I'd my dentist's office, more than once actually. Do I have to say? Yes you do. In the car before my kids' PTA meeting. Really? Yes. Excuse me, what's the weirdest place you've gotten lucky? I never win and tell. Well there you have it, you could get lucky anywhere playing at luckylandslots.com. Play for free right now. Are you feeling lucky? No purchase necessary, VGW, we're prohibited by law, 18 plus terms and conditions apply. All the way Z to the N, Z to the N, complex conjugate inverse, right? These are all the zeros of R of Z or PR of Z, it doesn't matter. They're all the same thing. And at the end of the day, X of N has N zeros, but each one of its zeros comes from each one of these pairs. Like its first zero or a zero can be, this one or that one. It's, second one can be this or that. Its Nth one can be this or that. Okay? So to build X of N, if you start from R of N and you want to get X of N, there's an ambiguity as to the first one. Is it this or is it that? So I can build two to the N signals that will all have the same R of N. Is that clear? There's two to the N possibilities for X of N that result in the same R of N. Because of this structure that R of N has, does that make it a little bit more easy to understand? Do they answer your question, Chris? Or still not yet? Okay. Question? I have two questions. First is, is the autocorrelation of, for autocorrelation goes back to the original function? I'm sorry, is the autocorrelation what? Autocorrelation of the autocorrelation gives us the original function. Autocorrelation of the autocorrelation gives you the original function. Right. No, because every time I take the autocorrelation as signal, its extent becomes double. So if I start with an end point sequence, it's autocorrelation as two end points roughly. And if I take autocorrelation at that, I get four end points. So I'm confused with the location of P Y X, which is really P Y X. P Y X. We have P Y of Z. Is that what you mean? Right, P Y of Z. Yeah. I think the only reason I introduced the mirror polynomial is to say the following is that this, you know what P R of Z was, right? The only reason I introduced this mirror business is to say that P R of Z can be written as a polynomial and its mirror. And right? Right. And given this structure for P R of Z, there's going to be two to the n ways I can do this factorization. That's all, there's two to the n possibilities for Y in other words. So depending upon which zeros of R, I pick to assign to Y. So did you assume that once you know P Y of Z, you can reconstruct that. That's right. But I'm saying there's two to the n ways I can do this factorization. Right. So the second question was, you mentioned there was an infinite number of possibilities when you have n plus one stand person. Yeah. But here you only have two to the n. Here I'm assuming, here I'm assuming I know I have many samples. Remember, suppose that this two to the n ambiguity was not even there. Suppose God came and told you, oh, this two to the n signal, that's the one. That's the one that corresponds to this, right? So then you can get R of n, right? But to go from R of n to X of n, well I guess by that time, you know what the answer is. See, the previous, the reason I said here, I'm assuming I only know n plus one samples of it, right? So if I want to solve the linear system of equations that as I had before, I can assign an arbitrary phase here. I can assign, you know, phase zero, phase pi over three, phase, you know, I can do, I can assign different phases to this and then solve the inverse, solve the linear system of equations to find X and I get a different answer. And this setup, on the other hand, I'm kind of assuming that I know X of omega at any point I wanted to. The two different, I can see why it causes confusion. There are two different setups. But you can see in this setup, if I pick one set of phase, I get one signal, like another phase, another signal. It's the linear system of equation where, on the right-hand side, instead of knowing the exact values, we only know the magnitude of what should be there. So you can assign arbitrary phase and based on what arbitrary phase you assign, you can get a different signal. I think perhaps, yeah, this picture kind of sums it up in a nice way is that these are the zero pairs of R of Z. And depending upon which one of these, in each stage, which one I pick for my signal, I can end up with two to the n signals. All of them have the same R of n. That kind of sums it up in a nice way. Question, yeah. So when you're using the autocorrelation method, you physically rely on the perfectly evaluating the autocorrelation function in time. So, and you need two n plus one samples to do that. Right, the question that was asked was, can I go from R of n from X of n? I mean, sorry, can I go, if I manage, let's see, yeah, this question here was, sorry, the question here was, if I know X of omega squared, in other words, R of omega. Let's call this R of, this is R of omega, oh, we've already defined it here. If I know R of omega, can I get R of n? That was the question that was asked. And the answer is, yeah, as long as you sample R of omega at two n plus one points, you ought to be able to get R of n. Yeah. So that means that if you have more than two n plus one samples of your magnitude of X of omega, it doesn't help you. Right. The problem is not going from R of omega to R of n, or going from X of omega squared to R of n. If you know X of omega squared, you can uniquely reconstruct R of n. That's not the problem. The problem is, that R of n correspond to two to the impossible X of, X's. In other words, if I have a correlation function, it could correspond two to the n possible discrete time signals could have the same correlation function. That's the crux of the matter. Yeah, so if I understand correctly, if you have a number of samples of X of omega magnitude. So if you have n plus one samples, then ambiguity is infinity. And then it's infinity until you know two n plus one samples, in which case it becomes two to the n. Okay. Two to the n. Right. But then after that, it's still two to the n. Yeah. That's right. That's exactly right. You got it. That's exactly right. So here, that's right. The ambiguity is not going from R of omega to X to R of n, or going from here to R of n. That we can do with two n plus one samples. But once we have R of n, there's two to the n possible signals that have the same correlation, autocorrelation function. That's the problem. Okay. So we're all convinced that the 1D doesn't work out, and we don't just pack up and go home. Now we're going to consider the two-dimensional case for Fourier transform magnitude. And what does that mean? Well, now we have omega one omega two that repeats itself periodically. It's doubly periodic. It goes from minus pi to pi. And now we're assuming that we know X of omega one omega two squared. And again, for simplicity, we're not going to be stingy with the number of samples. We're assuming we have, if our signal, if our X of n one and n two, we assume is n by n, it has n by n region of support. Okay? So we assume that we know X of omega one and omega two, and add more than n squared point. That's if 4n, 8n squared, whatever. And now we're asking terribly recover X of n. What has changed in 2D is that unlike one dimension, most two-dimensional polynomials are irreducible. That means they're not factorable. And I already talked about that a little bit in the first lecture. So in 2D, unlike in 1D, most 2D polynomials are what's called irreducible. Reducible means that they can be factor, irreducible, IR at the beginning means they can't be factor. That means they're non-factorable. In fact, again, Monty Hayes shows that, actually, you came from Georgia Tech. Did you ever take courses from Monty? Oh, no. Okay. But you've heard of it, Monty. Right. Good. In fact, Monty Hayes showed that the class of irreducible polynomials is of measure zero in the class of all... the class of irreducible two-dimensional polynomials is of measure zero in the class of all 2D polynomials. And if you close your eye, throw the door, pick a random 2D polynomial. Chances are 99.99. Hey, Amazon Prime members. Why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus, save 10% on Amazon brands. Like our new brand, Amazon Saver, 365 by Whole Foods Market, Aplenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. It is Ryan C. Chris here. People always say it's good to unwind, but it's easier said than done. The exception, Chumba Casino. To actually make it easier done than said. Or at least the same. Chumba Casino is an online social casino with hundreds of casino style games like Slots and Blackjack. Play for fun. Play for free for your chance to redeem some serious prizes. Sign up now and collect your free welcome bonus at ChumbaCocino.com. Sponsored by Chumba Casino. No purchase necessary. VGW Group. Voidware prohibited by law. 18+ terms and conditions apply. 99% that it is irreducible. That means it can't be factored. Simple language, most 2D polynomials just can't be factored. So, and he did his thesis. He used that fact to show, and I won't show the proof of it, but I mainly state the theorem that he came out with. This is 1982 approximately. That says the following. That says if X of N1 and N2 has irreducible associated polynomial, and we already know what associated polynomial means, it's just Z transform, but just shift it so that the powers of Z are positive instead of going from minus N to plus N, they go from zero to 2N or something like that, right? Under the polynomial, then all other Y of N, which have the same Fourier transform magnitude, are equivalent, and we're going to define what equivalent means to X, and equivalent means the following. We say Y of N1 and N2 is equivalent to X of N1 and N2, if any one of these three things happens. If Y of N1 and N2 is equal to e to the J theta times X of N1 and N2, and you can already see why that's the case, because the Fourier transform magnitude of this guy and the Fourier transform magnitude X and Y, if they're related in this manner, they're the same. So, there's an, there's an ambiguity factor of e to the J theta, but we can come away from conditions to easily remove that. We'll see that in one second. Another possibility for equivalence is that Y of N1 and N2 is, actually I, let me cross that out, I should say it's, I'm going to write it in one shot instead of multiple steps, is X of K1 plus or minus N1 comma K2 plus or minus N2. That has everything in one shot rather than multiple shots. So, let's, let's make few observations on this. Observation one is that if X of N1 and N2 has magnitude X of omega 1 and omega 2, then we know that e to the J theta times X of N1 and N2 also has the same magnitude, right? Mathematically it's very easy to show. So, this e to the J theta factor, whatever phase factor instead of is in, in the space domain in front of the signal is indistinguishable. But in a minute, we're going to, we're going to constrain our signal to be real and positive and that knocks out this e to the J theta. Observation two, I'm just giving you intuitive reasons as to why we have these, these things here and these things here. If X of N1 and N2 has, this corresponds to X of omega 1 and omega 2 magnitude squared. If, if, if, if, it's Fourier transform magnitude squared is this, then we already know that if it's shifted by K1 and K2 in the space domain, we get the same Fourier transform magnitude. We know that shift by K1 and K2 in space domain has the same Fourier transform magnitude. Okay? So that, so the shifting also causes a lot of problems. So, how do we, how do we, how do we try, how do we try to uniquely specify X? So in other words, let me, let me just try to roll back please so I can see half of the other sheet. I had a quick question. Yeah, sure. I don't know. In the past, whenever I, when you, when you add a phase to some function and then transform it, you shift the, the, the frequencies that the transform is evaluated at. If the, if the phase shift is this, is a linear function of the frequency, then it gets results in a shift. In a, in a, if, if either the J omega you put here is, is either J omega 1 times alpha, for example, then it corresponds to shift of alpha in this thing. Let me, I was going to say one more thing about this. Let me say that if it's a question still, yeah, did I answer your question? Well, actually let me, let me let you finish it. Go ahead. Yeah. If you say it's, if it doesn't shift the frequency, I'm talking about observation one where you add the e to the J theta and then take the transform. Yeah. Um, I've always thought that when you do that, you, you, you end up switching the frequencies that you evaluate the transform at. Oh, but this e to the J theta is, there has no n function dependency. It's a, it's a constant. It has no, it's, it's like, um, you know, theta can be zero and then it's one. Theta can be pi over two. It's, it's a, it's not an n depend, n one or n two depend on thing. Right. It's, it's just multiplying the signal by constant. Right. So did that clear? Okay. So looking at this observation here, uh, so if I shift by k one and k two in the space domain, I get the same Fourier transform magnitude. That means that if, if my original signal, for example, had this region of support as a function of n one and n two, now if I just shift the thing and n one and n two, then I get, I get the same Fourier transform magnitude. So no wonder there's an ambiguity still hanging and, and you might, with all the time, you might be getting very worried, but, but don't, we'll remove them. And then we have our observation three, which is, um, a rotation factor. And that's the one on the ud we're going to have a hard time getting rid of. And that is, if x of n one and n two has, of course, has a Fourier transform magnitude this, then one of n one and n two, which is x of n minus n one and minus n two also has the same Fourier transform. So what, what's our trick or how do we, how do we get rid of all these problems? Well, first of all, to fix, to fix this problem, to fix the, e to the j theta problem, if theta is anything but zero, it's, it's going to be, e to the j theta is going to be some sort of a, either negative or complex number. Like if theta is zero, it's one, if theta is pi, it's minus one, theta is pi over two is j, theta is three pi over two is minus j. So it's, it's most of the time it's going to be complex unless theta is zero or pi. So if I assume my original x is real, signal x of n one and n two is real. And in many applications, it's not a bad assumption to make. That means e to the j theta can only take on the value theta zero or theta equals pi. If theta goes pi, e to the j theta becomes minus one, theta goes zero, it becomes one. So furthermore, so then, the ambiguity has been reduced by quite a bit already. Furthermore, if I assume signal is positive, the quantity we were after, the discrete time signal is also positive, then that forces theta to be zero, it can't even be pi. Okay. So if x is positive, then there is no positive and real, then for sure we can say that theta is equal to zero and we got rid of problem one, if you will. How about problem two, this shift business? Well, that's, that's kind of hard to get rid of, but if we just say we know the region of support of, of our signal x, we know that it's, it's non zero between zero and n in n one and zero and n in the other dimension, then we can get rid of the shift problem. So we're, we're just going to keep adding assumptions until these ambiguities all go away. So now furthermore, assume, so this was to fix the problem one, can you roll up, please, to half of the other pages shown? Excuse me, can you roll up? So half of the other pages is shown. Thank you. So we made assumption one to get rid of observation one or to fix observation one. Assumption two is that we want to assume that we know the extent of x of n one and n two is known. Okay? That means we're not going to worry whether we know that the non zero values are, and this we have this region of support, it's non zero for n one and n two being in this region and not, and therefore you can't shift it here. That's, that's not a probably bad assumption to make either. And finally, for the theorem to hold true, we also have to assume that x of n one and n two is irreducible, okay? Because it's a condition of the theorem. Monty Hayes assumed it, for this equivalence thing to be true, x has to be irreducible, which means that what that means is that the z-transform of the signal x is irreducible. And if we assume all these things, if the real is positive, we know it's extent, and the z-transform is reducible, then we can conclude using Hayes's theorem that we can nail the signal to a factor of two. In other words, it's either we get x of n one and n two, or we get its reflection. The reflection one is the one thing you can't, you can't get away from x of n minus n one comma n minus n two. So both of these things have the same four-year transfer magnitude. So overall, assume the signal is real, x is real, suppose we know, add positive, and suppose we know the region of support, we know the extent of it. Then the four-year transfer magnitude can be used to recover either x or its reflection and reflection is here, uniquely. I use the word uniquely in quotation because it's either this or that. So before I wrap up the lecture, I like to show two things. One of them is the, some examples of four-year transfer and reconstruction. So you can see, I mean, reconstruction from four-year transfer magnitude. So after all these mathematics, you can have a feeling that you actually know what it is. So here's a 12 by 12 pixel signal that can you zoom in, please, as much as you can. So on the left, you have a 12 by 12 signal. Sorry. So you have a 24 by 24 signal. This is the IEEE lady. You can tell from her hairstyle that, actually, there's so few pixels you can't really tell who she is, but if you look at the higher resolution picture, you can tell that this is a hairstyle from the 50s or something, or maybe even 40s, or maybe even 30s, I don't know. And this is the original, and this is the reconstruction using the technique developed by Israelovitz and MIM. And this is a closed form solution technique. It's not iterative. Where he starts tracking the zeros of the z-transform and the z-domain. And the problem with this is that at least at the time it was invented, which was mid-80s, you couldn't apply to any signals that were higher than 24 by 24, or else the problem was the ill conditionness of the problem. And just so that you can get a taste of what a reconstruction from-- you can also apply iterative techniques to do that. And let me see if I have a flow diagram. I don't have a flow diagram, but you can imagine an iterative technique of the following way. And this is really the last thing for today's lecture. So here is a proposed iterative algorithm to actually practically get the phase or recover the phase from 4-year transform magnitude, right? And for this algorithm, we're assuming that we know the signal at 4n times 4n samples of x of omega 1 omega 2 squared. Just you can be 8n. It could be 2n, whatever, but let's just say we know that 4n. So what do you do? You start with some sort of initial guess for the signal. And the signal itself has a region of support of n by n, where n1 ranges 0 to n minus 1, and 2 ranges from 0 to n minus 1. We're assuming the x is positive and real. All those assumptions we're going to make, we make. And we're assuming that it's irreducible. And the fact that we're assuming x is-- has a z-transform that's irreducible is not a stretch of imagination because most two-dimensional signals have an irreducible bond associated-- irreducible bond along any way. If you end up having a reducible bond along, you're extremely unlucky. So the fact-- so the reason this theorem is important is because the condition it requires, the assumption it makes, is easy to make in practice. Most 2D signals have irreducible bonds. Okay. So you start with an initial guess. Your initial guess is n by n. You compute its DTFT, or you compute its DTFT, or its DFT at 4n by 4n samples. And when you go to the computer, you can't compute DTFT because it's a continuous variable, but you can compute this 4n by 4n DFT. And how does one compute the 4n by 4n DFT of n by n signal? Good, good. Tied it with zero. So then you take the DFT of it. And now you check out its magnitude. You're given 4n by 4n samples of the magnitude function. You start with some random initial guess. So you ask yourself, are the resulting magnitude the same as what we were given? Is it close? And if it is yes, it's sufficiently close, we're done. Stop. If it is not, what do we do? Well, we keep the phase that this guy gave us. Remember, when we take the 4n by 4n DFT, it gives us a complex number that has magnitude n phase. We keep the phase that it gave us, and we replace the magnitude by the given guy. So keep the phase, add those 4n by 4n samples, and then replace the magnitude with what was given. And now what do we do? We take an inverse 4n by 4n DFT. Inverse DFT, 4n by 4n. So this is all 4n by 4n. This is 4n by 4n. And the output of this is 4n by 4n. And now what do we do from here? The original sequence we know has a finite extent, and it's n by n. So if I take a inverse 4n for your transfer and I get 4n by 4n, the remaining 3n by 3n samples have got to be 0. So if this is 0, 4n, 4n, 4n, we know this is the only non-zero part. This is 0, 0, 0. So you set the extra values in here to 0. So set extra coefficients to 0. Because we are after a signal that's 0 here and it only has non-zero values between 0 and n. And now you get a signal that's n by n again. And you go back here. You take a 4n by 4n DFT of it and you keep iterating until you exit out of it, until the Fourier transfer magnitude of the resulting signal that you get is close enough to what you were given, in which case you stopped. Right? And this algorithm actually, I have personally run it on signals, and I can tell you what you get if you apply this iterative algorithm. If you start with a given image, you get the, it's signal that's a combination of a signal and a rotation version of it. You see both the features of the original and the rotated version in the convert, so this thing doesn't really converge very well. It's stagnates, it does all kinds of bad things, and where does it stagnate? It's this ambiguity between the signal and its flipped version that kind of kills you. And one way to prevent that stagnation and that ambiguity is to nail down the signal by adding additional information or additional assumptions. Suppose I know, I don't know the phase at one point. Suppose I know, I cut a signal in the space domain with a threshold, I know which sample values it's above, which one is above. Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus, save 10% on Amazon brands, like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty, and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. Looking for excitement? Chumba Casino is here. Play any time, play anywhere. Play on the train, play at the store, play at home, play when you're bored. Play today for your chance to win and get daily bonuses when you log in. So what are you waiting for? Don't delay. Chumba Casino is free to play. Experience social gameplay like never before. Go to Chumba Casino right now to play hundreds of games, including online slots. Bingo, Flingo, and more. Live the Chumba Life at ChumbaCasino.com.