Welcome back so we're talking about compressed sensing and how we are able to reconstruct a full
high-resolution image, or whatever signal we're working with, an audio signal or image, from a
dramatic subsampling of the information. So even if I only had a small number of random pixels from
that image can we infer what the active Fourier coefficients in that image are in this vector "s",
the sparse vector "s", and then can we use those to reconstruct the full image in "x". Okay so
we're gonna walk through now the math of how to do this. So this is kind of the matrix form,
a pictorial form, of this system of equations that I've written down here okay so "Psi" is our
universal transform basis. In this case I think this is a discrete cosine basis but you can think
of it as some Fourier basis or some wavelet basis. "s" is my sparse vector of coefficients here this
is kind of a cartoon where there's only three nonzero coefficients everything else is zero so
here white is zero okay and "y" is my measurement. So this C matrix here what C is doing this is my
measurement matrix it is basically pulling rows of Psi time "s". Psi times "s" is "x" my original
image. So C pulling rows of this basically means it's sampling pixels from X so Y is just
a subsample of random pixels from X okay that's what Y is now this system of equations is what's
called underdetermined this is really important this is an under determined system of equations
and we've seen this before in the SVD chapter we've seen systems that are under determined
before we have measurements of Y we know what C and P I R we know which pixels we measured and
we know what our Fourier transform basis is and we're trying to solve for s the sparse vector
of coefficients that is consistent with those measurements okay now there are this Y vector
has only a few entries in it and s might have a million entries and so there are infinitely many
solutions of this system of equations there's infinitely many S's that when I multiply by C
times I I will get back at this measurement Y and that's what I mean by underdetermined is that out
of all of those infinitely many S's how do I find the right one that is actually the Fourier
coefficients of my my image okay and so this is where it gets really interesting in this this is
again this is an underdetermined inverse problem okay so because we're basically trying to invert
Y to solve for s that's called an inverse problem so this is an underdetermined inverse problem and
so we're gonna have to use additional information out of all of these infinitely many S's we're
gonna have to use additional information to find this very special particular s for you know in
our Fourier transform basis okay now if you had written down this math problem you could have
written this down a hundred years ago and people would understand basically what you're trying to
do but you wouldn't have been able to solve for this s finding the very particular s that
satisfies this equations that happens to be thus Parsis s in your Fourier basis people wouldn't
have been able to solve that problem it's called a combinatorial e hard problem you literally have to
try all combinations of entries to try to find the Sparsit s that satisfies the system of equations
okay and it's only in the last 15 years that huge advances in applied math and statistics have
given us algorithms to solve for the sparsit's s the s with the most zeros that satisfies this
equation in a scalable robust fashion so there is great work by Donahoe and can des and Romberg
and tau biruni a crop many others there is a huge literature on this starting in the kind of early
two-thousands like 2004 to 2006 that developed a mathematical framework to solve for the very
particular s that we're looking for out of this infinitely many solutions and the s that we're
looking for we want the sparsit's s so solve for the sparse cysts s out of all possible s's that
you could solve for and remember that's based on this fundamental observation that all signals are
compressible in these Universal transform bases so X when I afford when I Fourier transform it
is going to be ultra ultra sparse so what I'm looking for is a vector S that satisfies this
system of equations and is as sparse as possible good ok so there are many many ways to to solve
for s here and I'm just going to write down a few different ways of writing this optimization
problem and then show you what this looks like ok so what I could write down is I could write
down then we're trying to minimize we're trying to find s that minimizes C times sy times s minus y
and we're going to try to minimize this in the two norm because I just want I want Y and C times side
times s to be as close as possible and effectively I want this to be 0 I want to find s that exactly
satisfies this but remember there are infinitely many S's that satisfy that and so what i can do
is i can add on this penalty term so there's some constant lambda just a number that tells me how
important this next term is times the norm of s and what people have done a lot in the past
is you would put a two norm on this s and this is this is what we did when we looked at the singular
value decomposition for underdetermined systems is we solved for the minimum two norm solution of
the system of equations but when you solve for the minimum two norm system this is what you get okay
so this is the S that has the minimum two norm that satisfies this system of equations C times
psi is Theta here ok and notice that s is kind of dense it has a little bit of energy in all of its
entries and that's what this two norm does the two norm spreads out the error in the the entries of
s so that you have the smallest radius possible but every term is active okay and so this s most
certainly does satisfy this system of equations but it's not at all sparse it's not the solution
that we want okay and so instead of doing the two norm what we can do is put in this one norm here
okay and the one norm I'm going to tell you all about the one norm later but what the one norm
does is it promotes solutions of the system that have as many zero entries as possible so when you
solve for the minimum one norm solution this is what you get you actually find the original
solution s that is as sparse as possible so if you're looking for solutions s to this system
of equations that are as sparse as possible this is the kind of optimization that you want to be
solving you want to minimize the error in the fit we know C we know PI we know why we're solving for
s such that S has the minimum one norm and that's going to give me the sparseness possible solution
and that's going to allow me to solve solve this problem in a in a convex optimization so okay I'm
gonna point out a couple of other things this is really important because this is a convex
optimization problem which means that it's not combinatorially hard it even when your problem
gets bigger and bigger and bigger even when this matrix and the specter get bigger and bigger and
bigger this scales efficiently with Moore's law so the you know the bigger the problem you have
you can just wait for computers to get faster and you can solve those bigger problems whereas
before solving this this optimization problem was combinatorially hard if you double the size
of your problem it might take a million years for your computers to get faster with Moore's law to
solve it okay so I'm glossing over a lot of stuff here I'll tell you more about kind of what I mean
by convex optimization and combinatorially hard and Moore's law and all of those things
later we'll talk about but what I want to point out is the problem we actually want to solve is
the minimum zero norm because the zero norm of s literally counts how many nonzero entries there
are in s but this is not convex you can't solve this efficiently with computers and so the big
advance in that that early 2000s I was talking about is showing that if you replace that with a
one norm with high probability this will converge to the sparse solution that we actually want okay
so that's really the big idea here in compress sensing is that we're gonna find the sparse a
solution to this underdetermined problem using l1 regularized optimization there's other ways
you can write this I'll just write down one more for you before I go you could also write this as
minimize the one norm of s such that this si si s minus y equals zero the two normal that equals
zero okay you could also minimize this s1 subject to some constraint on this being true and in many
cases if you have some measurement noise so Y is not exactly C times I times s but there's
some measurement noise this might not be exactly equal to 0 and so you can say that this has to be
the minimum one norm subject to this error being less than some epsilon or some threshold okay so
takeaway here is that there are lots of ways of writing this optimization problem and the
l1 norm will promote the Sparsit solution out of all of the infinitely many solutions to this
underdetermined problem the l1 norm is going to give us the sparsa solution and remember just to
take a step back that s is my vector of Fourier coefficients which we know is sparse for natural
signals so once I solve for this sparse s I can reconstruct my full image just by inverse Fourier
transform ok it sounds like magic it is absolutely not there are rigorous conditions on what kinds of
measurements you can take how many you need and when this optimization will and will not converge
so that's all coming up and then we'll code this up in Python and in MATLAB okay thank you