We present in this segment a general framework for solving estimation problems. Like the recovery problems we're addressing during this and next week. The framework is rather intuitive and quite powerful. And it has been applied towards the solution of various signal estimation problems. Of course, we apply it here specifically to the image restoration problem. According to it, we are interested in estimating a signal that belongs to a number of sets of signals. Each set represents the collection of signals that possess a certain property. For example, can define the set of all smooth images or the set of all images that only accept non-negative intensity values. Which is a very reasonable request given the nature of light. If the sets are convex, then the problem we are asked to solve is simple. One way to obtain a solution in later section of the sets, assuming it is not empty, is to alternate or [UNKNOWN] projections onto these sets. It's a rather intuitive and smart framework, as we will see. I would like to briefly discuss another approach towards solving recovery problems or estimating a signal. Under the name of Set Theoretic Approach. And you'll see that, if we apply to the specific problem at hand, the image restoration problem. We can come up with another version of the constrained least squares filter. This approach is rather intuitive. According to it, we are looking for a signal, an image, but has a set of properties. So, each property defines a set, such as the one shown here. So, all the signals, all the images that belong to this set, have a specific property. The set of signals have the second property we're interested in define another set, such as this one. And there could be a third, a fourth property and so on. So for the problem at hand, the image restoration problem, the example of the first set is a set of signals that satisfy this inequality here. So this is the set of the images that have high frequencies, that have energy at the high frequencies, less than absolute squared. Says again, a high-pass filter and therefore this is the energy of high frequencies. And this is the smoothness constrained, as we explained earlier. So all these signals that belong to this set are smooth. By the way, this set is shown as an ellipse here in the n dimensional space is an ellipsoid, the generalization of an ellipse. And is therefore a convex set, an important property of such set. The second set you can define based on our restoration problem is, is shown here. So, it's the set of images that have this difference y minus Hf being less than E squared and this is the fidelity to the data constraint. So, we are looking for an image that has both of these properties, it's smooth and satisfies the fidelity to the data. Therefore, we are looking for an image that belongs to the intersection of these two convex sets. And this intersection is going to be convex as well since the sets are convex. So this is the general setup of a set theoretic approach. And the question now is, how can one obtain a solution in the intersection of these two sets. By the way, these two sets, may have a non-empty intersection, or may not. So typically, after we find the solution, we do a posterior test. And we test if, indeed, the solution satisfies both constraints. Belongs to both sets, as we would be interested in. So, one approach to find the solution is to bound the intersection by another ellipsoid, as shown here. And choose the center of this ellipsoid, of this bounding ellipsoid as the solution. We'll see that this approach can result in a constrained least squares filter. So I have again two sets, a set C 1 and C 2, each of them represents a set of images with desirable properties. They intersect, C 0 is the intersection of the two sets. And I'm interested in finding a solution in the intersection of the two sets. An intuitively, very clear approach is to utilize projections onto convex sets, Approach algorithm. So according to it, I start from an arbitrary initial condition f 0 and I project image of 0 into the first set. So there's the projection P1 on set C 1 of f 0. Then I take this point and project it onto the second set. So this is now the projection two, one to set two, on the set C 2 of the point P1 of f 0. And they call this f 1. And I keep repeating this process. I now take this point, project it to C1. And then, I'll take it and project it back to C 2 and so on. So, the theory tells us that, in general, if I have m, such convex sets. If I repeat this projection onto convex sets or alternating projection algorithm, right. I start with an f 0 arbitrary and project onto the first, the second, the m set. This gives me the new update, f of k minus 1 becomes f of k. And they keep repeating this way. Then, in the limit, after so many iterations. The solution of star here is going to be in the intersection, C 0, of this m, in general, convex sets. So this should be a very, again, intuitively clear algorithm. Of course, these projections, depending on the description of these sets, might be a rather straightforward way to find these projections. Or it might be terribly com, complicated. So the theory of, set theoretic estimation following then any of the two solution approaches I mentioned. Has been applied to a number of problems successfully. And if I apply it now to the restoration problem at hand, I will see what expressions we obtain. [SOUND] So for the image restoration problem, we're looking for an image that belongs to both of these sets. This is the set that represents the [UNKNOWN] to the data. And this is the set that represents the smoothness constraint. So according to the first approach we discussed, we'll find a ellipsoid bounding the intersection of these two sets. And then it can be shown that the center of this ellipsoid, the bounding ellipsoid, is given by this expression. So this is the expression for the constrained least squares filter that we derived earlier. The difference being that now the equalization parameter alpha is given to us. Because we assumed that we know this two bounds E and epsilon. It should be clear that by picking E and epsilon a certain way, these two sets may not intersect. If they both are, for example, chosen to be very small. And therefore, I need to check if indeed this solution I find, it belongs to both of these sets that it should belong. The second approach we discussed is the projection onto convex sets. So if I follow this, I have two sets. The first one is set one. So, this is C 1. This is C 2. And this is the projection of f of an f of an image onto the first set P 1 is given by this expression. And lambda here needs to be chosen appropriately. Soo that P1f belongs to set C 1. Or another words, P1f satisfies this first expression. It is the projection of the second set, the set of smooth images. And similarly lambda 2 needs to be chosen appropriately so that p2f belongs to the second set. So it keep alternating the projection so to this two set I'm going to converge to a point in the intersection. So again this is a specific application of this set's theoretical approach to the image restoration problem. However now that hopefully you do, have a grasp of the basic idea. You can search and see that this approach, estimation approach, has been applied to the solution of additional problems of interest.
