noc18-ee31-Lec 56 | Applied Optimization | Compressive Sensing -II

[Music] [Music] hello welcome to another module in this massive open online course so we are looking at compressive sensing right where you try to compress not after the sensing process all right so you try to compress during the sensing process itself by making much fewer number of measurements in comparison to the dimension of the signal and then later try to reconstruct the signal from the very few measurements made all right so let us continue our discussion on compressive sensing let us see what are the necessary conditions for this so you are looking at compressor sensing and what we have seen is one thing that has to be done we are doing is essentially you have a measurement vector Y of equals Phi times X bar and this is you're sensing matrix and you have M measurements y1 these are your M measurements you have your matrix Phi and I'm going to draw this vector much larger than Y bar purposefully because you are making much fewer measurements than the length of the signal X okay so this is your measurement vector and this is your signal and this is you're sensing matrix and remember this is an M cross n matrix and what we have is that M is less than or equal to and that is we make significantly fewer measurements or let's say m is significantly lower than L all right now if you view this as a system of equation equations then we have M as a number of equations n equals number of unknowns or number of equations is less Sigma e lower than the number of unknowns so simple linear algebra tells us high school-level linear algebra tells us that one cannot reconstruct the vector X bar of length n which basically comprises of n unknowns from simply M equation since the number of equations is much lower than the number of unknowns so this is an underdetermined system all right so our stresses so one cannot uniquely determine X bar therefore this system the sensing system has to satisfy certain special properties in order to recover X bar from the observation now what are those conditions or what is what the properties the system has to satisfy that is what what to look at so so in order to recover or reconstruct in order to require x-bar from y bar the sensing system must satisfy some conditions what are those conditions for instance let us look at the first condition the first condition states that this must satisfy something the first condition states that measurements are not simply in the time or space these are not simply in time or space okay these are not simply in time or space rather they have to employ noise like measurements have to employ noise like noise like or one can say pseudo noise or noise like these have to employ pseudo noise or noise like waveform but let's just say noise like waveforms measurements have to employ what is the meaning of that the meaning of that is if you look at this sensing matrix Phi okay if you look at remember we said we have the sensing matrix which is M cross n which means there is M rows and M columns if you look at each row which we are denoting by Phi 1 bar transpose Phi 2 bar transpose Phi M bar transpose so these are the rows so each row of the sensing matrix each PI I bar transpose which is the eyath row has to be a random noise this has to be a noise like way for which means that it has to be something very random it has to look like a random or pseudo-random sequence for instance like some random sequence of either can be a random sequence a random sequence of minus 1 comma 1 or it has to be some random noise like waveform such as Gaussian or so on so it has to be either a random noise like or a random sequence 1 minus 1 so so each row that is if you denote the I throw by Phi I bar transpose of the sensing matrix Phi this has to look like noise just to look purely like noise it cannot be one followed account so the matrix Phi cannot look like an identity matrix 1 followed by 0 0 1 0 it cannot look like an identity each row has to look like and these rows have to look like independent realization of the noise waveforms alright and thereby when you are making the measurement what you are doing is you're taking the projections of the signal on this noise like waveform so when you are making the measurements you have your y1 y2 y M which is equal to y1 bar transpose Phi 2 bar transpose Phi M bar transpose times X power so this is equal to why one bar transpose X bar fight over transpose X bar by M bar transpose X bar so each is a projection so each measurement if you look at this each [Music] measurement I which is PI I bar transpose X bar the measurement Y is fire bar transpose X bar this is the projection of X bar this is the projection of X bar on the random noise like waveform fiber this is the projection of X bar so what you're doing when you're taking these measurements which is each row of five the sensing matrix is a noise like waveform and when you take in the measurement what you're doing is nothing but taking the projection of this X bar a linear combination of X bar using this noise like waveform which is the Rho Phi a bar so the eyuth measurement is Phi by transpose X bar all right so that's an important property of the sensing matrix okay now let's talk about the say vector X bar now the vector X bar itself has to satisfy an important property and this I would say is the important property of most important property important property of X bar the vector X bar and I am going to introduce this terminology which we are going to use very frequently X bar has to be sparse and this is a very important property X bar has to be sparse what is the meaning of this remember when we say something is sparse when we say an area is sparsely populated which it means that there are very few people in that all right this is sparse implies that it's very few some its sparse and some object implies there's very few numbers of that sparse object in particular if it's sparsely populated a country is sparsely populated implies that there are very few people in there now X bar is sparse implies that very simply it implies that a large number of entries of X bar are 0 only very few entries are nonzero so this implies that basically what this implies is that large number of entries so sparse implies a large number of our zero only very few entries which are marking by these XS for instance only very few entries are nonzero only very few entries are nonzero so a large number of entries of X bar are zero very few into it so X bar is a sparse vector or so X bar is first or alternatively and this is typically what happens or X bar equals size sub matrix I times alpha bar so X bar is n cross 1 this alpha bar is n cross 1 and sy is an N cross n basis such that alpha bar is a sparse vector that is alpha bar equal sparse implies alpha bar has very few alpha bar has very so so either X very sparse the oil vector that you are trying to recover or more importantly and this is what happens more frequently like an image X bar can be expressed as a linear transformation of a sparse vector for instance we take an image image if you look at it in the spatial domain it's not possible if you take it for instance the wavelet transform it's an excellent example if you look at the wavelet coefficients of an image then they're sparse very few coefficients are nonzero so therefore I can have an image X bar which is I times alpha bar so let us say this is image these are the wavelet coefficient and this is your wavelet transform matrix linear transform okay so x-bar a sparse or x bar can be expressed in terms of alpha bar which is sparse and therefore now if you substitute this the sensing model becomes y bar equals Phi X bar equals Phi sy times X bar equals Phi tilde times X bar okay I am sorry Feist I times alpha bar and if you do notify sy as Y Phi tilde the effective sensing matrix this Phi tilde now becomes your effective sensing matrix and now alpha bar is sparse and you still have the same relation this is M cross 1 this is M cross N and this is n cross 1 now in this model it's as if you are trying to you are trying to sense the vector alpha bar which is in the wavelet domain okay now once you get the wavelet coefficients naturally you can reconstruct the image right because image and wavelet they have a one-to-one correspondence if you have an image you can represent in terms of its wavelet transform right if you have the wavelet transpose the wavelet coefficients are condensed of the image all right but the wavelet coefficients satisfy a very important property which is that this coefficients the wavelet vector of wavelet coefficients is sparse and that is very amenable to compressive sense and this is what is sort of what frequently happens and the model can be extended right so your Y is equal to 5 times X bar you substitute for X bar sy times alpha bar so it becomes Phi sy into alpha bar and now you reconstruct alpha bar from alpha bar which is sparse vector sparse signal recovery a compressive sensing and then you get the image from the wavelet coefficients alright or X bar from alpha bar using X bar equal to C alpha bar so once you get alpha bar use X hat equals sy alpha hat to obtain estimate X hat from alpha hat okay so that is what you do okay and now if you look at this phi tilde matrix this has to contain noise like waveforms okay so phi tilde which is your effective sensing matrix has to comprise this has to comprise of noise like waveforms okay.what contains noise like waveforms okay now how do we construct this alpha bar or X bar if X bar is sparse how to reconstruct let us assume that X bar is sparse and Phi contains noise like waveforms now the question that we want to ask is how to reconstruct X bar to reconstruct X bar what we have to do is we have to enforce the Sparsit remember X bar is a sparse vector so we have two ends for sparsity so how to reconstruct X bar the answer is enforce parsecity what does it mean to say enforce pass it implies we have to somehow impose a condition that X bar contains a large number of remember we said X bar is a sparse vector so we have to enforce the sparse candy this capacity which implies that we have to ensure that the reconstructed vector X bar is such that a large number of elements are zeros only some elements are nonzero so which implies we have to ensure that large number of elements of X bar r0 we have to ensure that large number of elements of X bar are zero okay this is what in fact ensure that large number of elements of X bar okay large number of elements of X bar are zero alright so that X bar is sparse and this is precisely what is enforced by what we call the l0 norm that is if you denote the l0 norm of a vector this is l0 norm like similar to L 1 L infinity and L 2 norm this is the L 0 norm ok this L 0 norm and L 0 non this equals the number of nonzero element of X bar okay so this is precisely what you want to minimize the number of nonzero elements of X bar which is L 0 norm ok for instance let us say you have the vector X bar equals 0 0 to 0 minus 1 0 0 0 ok now L 0 now look at this is 8 elements but only two nonzero elements which implies if you look at Elsinore norm of X bar that is simply - all right so very simple all you have to do is count the number of nonzero elements of X bar all right whatever is the number of nonzero elements that is the l0 nothing else to be done so it's very simple their concept of l0 norm itself is very simple so this l0 norm concept this l0 norm concept is very simple but there is a problem so in fact the non zero elements we are not concerned with the values of the nonzero elements we just have the number of nonzero elements we we are not concerned with observed here and like the other norms not at all concerned with values of something that is strange for instance this could have been 2 comma 1 and in fact if you have another X tilde which is 0 0 3 0 5 0 0 0 nonzero elements are 3 comma 5 and if you look at l0 norm of X tilde that is also 2 all right it's the interesting part is we are not at all concerned with what are the values of these nonzero elements we are only concerned with the number of nonzero elements that is the most interesting thing about the l0 and that is what in fact makes it very complex this problem and therefore so the optimization problem for now reconstruction and therefore and this is very interesting therefore optimization problem for reconstruction of X bar is the same thing that we talked about we have the sensing model we want to minimize the l0 norm okay and now subject to the constraint that y bar equals Phi times X bar what is YY bar is observation vector that is what's something that we've seen already seen Y bar Phi sensing matrix S bar is a vector that we are trying to estimate X bar so we minimize so this is basically enforces what we mean by enforcing sparsity this is enforcing sparsity because we are minimizing the LG row now that is minimizing the number of nonzero elements so this is the relevant optimization problem and why do we need this we need this because M number of equations M is less than or equal to n which implies the number of equations is less than or equal to number of unknowns okay and therefore one has to exploit sparsity so reconstruction is only possible exploiting because as we said if you treat this reconstruction only possible via reconstruction only possible by exploiting sparse area so what does this mean you're enforcing sparsity which means you are trying to find here finding the sparse s vector find the sparse s Twitter which satisfies that satisfies the observation model okay so that is what the optimization problem is that satisfies observation model yqr equal to Y bar equal to 5x bar so it will be trying to find this persist vector okay now what is now we have written an optimization problem like similar to several optimization problems that we've seen before we have an optimization problem okay you might think that you can solve it similar to fashion that we have done before an optimization objective plus Lagrange multiplier the problem with this is this optimization problem not only the object of non differentiable this optimization problem is highly non convex if you look at the l0 norm norm X bar 0 L 0 norm this is highly convex this is highly non-convex implies very difficult to solve above optimization problem very difficult to solve over an consider a simple technique what you can do is for instance let us say you have M elements or m n equals size of X bar what you can do is set only one nonzero element of X bar solve it already you will have one equation you laugh one or no you will have only one unknown but the nonzero unknown can be in any of the N positions so we will have to solve n systems okay and then similarly you can have two nonzero elements the two nonzero elements can you can be in any of the two locations so you have n see two such combinations so you have to all NC two systems so so on and so forth if you look at this total number of total number of equations that have to be solved is n choose 1 plus n choose 2 plus so on and this will be 2 to the power of n or to the approximately you do not need to get it the exact number what you can see is this Rises exponentially ok so this is the order 2 to the power or you can write order 2 to the power of n so total number of systems it's just highly complex for instance if we have a signal vector X bar of dimension 100 then you have to solve 2 to the power of something of the order of 2 to the power 100 which is impossible all right that cannot be solved by any known computer either now or in a very far future right so the point is that this problem although it's very simple to state the optimization problem it is an extremely complicated optimization formula so now if you look at for instance the L 0 what is the L 0 nor if you look at for instance L 0 norm equal to L 0 norm if you look at a two-dimensional plane this one point has L 0 norm equal to 0 because that is the origin now this access other than origin if you look at this axis that has L 0 because on the axis you have only 1 is nonzero element so this is rest all of the plane other than axis and origin is so if you look at L 0 not less than equal to 1 that comprises only of the axis so access so if you look at this object it is highly non convex so if you look at the l0 nor ball the l0 norm ball this is the else this is literally the l0 norm ball which is basically highly this is highly non convex and that is the problem in solving this optimization problem all right so we would like to make very few measurements agreed projections or noise like waveforms agreed the vector X bar is sparse or its parts in some appropriate domain X bar equals I times alpha bar but the problem is that the problem eventually the problem that has to be solved in for sparsity which is basically minimizing the elbow l0 norm that has an exponential complexity it's an np-hard problem and which is therefore practically impossible to solve for large signals X bar that is signals of the size let's say even 20 samples 20 samples or 25 becomes very difficult exceedingly difficult and if 100 samples it's impossible to solve and therefore one has to come up with other ingenious techniques to solve this optimization problem and that is basically at the heart of compresses and see what are the other techniques that can be used to solve this optimization problem which we are going to look at in subsequent modules that forms the basis for compressing and that is what in fact these techniques have revolutionized the field of compressors alright so let us stop here and continue in the subsequent modules thank you very much [Music] [Music]