We're going to use a very simple diagram to demonstrate and to present the model. Again we are on the search for a model for a signal X that has N dimensions. What is N? For example if we consider 8x8 blocks. As in jpeg we have that N is equal to 64 why 64? We take an 8x8 block or image patch and we take one row after another. We concatenate them and we get N = 64. This is the signal we are looking to model. Now. The next step and actually one of the main components of Sparse Modelling is the Dictionary. The Dictionary is a matrix which is N by K. N is the dimension of the signal we are looking to model. K is the size of the dictionary. We have K columns. Every column is called an atom. It's kind of an image, kind of a patch. Because every column is 64-dimensional. And we have K such columns. Very often, k. Is larger than n. That's not necessary, but happens very often. For example, when we are going to do image renouncing as we are using as an example. If case larger than n, then we say that the dictionary is over complete. Now, if K is equal to N, then the dictionary's complete. For example, Fourier or discrete cosine transform are complete dictionaries. If K is less than N, we say that a dictionary is under-complete. Now we have the dictionary. The second element of sparse modeling is. This vector alpha. And what we have is a vector, alpha, that has to have dimensions, K, and we multiply the matrix, D, the dictionary, by the vector, alpha, and we produce the signal that we're trying to model. What's particular of this vector alpha, is the number of non zero entries of the vector is very small. We represent those by this red dot. We have, at most, L non zero entries. And when we multiply this matrix, the Dictionary D by alpha. What we are doing is having a linear combination of the atoms. Corresponding to the non-zero entries. So, we are combining, this is the second one. It means it's picking the second atom. This is picking its corresponding atom. And this is picking its corresponding atom. And we basically have a linear combination according to the coefficients here of those L atoms. And because these are only a few non-zero coefficients, this vector is very sparse. And from that, the concept of sparse modeling. So what we have is basically. A signal. Represented as a product of the dictionary, and a vector alpha. With only a few non zero entries. A very sparse vector. Now, this model is, first of all, very, very simple. Once we have the dictionary, d. And alpha will obtain the signal just by a simple product. This dictionary, we're going to discuss a lot about it in this video, in the future videos. But for now, it's a fixed dictionary of dimensions N by K, as we have seen in the previous slide. Now, the model is extremely rich. Let's just do some numbers. If we have a dictionary of size K, meaning K atoms, and we pick L. We have L choose out of K possibilities. So if L is three we can pick any three out of K. Once we pick them, each one of those selections define a subspace, a very low dimensional subspace. Once we pick, we do that selection, the signal, it's just a linear combination of the corresponding atoms and that's a linear subspace. But we have many of them. We have L out of K, a lot of them. So the model is extremely, extremely rich and, hopefully, that will help us to represent. Basically any signal of interest. So, the model is simple, the model is very rich. And also, the model is actually familiar to us. This is not the first time that we see such a model of taking basically a signal and representing it as a linear combination of a dictionary with only a few atoms of that dictionary. Let's think for a minute, or for a few seconds, when have we seen already this model? We. Remember what we have learned in the last few weeks. We have seen this model. In JPEG. When, or how, in JPEG D. Is basically the cosine basis. In JPEG we took and eight*8 block. We did a transform into the cosine domain. So d is the cosine basis. And alpha is basically the coefficient of the cosine transform. And we saw that, for example, when we quantize. A lot of the, these great cosine transform coefficients became zero. So basically alpha was 64-dimensional. But a lot of it was zero. So it was a very, very sparse vector. And it achieved an extremely good representation of the eight by eight patch. With just a few provisions, so JPEG is a great example of the power of sparsity. Let me just give you another extreme example of how we can represent signals in a very sparse fashion. Consider that D includes all the signals of interest. So if you're talking about images, this has huge matrix, K basically goes over all the possible images. If that happens, then every time you want to represent a signal x, an image. You only go and pick the corresponding atom. The corresponding column in d. And that means that our sparsity is one. So this extreme example is only to illustrate that we can do sparse representations of signals. Of course, it's not very practical; because imagine that you cannot put all the patches or all the images in one dictionary. That would be huge, and it won't be very useful. The JPEG is, as we say, probably the most successful image processing algorithm, and it's based on Sparse Representations. So, that's what we want. We want to Sparse Representation of sigmas. And the basic idea once again is that the signal is a linear combination of a few atoms because alpha is sparse. How do we measure Sparsity, is the next question? The way we are going to measure Sparsity is with. This, which is called the LP norm for a given P. Remember, alpha is nothing else than a K dimensional vector. And what we are doing here with this formula is that we take every entry of alpha, and we take the absolute value, and we elevate to the P power, and we add all of them. And that's the LP norm of the vector. Let's illustrate this for different values of P. If p is equal to two, we don't really get what we want, because what we want is to penalize. With an equal amount, every time one of the entries of alpha is non-zero. And when it's zero, don't penalize at all. So, that happens. Zero, no penalization. But then the penalization increases quadratically with actually demanding to lose the entry. We don't want that. We want kind of an equal penalization. As long as it's non-zero, it gets penalized. What happen when P is equal to one. At least the penalization now is proportional. Directly proportional and linearly proportional to the magnitude of the entry, is not quadratic, that's better, but doesn't look like it is good. We are going to see, later on that this is actually a very good penalty function. This L1. L for P = 1 It doesn't look like. But we are going to see that, under certain conditions, this is exactly what we are looking for. But before we get into that, let's keep looking for the ideal case. If now, P becomes less than one, then we start to have what we really want. A penalty of zero if the coefficient is zero. And then the penalty starts to flatten out, meaning. As long as the coefficient is non-zero, we get the same penalty. If we further decrease p less than one, I'm getting close to zero, we get exactly what we want. Zero penalty and equal penalty for everybody that is non-zero. So the way we are going to measure sparsity is with this function. For P equal zero. And that's often written. As in this fashion with a zero here, and a zero there. This is what's called a L0 pseudonorm. It's not really a norm, and that's why it's called the pseudonorm, although very often, it's called also the norm, with the understanding that it's not exactly a norm, and this is how we are going to measure sparcity. We are going to count the number of non-zero elements in the vector alpha. [SOUND] So this is what we basically have here. Signal represented as a linear combination of atoms from this, that we're not allowed to pick more than l of those atoms. So back to our problem of image denoising. The Maximum-A-posteriori estimation of image denoising. What we have, is that we want to represent our signal. Very closely, this is the measurement and this is what we want to be. We want to have a close representation, meaning very close. X have to be as close as possible to Y as long as it belonged to the right model and then we replace X by the alpha. Because we know that now we're going to be representing the signal as. The dictionary multiplied by alpha that not every alpha we basically must have the no more than L entries in alpha are non zero. To give a. Illustrative representation, and of course we get back. The signal by the alpha, where alpha is the optimal. So, in a, in a very simple pictorial representation, what we have is D alpha, this is D, has dimensions N by K. This is alpha, that has dimensions K. We'll subtract Y. That's aware approximation error. But we are not allowed to pick any alpha. We're only allowed to pick alpha that has at most L non-zeros, which means that we are going to be approximating Y by, at most. L columns, the linear combination of at most L columns of D. And from now on, the representation is given by alpha. Instead of X we use alpha and we know if we want to recover the signal we basically multiply by D. Now what we have obtained is a very low dimensional representation of. Our signal, and a low dimensional approximation of y. And the idea is that, if we reduce the dimension of y. Basically, we are getting rid of the noise. Because we are not allowing to use all of the items. We're only allowing to use very few, projecting the signal into a low dimension. And therefore, reducing the noise. It's the same as we saw with the points. We have points. On the plane. That if we say that we are only allowed to represent all these points with a straight line. With feet of straight line and we're basically projecting the points onto the straight line and by that we are denoising the points because we go into a much lower dimension. In this case we just go from two to one, but that illustrates the concept that we're going to a lower dimension of space and by that we get rid of the noise. In order to represent the noise we will need many additional atoms and that's why we are restricting alpha to be sparse. Now. Are we done? We are only at the very beginning of this week. So for sure we are not done. Let me illustrate a few of the problems that we need to still solve. Now. We were talking about this, minimize the error under the constraint that you are not allowed to pick more than L non zero entries in alpha. Is this the problem we need to solve? Maybe we can solve it in this way. Let us constrain here the error. You don't want more than the given error and find the sparse's possible vector that achieves this error. Or we can actually have a combination of the sparsity and error and try to optimize for alpha such that it minimizes the sum of the two terms with a coefficient lambda. So, we have three possibilities here. Sometimes the three are equivalent. Sometimes they are not. Which one shall we be using? Another problem. In this case, a theoretical problem. Will we always find an alpha? So, I give you a y. I give you a dictionary. Will I be able to find, for example, an alpha that is sparse enough, and represents this signal up to certain error. Is that possible? And if I find it, will that be unique? Will there be only one alpha? Will any alpha have the same support, the same non-zero entries? When is that possible? And of course what about a dictionary? Which dictionary should I use in order to get alpha as sparse as possible? This is going to be something that we are going to discuss quite a lot during this week. And these are some of the questions these very nice sparse modelling and sparse representations open. So what have we done? We basically started with image denoising as an example and we say, we need to model the signal, we need to understand what do we mean by image denoising, what type of clean signal are we looking for. And that basically opened a question to say, we need to define models. When we say we need to define models, we basically. Describe a model, which is the sparse model. The signal is a linear combination of a few elements. A few atoms of a given dictionary. Once we define that, are we done? Of course no. We have all these questions that we just mentioned, theoretical, computational, how do I compute that alpha and, of course, how do I compute a dictionary that is appropriate for the type of signals that we are looking for? So these are some of the questions that we are going to address during the next few videos. And I'm looking forward to that. This is, as I say, a very, very exciting topic. And very, very active topic in image processing right now. Thank you very much. Looking forward to seeing you in the next video.
