The Bold Blueprint Podcast
The Bold Blueprint Avideh Zakhor Start Where You Are
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. Cycling fans across Colorado are gearing up for Veloswap, the state's biggest bike expo, benefiting Bicycle Colorado. Bring your family to the National Western Complex in Denver one day only on November 2nd for an epic day of bike-based fun. Find deals on bikes, clothing, gear and more from over 150 local and national vendors. Plus bike demos, kids bike rodeos, speakers and prize giveaways. Find more at veloswap.com. Are there any questions or comments about last times lecture or homework or logistics? I don't know what I can't remember off the top of my head what the second problem is. Let me talk to you offline at the end of the class or whoever wants to. Actually here Cindy, did you visit Cindy in her office hours? At the end of the class either come to me or her and we'll just go over. Let me turn this off. Okay so I have the book here we can go over at the end of the class. Any other issues or questions? How many people have finished homework? How many have started it? Okay so let me just give a brief overview of last times lecture and then get going on today's lecture. What we talked about last time, actually let me ask you a different question before getting started. Did everybody successfully get the pages of the book that they wanted? Okay and is the PDF file readable, intelligible? Okay very good. Okay so let me just quickly go over what we did last time. We are talking about the problem of reconstructing signals from partial Fourier information. A few lectures ago we talked about starting with a signal where we have its projections and the idea is to be able to reconstruct a two-dimensional signal from its various projections and we did that through going through the Fourier domain using the projection slice theorem. Then last time we talked about having a discrete time signal where we know its region of support, we know the indices for widgets, it's non-text on non-zero values and we're interested in and we have its its Fourier transform and we can sample it as as finely as we want. So if the signal has only n squared non-zero values as an n by n signal, we have the freedom of sampling the magnitude of the Fourier domain as many samples as we want and 4n square, 8n square, etc. And we showed that while in one-dimensional signals it's not possible to reconstruct the signal from its Fourier transform magnitude in particular for an n point signal, there's two to the n possible signals that could have the same Fourier transform magnitudes simply because of the positions of the zeros of the z transform of the signal can be either inside or outside. For two-dimensional signals that's not the case and the main result was due to money haze which showed that if the associated polynomial of a signal is irreducible, that means the polynomial corresponding to a z transform can't be factored, then it's possible, if we know the signal is real and we know it's positive, then the MBU defector is just two. It's either the signal itself or the flip version of it, flip-reflect the version of it. And then I showed an algorithm or I wrote down an algorithm that iteratively computed, given a Fourier transform magnitude, it would compute the the signal itself. And I ended last time's lecture by saying that even though that algorithm exists, it can really only be run on very small images, maybe 20 by 20. In fact, David's relevance came up with a non iterative algorithm, not the one we talked about, but a closed-form kind of solutions where he was tracking zeros of polynomials in higher-dimensional spaces and even that algorithm could only be applied to very small signals. And I think this is a very good opportunity for me to talk a little bit more formally about a little bit of a detour in numerical analysis and talk about well conditionness versus yield conditionness of problems versus algorithms. And the reason for doing that is because the reconstruction from Fourier transform magnitude is a classic problem that it itself is very yield condition or has been shown to be yield condition. And besides, there's a lot of other examples of both problems and algorithms that could be yield condition. So let me start with that. And then after that, I'm going to move on to the problem of reconstructing images or multi-dimensional signals from their Fourier transform phase. So we haven't got the magnitude, but we have the phase. And what we'll show is that that's a very well-conditioned problem and from just one bit of phase information, in other words, you can even quantize phase to one bit and still reconstruct the signal from its Fourier transform phase. And then I move on to the dual of all these problems, which is the problem of reconstructing multi-dimensional signals from their zero crossings in the space domain. And that's the dual to the problem of reconstructing from one bit of phase in the Fourier domain. And then I move on from there to talk about the problem of reconstructing multi-dimensional signals from multiple level crossings. And we'll show again that reconstructing from zero crossings is extremely yield condition. However, to make a better condition, you can add multiple level crossings. And then that brings us the notion of implicit sampling versus explicit sampling, which is something I'll talk about briefly. Okay, so let me start by doing a little detour into numerical analysis. So what I'm going to talk about is two things. Problems being either well-conditioned or ill-conditioned. And then versus algorithms being well-conditioned or ill-conditioned. Okay, so what do I mean by a problem being, and in fact, there is a thing for both of these things called condition number. That's just the measure of how well-conditioned or how ill-conditioned it is. So you don't have to think of this as a qualitative thing like, whoa, what does it mean? It's well and ill. It's everything in the universe divided into good and bad. No, it's not. So there's actually a scale or a quantity that you can metric, that you can use to measure the well-conditionedness or the ill-conditionedness of a problem. And that's called the condition number. Okay, so if you, so what do I mean by all of this? So condition number is a measure of how well-conditioned. 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. Everybody needs some variety in life. That's what I love about Chumba Casino. They know how to keep things fresh and exciting. All their games are free to play. Like Spin Slots, Bingo and Solitaire, you can claim free daily login bonuses too. And they release new games every week. So spice things up with Chumba Casino.com now for your chance to redeem some serious prizes. Sponsored by Chumba Casino. No purchase necessary. VGW Group. Void where prohibited by law. 18 plus terms and conditions apply. Conditioned. Either an algorithm or a problem is. Either an algorithm or a problem is. And remember the algorithms are applied to problems here. So in other words, I can't talk about an algorithm in vacuum. And I got them for doing what? For solving a specific problem. So let me just draw some boxes here if you can roll up for half of the other page. Great. So if you have a problem, you can think of it as a set of input data going in and a set of output coming out. Okay. I mean the most recent problem we've been working on is what? Well, we have samples of the Fourier transform magnitude. FTM, samples of FTM goes in. And this is called the problem of reconstructing from Fourier transform magnitude. And the output is a signal, the unknown signal. And typically this is called an inverse problem. You're trying to undo, suppose the signal on a nutrient was in time domain, you got it and you only got samples of the Fourier transform, you're undoing and you get the signal back. Or let me talk about a different problem. One thing that, for example, Cindy works on a lot. In IC manufacturing, in the lithography step of IC manufacturing, you have an optical projection system and you put a mask and you put the wafer here and you shine light through the mask and that mask causes a wafer. Yeah, right? So the problem is, given a mask, what kind of intensity pattern do I get on the wafer? Okay. And the photographers and optical engineers for years have been trying to model this optical system. So initially they modeled it as coherent because then the relationship between these two things is a simple LTI, linear time invariant. And they said, well, that's not so good. It's incoherent and then they then the model is a slightly different way. Then Hopkins came along and they said, well, you know, it's partially coherent and there's a complicated for to pull integral that relates the mask pattern to the intensity pattern on the wafer. But that's a problem. And the inverse of that problem is, is you have the intensity pattern on the wafer and you want to compute the desired mask that causes that. So you have a desired intensity pattern and you want to compute the mask that results in that good pattern and that's called an inverse problem. But for now, don't get so caught up between forward and inverse. That's that's a minor point. In this class, as it turns out, in a good part of the class is is devoted to inverse problems. You've got an image that somehow got degraded. You're looking at the degraded signal and you want to solve the inverse problem of undoing that degradation. So that's an inverse problem. But in all of these cases, there's input going in and there's output coming out. And notice, I didn't tell you how you compute the output from the input. I'm just telling you what the problem is. I'm not telling the algorithm. I'm not telling giving you a technique or a procedure or a method to solve it. I'm just telling you what goes in, what information do we have and you know another problem that we all know. The weather problem, for example, or the linear system of equation problem. So if I have solving a linear, can you please put the system of equation A X equals B. So in this case, the input is matrix A and vector B and the output is X, the unknowns. And another problem is the weather problem. So the initial conditions goes in over a region. You know what the pressure is, what the temperature is currently, temperature distribution, pressure distribution. You have satellite imagery from all over from the neighboring regions, satellite imagery and outcomes prediction, like tomorrow's temperature. And tomorrow's rain levels and pressure levels. So these are all examples of problems. And let's talk about another problem. Finding roots of a polynomial. So I have a polynomial, A X cube plus B X squared plus C X plus D. The input is A, B, C, D, the coefficients and the output is the roots. So these are all examples of problems. Now an algorithm is a method or a way to solve a particular problem. So in contrast an algorithm is a method to solve a particular problem. And many times there's more than one method to solve a problem. Can anybody, in all the problems that we just talked about there, can anybody come up with a really crisp example? Let's stare at all the problems that I wrote down here. I mean you've all taken linear algebra, right? At some point in your life, we'll know something about linear algebra, maybe 2, 2, 21 and Berkeley or whatever. When we want to solve A X equals B, there's many methods to, there's many algorithms to solve this problem of linear system of equation. What are the possible algorithms? So here's a list of possible algorithms. Yeah. Excellent. Gaussian elimination. What else? Yeah. There's another variation of Gaussian elimination. It's called what? Actually, what's the problem with, yeah. This is a very good thing you brought up Gaussian elimination. Excellent. And, huh? Primers, you may take the inverse of the matrix. Okay. Compute the inverse. But I still want to come back to this Gaussian elimination. There's a variation of it that's better than the original Gaussian elimination. What's that? You all know, if you like Gaussian elimination, you're kind of in trouble, right? Or maybe you didn't know. Actually, you didn't know because I'm now giving you that lecture. It's, Gaussian elimination results in a lot of errors. And so people came up with a way to fix it. And it's called with pivoting. So Gaussian elimination with pivoting. Okay. What else do we add? And again, the reason was Gaussian elimination as an algorithm was an ill-condition algorithm. Even though the problem itself could be very well conditioned. But we still haven't talked about conditioning. So let's just keep it to what we mean by algorithms and problems. What else? SVD, you can use S, single-value decomposition to solve linear sequence equations. What else? QR. You can use QR decomposition. How many of you have heard of SVD? How many have heard of QR? Okay. QR. But, but QR is actually an extremely stable way of solving this stuff. Pardon? Actually, it doesn't, I don't think it stands for anything. It's, or if it does, I don't remember at this point. When I learned it, it was just always referred to in, in Golub and Van Lone, which is the kind of a Bible in America. 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.com. Sponsored by Chumba Casino, no purchase necessary. VGW Group. Avoid where prohibited by law. 18 plus terms and conditions apply. Announce it. It was always called QR decomposition. Essentially what you're doing, you apply a series of transformation to your A matrix so that it becomes triangular and then you start kind of solving it. So of all these methods, again, when I was a student, there was a linear algebra packet, it was called Zimpak. How many of you have heard or ever used? Okay, good. Still in existence, right? So when you go to Limpak to try to solve your AX equals V, and then how do you decide which algorithm to choose? And that comes out a lot in my research. Like my grad students come to me and say, "Look, I got to solve this in this equation. Which one should I use?" You want to solve a well-conditioned algorithm which I explained in just a second. But also, it has to do with other limitations. For example, there's a whole class of iterative algorithms. And why is that? If the size of your A is so big that you have an analytical formula as to what the formula for each row or for each column is, but the size is so big, you can't possibly store it or it's stupid to store it. Like let's say it's a million by million matrix. Then at any point in time, you can regenerate the i-th row or the j-th column of it, but storing it explicitly in the computer is just suicidal. Then you resort to iterative algorithms. And actually, now it's escaping my mind. It has a Russian name for that. Not here of spaces. Can I forget this? Anyway, there's a whole like third of a numerical analysis class that's devoted. Every time you talk about linear numerical techniques for slightly x equals be a third of a class is devoted to iterative algorithm. So it all depends upon what your conditions are, whether your matrices are too big to store or they're small, etc. A problem has an input and an output. An algorithm also takes that input and generates an output, but it's a method of computation. It's a method that tells you how to go from the input to the output. Okay, so now I want to talk about a problem being well-conditioned. So well-conditioned or condition of a problem. Let's just drop the well, condition of a problem. Basically, condition number of a problem or how well-conditioned it is is kind of the ratio between the perturbation of in the output over the perturbation in the input. And I'll explain that in just a second. And what do I mean by that? So here's our problem box. Here's input going in and here's output going in. Let's say the input in this, in the a x equals b, a case is a and b, and output is x. Okay, so I call the condition number of this problem is the relative change in the output over the relative change in the input. Okay, so if I perturb the input a, for example, by another matrix epsilon, how much does the output get changed? And in real life you use norms of matrices and norms of the vectors and stuff to show that ratio. So it's the relative change, so it's a relative change in the output over the relative change in the input. And if that number is very large, then the condition number of the problem is large, then the problem is ill-conditioned. So this is the condition number, and the thing you want to remember is that if the condition number is large, then the problem is ill-conditioned. And the other hand, if condition number is small, that means it's of the order of somewhere between one, ideally close to one, then the problem is well-conditioned. And notice this relates to the problem. It has nothing to do with how we solve the problem, what algorithm we apply to it, it's intrinsic to the problem itself. It's independent of the algorithm you chose to solve it. So in the problem of, first of all, the first question you might ask is, I don't really understand why do you want to perturb the input and why do you want to see how much that perturbation in the input causes change in the output? Can anybody make a guess as to why that's a good idea? Why does it make sense to think of condition number as being the relative change in the output given the relative change in the input? Well, there's two reasons. One reason is that, I've alluded to it before, in the lectures before, one reason is that by the virtue of just inputting your A's and B's or your input to a computer program, you've already introduced perturbation. Well, I mean, it's both the numerical representation of the numbers in the computer and also the measurement error in A. Let's talk about the weather problem. I can measure temperature and I can measure pressure and I can profile temperature and pressure, let's say, all over the Bay Area, as my initial condition so that I can predict the weather tomorrow, but there's measurement errors in that all the time. My thermometer can only go to so much precision and so much precision. Anything real life has finite precision. And secondly, when I start crunching numbers, and these, suppose that God gave us this input to infinite precision and we start crunching the numbers in the computer, there's round-off errors because of the finite precision of the computer. So there's bound to be changes in the output, both due to the calculations and the additions and multiplies they all introduce round-off errors and also due to the quantization of the input as you plug this into the problem. So if a slight change in the input, and the changes in the input again doesn't have to be all from the input, it could be as if it could be the effective change in the input as a result of the number crunching that goes on in the middle. If the little change in the input causes a big change in the output, by being large, I mean 10 to the 6, 10 to the 10, 10 to the 12, I change my input from number 5 to number 6 and my output changes from, I don't know, 1 to 1 million. That's a big change, right? Then we call that a problem in condition, okay? And for the problem of AX equals B, which is our favorite problem to address this problem, is there a quant, so this is independent, we were talking about the problem, it's independent of the algorithm, is there something about this problem, about the input, that can tell us how well conditioned the problem is? It's the condition number of the problem, for AX equals B, what is the condition number of the problem? Does anybody happen to know? It's the condition number of this matrix A, it's entirely dependent on A, and what you might say, well what is the condition number of a matrix? It's the ratio between its largest singular value over its smaller singular value, okay? The reason I know that it took courses and all that, but it's a good example case, so for AX equals B, A has a thing called condition number, which is mathematically, it's the ratio between the largest singular value and the smallest singular value, and it's a measure of how close to singularity A is, I mean, as you remember like when you did algebra, this matrix A, if you just talk about the 2 by 2 matrix, it's not the case that either is determinant 0 or non-zero, even though that's the way they taught you that, the determinant can be close to 0 or can be far away from 0, so in some sense, this thing, the ratio between, so when the matrix is singular, it's determinant, slack is 0, this number is infinity, that means the condition number of the matrix is infinity, that means your problem is, 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. Every day when you log into Chumbah Casino.com, the ultimate online social casino, you get a free daily bonus, imagine if you got daily bonuses in other parts of your life, I chose french fries over loaded french fries, I asked Stewart from accounting about his weekend, even though I don't care, I updated my operating system without having to call tech support, collect your free daily bonus at Chumbah Casino.com now and live the Chumbah Life. The smallest this can be is one, right, the largest and the smallest single, that means your problem is very well conditioned, your matrix is far from being singular, this notion of condition number is kind of a metric that has a gray scale in it, it's not that how that's matrix is singular and non-singular, that's a binary view of the world and that's useless, but this thing gives us some a gray scale view of the world as to how well conditioned the matrix is. So that's what I mean by the problem being well conditioned, it has nothing to do with which one of these lists of algorithms I applied to it. So condition number, so what I wanted to walk away from is that the condition number of problem depends on the intrinsic, intrinsic, I would say, genetic signature of the problem aspects of the problem itself, okay, and so your problem fundamentally can be ill conditioned or well conditioned, if the condition in ax equals v, if the condition number of the matrix is large, it's ill conditioned, if the condition number of matrix is small, it's well conditioned. Now you start with a problem, so it's either well conditioned and ill conditioned, and I know this is, you know, superficial, but let's just simplify the world, it's either well conditioned or ill conditioned, if it is ill conditioned, you can kind of conclude no matter what algorithm you apply, you're in kind of a trouble, there's going to be inaccuracies in your answers, there's going to be instabilities in your answers, but you could start with a very well conditioned problem, matrix with a very small conditioned number, and then apply an ill conditioned algorithm. And so what do I mean by an algorithm being ill conditioned or well conditioned, the same thing, an algorithm is ill conditioned, if a small change in its input results in a large change in the relative value of the output, so let's write that down, so condition number of an algorithm is the same thing, here's an algorithm, input, output, is, so the condition number is the ratio between relative change in the output over relative change in the input, okay, and you might say well that comes close to, awfully close to problem condition number, and that's correct, it is, if the problem itself is ill conditioned, you almost have no chance of designing an algorithm that will be, that will not be ill conditioned, in other words the algorithm can only do as well as the problem, however, if the problem is well conditioned, a bad algorithm could kill it, so even though the problem itself, let's say AX equals B, was well conditioned, applying a bad algorithm to it could cause a lot of error at the output, there are a noise at the output, given a particular input, so if, so if the problem is in condition, you're kind of out of luck, it's hard to find, no matter what algorithm you find, it can, the best it can do is cope with, you know, it's just produce perturbations in the output, which is what the problem inherently would introduce, and the other hand, if the problem is well conditioned, you can apply well conditioned algorithm or ill conditioned algorithms, in this case you get good answers, in this case you get messed up answers, you get a lot of errors, okay, so the morale of this whole detour into numerical analysis is that, and coming back before I talk about morale, let me just, we can give a concrete example, let's come back here to the list of algorithms we had, so it turns out Gaussian elimination by itself could be extremely an ill conditioned way of solving, even a well conditioned may AX equals B problem, so this is bad, so this is a bad or ill conditioned algorithm, even though, so even if you have a well conditioned problem, AX equals B with a small conditioned number from matrix A, applying this could mess things up, computing the inverse, anybody, good or bad, terrible, it's not even bad, okay, it's just about the worst way of solving AX equals B, Gaussian elimination with pivoting, good, that saves it, that's a method, the reason they came out with pivoting is essentially to fix Gaussian elimination, it was an algorithm that to begin with was bad, but if you do pivoting it fixes it, SVD, excellent, QR, excellent, iterative algorithms, they could be good or bad, but they're always good for large problems, where you can't store the matrix itself, okay, but our iterative algorithms always have convergence issues you have to worry about, okay, so the thing I want you to walk away from is really this picture, is that even though the problem could be well conditioned, if you apply an ill conditioned algorithm to it, you could get answers that are way, way off, and you could run into instabilities, and in real life, how do you measure, suppose I was dealing with how could I circumvent some of these issues, well if I apply in a lot of precision, like if I have 64-bit computers, or if I use 128-bit mantises and exponents and stuff, I could alleviate some of these problems, but how do I know what the true answer is, let me try to rephrase what I'm trying to say, so how could we measure some of these things in real life, how could you experiment or play with some of these things in real life, well I could give you an A, C, C, C, B problem, and A could have very large condition number, it's not exactly singular, but it's close to singular, okay, and you could, for example, apply 64-bit precision to solve it, and then you can apply 10-bit precision to solve it, and then you can find that the answer that the 10-bit precision gives you is way off, is much, much different from the answer that the 64-bit precision gives you, and that's what I mean by messed up, I guess I was trying to justify the meaning of the word messed up, is that if somehow magically there was a way to compute the exact answer, it would be way off from any answer you would get by, for example, using lower precision, or by changing slightly the values of A, okay, in many real life algorithms and problems, in many real life situations and applications, these matrices A and vectors B come from actual measurements out in the field, like A could be an image, and you take an image, how do you take an image, is CCD sensors in a camera, there's noise, there's pixels, all kinds of things, so that's really why we care about the condition number of the problem to begin with and the condition number of the algorithm, and it turns out that in image, and we'll talk about this when we talk about restoration enhancement and other things, is there's a lot of algorithms people have proposed initially that were not very well-conditioned, in this technique called regularization that you can apply in order to turn the problem into something well-conditioned, so you can solve it using standard algorithms. Okay, are there any questions or comments on this? Okay, so to the immediate problem that we have at hand, the problem of recon reconstruction from Fourier transform magnitude, so even though my clonin and haze showed that most polynomials are reducible and that you could uniquely recover the signal, in practice, this is a very ill-conditioned problem, and that's another manifestation of ill-conditionedness, is that you can apply it to a small data set, but not to a large data set. 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. You can apply it to 20 by 20 images or 30 by 30, but not 1,000 by 1,000. So even though theoretically Hazel McClellan showed the uniqueness in practice, it's ill-conditioned. And one of the reasons it's ill-conditioned, and people have actually shown it. By the way, a bunch of people in numerical analysis spend their time proving that the problem is ill-conditioned, so that you don't waste your time kind of looking for an algorithm. It's a bit of a chicken and egg problem in that you might say, well, how do I know really? I mean, a x equals b is a special case where we were lucky enough to find something about a that tells about the condition number of the problem itself. Many other times you have a problem, how do you know that if the problem itself is ill-conditioned? Well, you try algorithm A, it doesn't work. You try algorithm B, it doesn't work. You try C, it doesn't work. And after a while, people get tired of it and say, geez, this has got to be an ill-conditioned problem. Nobody can find an algorithm that works on it. And many times it's true that it's a case. And some people then roll up their sleeves and start mathematically proving that this problem is ill-conditioned without using a specific algorithm. Because you see, if you apply a specific algorithm, somebody might come along and say, oh, the way you're solving it is bad. So knowing deep down, whether it was the problem itself or the algorithm you apply to it is bad. It's a very general, it's a very difficult problem in science and engineering. And so people, you really have to roll up your sleeves and do some deep mathematical analysis to show that the problem itself is ill-conditioned. So in this case, so they showed it's unique and everybody was happy for like two years. They said, great, great. This is something different in 2D than in 1D and you can use it in optical astronomy, electron microscopy, which is by the way what they're using to look at the particles that store dust gut. But then when people tried to come up with algorithms, everything failed. And then finally people said, well, why do you think it's failing? And then they came across another result in approximation theory, which shows that even though most two-dimensional polynomials are irreducible, that means can't be factored, almost all of them can almost be factored. In other words, there's a factorization algorithm that you can apply to it that's close enough that can be factored. So in reality, there's another result that showed that 2D polynomials can almost, I mean not precisely, closely be approximated by factors. And as you recall, the result by Hays and McClelland required the irreducibility. And in fact, if you look at the polynomial approximation theory literature, there's algorithms that you can find. You start with a two-dimensional polynomial and you apply the algorithm, it factors it for you as closely as it can in an approximate way. So almost all the 2D polynomials, even though they're not exactly factorable, they're almost factorable, and therefore that is the fundamental reason for the ill-conditionness of this problem. And if you're interested in the closed-form solution for this problem, there's closed-form and iterative solutions. The iterative solution we talked about, the closed-form solution was derived by Israel a bit and Lim was the author of your book. And did I show you the pictures from last time of some examples of reconstruction from Fourier transform magnitude? Anybody remember? I'll just flip it again because that kind of brings to conclusion this topic. Here we go. You almost can't see a difference. I think you can zoom in, please. The only noticeable thing I would say about this is that the reason this image looks so grainy is because this is the biggest image, David's relevance, who was actually a grad student at the same time as I was at MIT. That's the biggest image you could ever process, which is, I think, 24 by 24 pixels. If he tried. I mean, it's granted. Now you have bigger computers, so you can probably do, I don't know, 50 by 50 or something like that. But this by algorithm has problems scaling into larger images. Okay? And the reference for Israel that says paper is, I believe Lim has a reference section, does he? Not at the end of the chapter, but does he have it at the end of the book? He does? Sorry, how come I can't find it for chapter? Oh, here we go. So if you look at, there is relevance in Lim, a new direct algorithm, direct me non-intuitive for image reconstruction from Fourier transform magnitude, IEEE transaction on signal processing, April 87. Wow, I thought it was much earlier than that, but I guess not. And there's another classic paper that I would like to refer you guys to. It's a, it's a, a mercero and Oppenheim paper on reconstruction. I guess he doesn't refer to that. Yeah. Anyway, there's a, there's a 1972 for, for the problem of reconstruction from projections, there's a classic paper by Oppenheim and Mercero. Let me write this down. So Oppenheim and Mercero, M-E-R-S-E-R-E-A-U, who's also at Georgia Tech, it's a 1972, it's called proceedings of IEEE and it has to do with projection slice theorem and reconstruction from projections, etc. Okay. Any questions? I'm going in these guys. All right, so now I'm going to change gears and talk about reconstruction from Fourier transform phase. And I'll be very upfront, this problem from a practical point of view is a lot less important. There's not, I can't list a bunch of applications that would use this, unlike the problem of Fourier transform magnitude, because in many applications, it's very difficult to measure phase, especially at very high frequencies, but it's not easy to measure phase and not know the magnitude, that doesn't occur too often. But nevertheless, the reason I want to talk about it is because it has a dual in the time domain or in the space domain that we'll talk about as well. So the setup is as follows. I have a signal, two-dimensional signal X of n1 and 2, it's n by n and n1 and n2 are integer, and I have its discrete time Fourier transform, which is X of omega 1 and omega 2, which has some magnitude and some phase, okay. And X of omega 1 and omega 2, as you all know, is given by this expression, summation over n1 and 2, X of n1 and n2, e to the minus j omega 1 and 1, e to the minus j omega 2 and 2, all remember that. And this guy is a phase function. This 4-year transform is a magnitude, as it has a phase, and omega 1 and omega 2 once again are continuous valued variables that go from a minus pi to plus pi, okay. And the idea is the same. I'm going to have samples of this phase, and again, if I have an n by n signal, I've got to have at least n-squared samples at least, but if I just have n-squared, I'm out of luck because of the... 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. Looking for excitement? Jamba Casino is here. Play anytime, 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. Ingo, slingo, and more. Live the Chumba Life at ChumbaCasino.com. B.T.W. room. No purchases are either prohibited by law, see terms and conditions, 18 plus. Because then I can choose any magnitude and that's a bad thing. So I'm going to have to sample, over sample this phase guy. So this is, let's say, field of omega 1 and omega 2, the phase corresponding to this sort of sample. And this is a problem that Patrick Van Hove, a Belgian fellow at MIT, solved at about 1982. He was also a student of J. Lin. Okay, yeah. This is a DTFT, the same as like a fast Fourier transform, like when he used MATLAB. When fast Fourier transform computes DFT. It computes samples of DTFT. Equally spaced samples of DTFT is DFT, right? So if I have an N by N signal, it's DFT is another N by N array of numbers. What I'm assuming here is that we have the discrete time Fourier transform as a function of omega 1 and omega 2, which are continuous variables. So I don't have an array of numbers, I have a function of continuous variables, but I have samples of it at 2N square, 4N square, 8N square, however, number of samples of it I want it. Not necessarily equally spaced, it could be random or whatever. And so let me just write this down. So we need to have samples of phi at more than N squared to even attempt to get anywhere. I was kind of curious why they scale the frequencies when they do that by the sampling interval. There's no sampling interval in the frequencies up there. It's periodic in 2 pi, not what it would actually be. Because I assume that the input has already been sampled. I have X of N1 and N2 and N1 and N2 are integers, they're not time samples. So when you go to the Fourier domain, all the T's and sampling periods, they've all evaporated. Because I'm not dealing with the continuous time input time domain signal or space domain signal, I'm dealing with a discrete time. It holds, if you can carry on the analysis by discretizing a continuous time thing, you will have the T and there will be T's all over the place. But it only complicates the equations. It doesn't affect the juice or the guts of the arguments that we're presenting. So we're assuming the sampling has already occurred in the time domain. So essentially, I need to have samples of phi at more than N squared points here. And then from that is what we're trying to reconstruct our signal. And what Patrick Van Hove showed was quite interesting is that not only, if you have enough samples of the phase, not only can you reconstruct the signal, and not only it's not ill-condition, it's extremely well-conditioned, you can even quantize the phase to one bit. In other words, you don't have to know what the exact value of the phase is. The phase is between zero and two pi itself, right? And you might have thought, oh geez, I have to know the phase very accurately to do the reconstruction. And he showed that if you just even quantize it to one bit, like is it between, I don't know, zero and pi or between pi and two pi. If you do that, then you can still, from that quantized phase values, you can recover the magnitude and therefore then recover the signal itself. And there are a couple of algorithms you can apply to do this problem. One is a direct method, which I'll talk about in a second, just involves solving linear system equations, which by the way comes up in signal processing a lot. And then the second method is the iterative one that we talked about last time, similar to the Fourier transform magnitude. So if you can roll up, please. So two algorithms, one is iterative, the other one is direct. And Van Hove, oh, actually, it wasn't, it wasn't Van Hove himself, it was either Van Hove or then it was Van Hove Curtis Oppenheim and Lim or a group of them. It was shown around 1982 that you can even quantize, even doesn't mean even an odd. You can go as far as quantizing the phase to one bit and yet reconstruct the signal successfully. The phase, I mean the phase of the Fourier transform. I hope that's, that's clear from the context. So what would be, it's kind of the, how what would be the flow diagram of, of a, of an iterative algorithm? It's not that different from, from the, the other one we talked about. So this, this setup, so here's the iterative algorithm. The setup is that we have an n by n signal. We know it's region of support. ROS means region of support. We know the indices of n1 and n2 over which they're non-zero. In other words, it's n by n. And we, we have the samples, let's say at two n, at two n of phase of the Fourier transform. Okay. So it starts up with the same way as before. You come up with an initial guess and that guess could be anything. And we call that y of n1 and n2. And this guess is an n by n signal because you already know your, the signal your after is n by n. And then you compute from there two n by two n DFT of y of n1 and n2. And that results in y of k1 and k2. So that comes back to your point. In real, even though I am assuming I have samples of DFT, when I do computation in the computer, if I have an n by n signal, I can compute this 2n by 2n or 4n by 4n DFT using the FFT algorithm, right? So, so how do I make 2n by 2n DFT of a signal that's n by n? This is my signal. It's non-zero here. This is n, 2n, n, 2n. How do I make, if my signal is only n by n, how do I make 2n by 2n DFT of it? I had to be 0, good, good, good. So then I get a 4, 2n by 2n signal, which is k by y of k1 and k2. And then I ask myself, is phase of x equal to phase of y at those samples that I was given? I'm given here in this iterative algorithm, I'm given samples of, oh, here, I already said that. Sorry, I don't have to repeat it. I'm given samples at these 2n by 2n points, okay? So I ask myself, is phi x is equal to phi y? And if the answer is yes, I stop. If the answer is no, what do I do? I keep the magnitude of y and then I replace the phase with a given phase, okay? And then from here, I take an inverse for your transform sorry, go to a new box and you take inverse for your transform to get, so at this point, I still have a 2n by 2n signal to get another 2n by 2n space domain signal. 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. It is Ryan Seacrest here. Everybody needs some variety in life. That's what I love about Chumba Casino. They know how to keep things fresh and exciting. All their games are free to play, like spin slots, bingo and solitaire. You can claim free daily login bonuses too, and they release new games every week. So spice things up with Chumba Casino.com now for your chance to redeem some serious prizes. Sponsored by Chumba Casino. No purchase necessary. VGW Group. Void we're prohibited by law. 18 plus terms and conditions apply. How do you get phi Y to be 2N by 2N? Compare the two. Because Y itself was 2N by 2N. Because initially Y was N by N, but I took it 2N by 2N. I'm sorry. It must be phi X then, because that's the original that you're comparing to. It's a phase. That's right. This is the phi X is the original, correct? Right. So in that N by N also. No, I'm assuming I know phi at 2N by 2N. And remember I said here, need to have samples of phi at more than N squared. So I'm assuming 4N squared. Do you see why you needed it more than that? Because if you don't, there's a fundamental and heron ambiguity. You can assign any magnitude, right? And then that results in any signal. So you've got to have something to constrain the problem, something to tie it down. Because you can think of, it's the same argument as we did last time. You can think of computing. This thing is nothing but a matrix linear system of equation, right? In X of N1 and N2, right? So if I go back and this thing is some magnitude of some phase. So if I write down an N squared by N2 and matrix, and I only know the phase, I can, at my whim, I can pick whatever magnitude I want for whatever samples. And depending on what I pick, I get a new signal. So it's like, I have infinite degrees of freedom, right? So it's got to be more than N squared. And to nail that down, I've assumed that I know samples of, so X here is the original signal. Maybe I didn't. And so phi of X is the thing that we're given, samples. So now I take the 2N by 2N inverse Fourier transform, inverse DTFT or inverse FFT, whatever. And then, so now I get a 2N by 2N signal. And that 2N by 2N signal might or might not have zeroes in these locations, but we want it to have zeroes. So what we do is set the signal to zero outside of the N by N region. And then come back here and repeat this process. Okay. It's pretty much the dual or the mirror of what we had for the magnitude problem. You're taking advantage of the fact that the region of support is N by N. Any questions on this? Yeah, please. So when you start with the 2N by 2N phase information, what did that come from exactly? Did you have the original signal? You mean the given? Yeah, given. Well, that is my problem for definition. I'm reconstructing from Fourier transform phase. What that really means, I have 2N by 2 and samples of the phase of the Fourier transform. Somehow somebody gave it to me. And the problem is, given that, can I go back and recover X? All right. That's the question. Question. I mean, how far out can you actually recover X? Like if you did this iterative approach for just say out to N, and then you did it out to like almost 2N, where you try to recover almost the whole entire thing, would it take a lot longer or is it a lot harder to get the right result? No, actually, this particular algorithm and this problem is so well conditioned. As I said, you can even cut the phase, you know, I think 2N squared would probably do the job. The reason I insisted on 2N by 2N is because equally spaced samples is because then it's easy to get DFTs of it back and forth, right? Because DFT is equally spaced samples of this guy, right? So if I do 2N coming back to your point, well how do I distribute 2N square points in this plane? I'll have square root of 2N samples in this direction, square root of 2 times N samples in the other direction. It's just from an implementation point of view. It's still possible to do it, by the way. You replace DFTs and then you use linear system of equations to do all the parts that build DFT, right? But in practice, yeah, you can have 2N scores should be enough. And in fact, if you quantize the phase, if you don't even sample the phase and don't know the value of the phase exactly, but you just say quantize it to one bit, it still works, okay? Okay, I'm going to actually skip the direct method. It's explained in the book and I trust you can go ahead and read that yourself, but I'd like to show you some examples of phase reconstruction. And the reason we went through this whole Ragamelon is to show you that, in fact, the phase of an image carries a lot more phase of the Fourier transform of this image, carries a lot more information than the magnitude does. So let me begin by showing here. This is an example of a phase-only reconstruction by a closed form algorithm. Again, it's described in the book on page 34. I'll encourage you to read it. Okay, so here we go. It's phase-only using the direct method 12 by 12 pixels signal. And again, we did IEEE. This is a famous ultra-police signal. And it involves the direct methods involving solving a linear system of equations, okay? Now, this is an example, on the other hand, of again doing phase-only reconstruction. You have the phase of the Fourier transform using the phase of the Fourier transform. This is what you get after, let's see, A is after one iteration, C, sorry, this is after one iteration, this is after 10 iteration, and this is after 50 iterations. So it converges pretty quickly. And you can already see the advantage of the iterative technique. Why is the linear system of equation with only a 12 by 12 pixel image? Because you had to store what's 144 by 144 matrix, double precision matrix, in the computers at that time, which I don't even want to mention their names because that shows how old I am. But okay, I'll say this PDP 11, the Axie 11, 750, you probably never heard of these things, right? There was a computer called, I guess none of you probably have heard of, there's a computer company called Digital. Has anybody heard of that? No, I knew you had them. It was actually off of Cambridge, Massachusetts, was where it was headquartered. So you went to Digital and you bought the Axie 11, 750 or PDP 11 was even the older generation. And what it was, it was a time-shared machine. The machine set in the machine room and everybody had a terminal on their desks. And you just, through the terminal, you logged in. And so you were always competing with your other fellow graduate students for the CPU cycles. And if you became a CPU hog, then everybody in the lab just hated you. And they wouldn't want to go to lunch with you and say, "Oh, she's the one who always has big jobs running." And I used to, I had a terminal in my room, in my dorm, that I would remote log in. And there was so much competition with CPU, I would start my algorithm. I had an iterative algorithm for my thesis, too, that had a lot of convergence problems. And it was a big CPU hog. So I would go to bed, I don't know what it, 11, 12. But I would set the alarm clock at four, wake me up, the thing was done at that time. And then I would restart another run and another run. It wasn't a good idea to have two runs in parallel because the swapping between those two processes would slow down the thing even further. And it turned out the best thing to do is just, at that time in the morning, between 12 and 8 in the morning, nobody was in the lab. So you could have the 100% of CPU of these, you know, PDP 11 or 11, 7, 5, all to yourself. So you wake up at four, you run it again, you wake up again at nine, and by the time you wake up in the morning, it's done. That way, you don't waste your whole day kind of waiting to see what the answers were. And anyway, that's, that's a long, anyway, why did I say that? Because on those PDP 11s and Vaxx 11, 7, 50s, and I can attest to it, you couldn't store matrices that were larger than, I don't know, 100 by 100 or 200 by 200. Because each one was double precision and the amount of memory it had at that time wasn't even enough. Now, as I was cleaning close to graduating, like a month before I graduated, my advisor got this really new fancy workstation, not from digital, but from a new company in California called Sun Microsystems, which by now is going bankrupt, right? Now, everybody uses PCs, but, but that, at that time, you know, Sun Microsystem was a big deal to have. Now you could do, now everybody said, ah, we can now store, you know, 400 by 400 matrices. Great, you know, now we can solve bigger images. But anyway, this is a prime example of why the iterative algorithm is better than the, then the direct algorithm, because if the direct algorithm involves some equations, you've got to explicitly store the matrix in the computer, and that's too bad, that's too, too much memory usage for that time or even for now. The problem isn't even now, you just end up processing bigger images, like 10,000 by 10,000. Now we're not content with, you know, with 500 by 500 even, we want to have bigger ones. In, okay, so, so this is the iterative algorithm, and it works pretty well. So now, another pretty interesting picture, I don't know if you've read the chapter or not, but this is a, I think, pretty amazing example. You might ask yourself, well, which is more important, the Fourier transform magnitude of a signal and Fourier transform phase, and what do I mean by which is more important? Well, suppose we do the following thought experiment, this is an original signal, it's a clock signal again, right? And this is an original signal of some city. Unfortunately, even in the book, this thing doesn't come, even if you come and look at it directly on my book right here, it doesn't look very good, it's got a lot of noise and everything, but it drives the point home. So, to get this image, what I did was I started with, let's see, with the phase of this signal and the magnitude phase of the Fourier transform, this signal and the magnitude of the Fourier transform, this signal, and I get that. And here, I started with phase of, phase of Fourier transform, this signal and magnitude of the Fourier transform, this signal, and I get this, right? I just married the phase and, and looking at what conclusion can you immediately arrive at? Yeah, the phase is definitely the dominant thing. The phase of the Fourier transform is, is extremely important. In fact, you can show that the magnitude of the Fourier transform most signals, you know, kind of look the same, they have a blind ear, we showed, I showed an example, they have a, this is an image, aerial image, and this is the Fourier transform magnitude, they have a low pass DC component here, and, and then pretty much die down to zero everywhere else. So, so there's not a lot of, and, and the reason that is the case is because we're looking at natural imagery and images. We're not looking at, you know, I could sit down and, and make a, a picture, or make a two-dimensional, I wouldn't call it a picture, I could sit down and construct a two-dimensional signal by having a very complicated looking Fourier transform magnitude. Up and down, up here, down here, high frequencies all over the place, and, and then assign some phase to it, and then take inverse Fourier transform. But what I get is not a natural looking image. I look at it and I say, it looks like garbage. It was like, you know, it, it, you, again, in your generation probably hasn't seen it. When you, when your TV doesn't have good reception, you get that black and white fuzz, you get something like that. If I, if I, if you do that experiment, it's not a, so it's a, it's a proper, the reason this experiment worked here, which I swapped the Fourier transform phase and magnitude, the reason this worked is, is because we're dealing with a kind of natural imagery rather than with synthetic zachormade pictures. It's, it's, it's that. And I, I bet there'll be some kind of a future computer arts where people will make images using that, but I'd be curious to know how, how that looks. Okay, um, yeah, question. Just that I curious, I mean, you don't really know any applications where you can measure the phase, other than some type of maybe interference. The, in, in Lim, in Jerry Lim's book, I think there, there's always, there's always few, he cites few applications, but my, and he might have references for it that does it. Let me quickly look at these notes for my, so, so, um, yeah, I, I don't know anything off the top of my head. Probably Jay Lim refers to something, but my understanding of Lim's book is he always over refers to, to the application is where some of them might be kind of not quite real life applications. For example, he might open this, I'm not saying he does here, but he might open the section by saying this problem has applications, electron microscopy, this, that, that, that, and the other, and then sometimes there's no reference, so you can really look it up. Sometimes there is, and you should look it up and see what it is. But, but sometimes there's not, I think in any application in, in optics, if you can measure, can you? I mean, you are an optics guy. Can you easily measure phase? Using lasers, right? Right. Right. Right. Right. In fact, I was visiting a company in Los Angeles like a week or two ago, and they showed me these laser applications where you're right. They, they generate the interference pattern and then from like holograms, exactly. Holograms are phases, right? So here's one application where you can measure phaser and, and do it, but it's not as prevalent in general many times. You see, measuring magnitude in optics anyway corresponds to what? You have a sensor that counts the full times, right? It's a pretty standard kind of a thing, right? Whereas measuring phase, other than the hologram thing, I, I can't think of a straightforward example. In general, measuring light is easy because, you know, it, you just, photons hit the sensor and we count it and boom, that is it. Okay. Okay. So, um, I think I'm going to stop at this point because I was going to talk about reconstruction from level crossings and multiple level crossings, but if I do that, then I have to redo it again next time. So I'm going to end the lecture here and I'll see you all on, on Friday. And, and if you have questions about that, that homework problem, feel free to either ask me or Cindy. 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. Lucky Land Slots asking people, what's the weirdest place you've gotten lucky? Lucky in line at the deli, I guess? Uh-huh in 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 Group would be recruited by law 18 plus terms and conditions apply.