so thank you to a hugger and and Massimo
I'm sorry I couldn't join you yesterday
always indisposed as they say and I'm
feeling a little bit better today so
let's see how we go so it turns out that
quite a lot of what I'm planning to say
has been said I think by from cease and
probably by jean-luc and see mine
yesterday but maybe the perspective is a
little bit different and the colors are
different and the fonts different and it
probably doesn't hurt to hear it more
than once anyway so I hope that you'll
bear with me if you've some of this
stuff seems familiar so what I'll talk
about mostly in this talk is about
formulation rather than solution and the
next lecture I'll talk more about
solutions algorithms which is more along
the lines of what France he's talked
about this morning and also yesterday so
today I'll talk about problems and how
they've written as optimization problems
all right so our goal really essentially
is to do inference of our optimization
so many inference problems in all of
these different areas image
reconstruction image denoising signal
reconstruction supervised learning
unsupervised learning statistical
inference and so on what if overlap
between these areas but many of these
can be written as optimization problems
and here's kind of the standard general
form of what happens you make some
observations about some data and there's
an object we call that why there's an
object that you're trying to recover
let's call that X that's what you're
trying to get out of the reconstruction
process and there's some sort of
criterion G which is a function of x and
y and given the why you want to find the
x that minimizes g and that turns out to
be the one that you're looking for or at
least an estimate of the one that you're
looking for so G is the inference
criterion and the big question is how do
we find G where does it come from what
principles do we use to build a G that
will give us the right answer and the
answer is it comes from the application
domain and as many many I gave you a
large variety of problems on the first
slide that fit this format and the G is
going to be different
depending on which domain it comes from
whether you're doing machine learning
signal processing system identification
computer vision bioinformatics and so on
many many areas and I'll give a number
of examples in the rest of this talk
okay and just to emphasize what we're
doing here in minimizing G with respect
to X we're seeking the X such a G of x
and y is less than or equal to g of z
and y for all other possible choices of
z ok and then how we solve the
optimization problem and then we'll say
more about that during the rest of today
ok so very often g has this kind of a
structure and this came up in and
prosthesis lectures as well it's got two
times the first time as is that will
call h depends directly on why and the
second term doesn't depend on Y ok the
first term is a measure of how well X
fits or explains the data y so Y is the
set of observations that you've made and
h is like a fitting function can call
this but it goes by a number of
different names loss function
observation model data term
log-likelihood as we'll see in a moment
where that comes from ok so this
measures the fit between x and y and the
second term is called often called the
regularizer and it somehow captures the
prior knowledge of exit the plausibility
of X also known as the generalizability
man this is the term as prime C so this
is the term that helps you avoid
overfitting to the data if you don't
have the sigh here or if tau equals zero
then you'll do a very good job at
fitting the data that you see but you
may not do such a good job of fitting
the data that you don't see and so it's
important to include this time to sort
of take account of the of the hem data
that's not observed in the empirical
model and so tell here is a parameter
it's a real number that captures the
trade-off between these two terms the
regularizer in the fitting term so since
the Y is fixed for purposes of this
problem we often just don't we often
just leave it out of the formulation and
just write down the objective as a
combination of the fitting term and
oh wait times the regularizer okay so
how does this come from statistical
models well very often that you've got
you've got a likelihood model you've
given and what's the likelihood of
observing why given an X the X of course
is the thing that you don't know but
suppose you did know it what's the
likelihood of observing why very often
you can write down that likelihood in
this form has the exponent of the
negative of some function H of x and y
some joint probability function / some
normalizing term okay so often this is a
probability of seeing y given x the
prior probability probability of X might
be given by some other term it might be
the exponent of minus tau times some
other function of X again / some
normalizing term so using bayesian
principles the probability of observing
the probability that x is the thing
you're trying to recover given it is
observed why using Bayes law is given by
this expression here probability of y
given x times p of x divided by the
probability of y okay so if i take the
log of that term i'll end up with is
something that's exactly of the form
that have had on the last few slides the
log of p of x given Y will simply be the
log of P of Y given X which is just
going to be minus H of X Y ty a plus the
probability of a plus log of P of X
which is going to be minus tau times I
of X and then everything else is stuff
that doesn't depend on X so I can
basically leave it out these constants
will show up there and also the p of y
which doesn't depend on X so if I just
focus on the part that depends on X I
end up with is just this g of x and y ok
now here we're usually seeking the X
that maximizes this probability whereas
in optimization where usually we usually
think in terms of minimization so that's
why instead of trying to maximize minus
G which is what I do if I maximize it so
this log posterior distribution I try to
minimize G ok unless of course it's the
same thing
so often the X that we're looking for is
a maximum hard posterior estimate our
posterior estimate so this is the
bayesian derivation of this ma P
principle okay so let's look at the
forms of these this unknown X very often
you can write it as a vector of some
kind in some formulations and I'll give
some examples later on it's more
conveniently expressed as a matrix what
sort of regular acer's I talk a lot
about regular eise's in this part of the
talk what sort of regularization
functions are we looking for very often
we are looking to to make the matrix or
vector sort of small in some sense to
the suppress it sighs not let it blow up
too much another thing we often like to
do with this solution is to impose some
sort of sparsity on it to make sure that
it consists mostly of zeroes just a few
non zero scatter around the place
sometimes we also try to impose specific
kinds of nonzero patterns so we don't
just want it to be to have few non zeros
but we want those non zero as to maybe
occur in clusters or to follow some sort
of pattern in the case of a matrix we
might be able to we might want to impose
some sort of low rank on the matrix or
we might want to impose some sort of
smoothness or piecewise smoothness so if
X represents a function or parameters as
a function we might want to make sure
that that function is not too rough this
of course the same thing in when you're
trying to do spline fitting you off and
try to impose smoothness properties on
the spline you recover ok now there are
different kinds of writing the of
combining the data fitting term to the
regularization term and the one that
I've talked about so far sometimes it's
called tikkun of regularization or you
actually write down an objective that's
just a combination of the day determine
the regularizer but there are other
things you can do and my colleague Mario
Figueredo came up with these names
obviously he dug into the literature a
little bit and he noticed that one other
way that you can formulate this problem
is to minimize the regularizer subject
to some threshold on the data term ok
you require the data turn to be below
some threshold epsilon or you can go the
other way
and you can minimize the data tone
subject to the irregular z being less
than some threshold now it turns out
that very often in the literature you'll
see these other two formulations being
used but in fact they're all sort of
equivalent there's you know in some sort
of semi rigorous sense you can show that
these things are all roughly saying the
same thing and in fact you can use you
can actually use indicator functions to
write them rigorously to write the
second and third one rigorously as one
of the first as the first one okay but
in some in some terms it's easy to prove
things about things that are written in
these forms than it is to prove things
about the ticket off form but you should
bear in mind that if you can prove
something about one of these forms it
usually says something about the first
form as well okay so a quick review of
norms I think this is probably something
that you're all totally familiar with
but I thought it wouldn't hurt to have a
slide about it a norm is simply a
function that map's a vector space to
the set of real numbers exact set of
non-negative real numbers it has three
basic properties there's the homogeneity
property if you take the vector X
multiplied by a scalar the norm gets
multiplied by the absolute value of the
scalar it satisfies the triangle
inequality so if you add together two
vectors in the vector space V and take
that norm that's less than or equal to
the sum of the norms of the two
individual vectors and the third one is
that the only vector that has norm zero
is the is the zero vector okay so if
you've got a vector that's not zero then
it's guaranteed to have a norm that's
positive all right there the key
properties of a norm and here are some
useful examples one is that if the
vector space happens to be the vector
space of a Euclidean of real vectors of
length n then there's a so-called LP
norm where you sum up the components of
X raised to the power P and then take
the 1 over P root of that of course the
special case where P equals 2 is very
important people's infinity p equals 1
the limit as P goes to infinity of this
is
simply the maximum absolute value of the
elements of X and the two norm I
mentioned also the Euclidean norm the
one norm is just the sum of the absolute
values of the elements of X when you
were talking about matrices it's useful
to talk to think about the new Klingon
that will come up again a little bit in
some of the examples I do later so the
nuclear norm is simply the sum of
singular values of x if X is symmetric
like that if x is n by n we can write
this as the trace of the square root of
x transpose X that's the same thing some
of singular values okay this is helpful
when we're trying to find low rank
solutions this kind of a norm suppresses
the rank of the matrix in another
important case that's not a norm is when
you take this expression here and let P
go to zero okay and what happens then
well what happens then is that this
expression goes to the so called
cardinality with a zero norm that that
it approaches the sum it approaches the
number of non zeros in X okay the number
of nonzero elements in acts and very
often that's what we're looking for if
we try to impose sparsity on a solution
we're looking for a solution with a
restricted number of nonzero s okay the
problem is that this is not a norm it
doesn't satisfy those those expressions
I had earlier on okay in fact it doesn't
satisfy the first one here for a start
if I take a vector with a given
cardinality and multiplied by a scalar
its cardinality doesn't change okay but
its norm is supposed to go up and so
it's not going to satisfy that first
condition all right here are some
pictures of norm balls so if we're
dealing in two dimensions are two it's
very easy to see what norms look like
this is the the blue line here is the
set of points in our two that have a 1
norm of one okay where the one norm is
one that is the absolute value of x1 and
x2 sums up to one this one is where the
set of points where the two norm is
equal to 1 as x1 squared plus X 2
squared is equal
the one and this is the set of points
where the Infinity norm is one that is
the maximum of x1 and x2 absolute value
is equal to one okay when we go to three
dimensions the diamond is still a
diamond but now it's a three-dimensional
kind of diamond so the surface of this
object here is the set of points where
the the one norm is equal to one and
then of course the ball stays of all so
they you know if we're using the 2 norm
the surface of the sphere is a set of
points where the 2 norm is equal to 1
alright so let's thinks think about I'm
going to start talking about recovering
sparse solutions of underdetermined
systems now which is something that I'm
sure Simone and John we've probably
talked about a bit yesterday but let's
suppose I've got a an underdetermined
system I'm given a set of measurements
why and another I got Y by taking a
times some vector X but this matrix a
has fewer rows than columns ok M is less
than n it's an underdetermined system so
that doesn't seem to be enough
information here to recover X we don't
have enough L elements in general to
recover hex we can do to get to get
something with a unique solution we can
try to recover we can try to find the
lease norm ax that satisfies this
constraint so we can write down an
optimization problem which is to find
the x with minimum 2 norm that satisfy
this constraint and we can write down in
closed form what the answer to that is
ok the problem with that is it may not
be the answer that we're looking for
there's a whole manifold of axes that
will satisfy this condition and I've
just picked out one of them here the
chances are it's not the one I'm looking
for unless we're unless we're very lucky
ok so how do I actually find the one I'm
looking for well you have to tell me
more about what I'm looking for here ok
but often we mean with the one way that
we may be looking for might be the one
with say a Mac certain specified maximum
number of non-zeros where it might be
the X it satisfies this condition with a
minimum number of non zeros ok that
might be the one that's most you
for to us for whatever reason and so
this might be the optimization problem
that we really want to solve the problem
with this optimization problem is it's
too hard okay this is not even a convex
problem it's not even continuous here as
we pointed out if you take a vector with
a certain cardinality and you take one
of the zero elements and just tweak it a
little bit the cardinality is suddenly
going to jump by one okay so the
function will jump and it's not a it's
not a nice problem to solve okay now a
little bit about convexity no convexity
Zahl red even mentioned a whole lot of
times but i thought i'd define terms
here as well well we're talking about
convex sets the key property is if i
take any two vectors in that set and
then everything on the line joining
those two vectors also has to be in the
set so here's an example of a non non
convex set where the line goes outside
the set if you've got a strictly convex
set and given any two elements in the
set every element on the line joining
those two elements is strictly inside
the set in the interior of the set we
call that strictly convex here's an
example of a set that's convex but not
strictly convex has basically got a flat
edge when we're talking about functions
we can think in terms of extended real
value functions we don't have to insist
that the range of the function is the
reels it can be the reals including plus
infinity okay so plus infinity is
allowed to be in the range that's useful
when we're defining the functions to
include indicator functions of sets for
example so first of all it's a proper
function if it's you know if it makes
any sense proper functions of those
whether domain the set of points where
the function value is is finite or or
infinity is I'm sorry where the set of
points is fighting the set of function
values as finite is not empty okay so it
has some has some finite values in its
range the function is convex if it looks
like this okay if you take two points X
and X Prime and you look at the function
value on the line between those two
points
okay but that function that the graph of
the function lies below what you get by
just interpolating the function linearly
between those two end points so the
left-hand side of this expression is
given by the function graph here the
right-hand side is just given by this
linear interpolant between f of X and f
of X Prime and as you can see the true
function lies on or below the end linear
interpolant ok now it's strictly convex
if this is the situation if the function
if the function is strictly below the
linear interpolant every are accepted
the two endpoints here's an example of a
function is not strictly convex where
it's got a flat piece here and so there
are points between the two end points
where the function is equal to the
linear interpolant ok now lower semi
continuity turns out to be an important
concept here lower semi continuous
functions are one where if you're
creeping towards some point x0 and
you're trying to look at the limit of
the function values as you approach x0
it might suddenly jump down when you get
to actually when you actually get to x0
ok it may not be continuous if it were
continuous then this would be an equal
sign but it may jump down ok it's not
allowed to jump up so that's called
lower semi continuity so here are two
functions here this one is lower semi
continuous ok because when you creep
toward zero if you're creeping towards
zero from this side it suddenly jumps
down to here when you get to zero if
you're creeping towards zero from this
side it's continuous ok this one is not
lower semi continuous because when
you're creeping towards zero from this
side it suddenly jumps up to this
function value now why is this an
important concept well one reason is
that the epigraph of a lower semi
continuous function is closed so the
epigraph of a function so it can use the
board briefly the epigraph of a function
f is just the set of points x and y
where y is greater than or equal to f of
X ok so if I have a function that looks
like this
everyone's got variety convex function
the epigraph is the set of points above
the function line here the set of points
up here including the function line
itself so if you've got a lower semi
continuous function like I've got in
this example the epigraph here is going
to include this piece of the vertical
axis whereas here it's not going to
include that piece of the vertical axis
and so this set won't be closed this
epigraph won't be closed because this
part of the line is not in the set where
is everything else here and here is in
the epigraph ok and that turns out to be
useful and in many contexts many
optimization contexts okay some other
concepts that are useful when you're
talking about minimizing these functions
f coercive functions of those where as X
goes off to infinity the function value
goes to infinity in all directions it
turns out to be a useful concept in
making sure that you're it erodes don't
run off to infinity in fact it
guarantees that the set of minimizes
isn't on empty there's this other
observation that if F is strictly convex
then G has at most the set of solutions
has at most one element ok there can be
at most one solution here are some more
examples here's a function that's
coercive and strictly convex and you can
see it has a unique minimizer here's a
function it's coercive but it's not
strictly convex and there's a whole set
of minimizer's here it's whole range and
here's a function is convex but not
coerce ok because in this direction is
not going to infinity like this could be
e to the minus X for example this is the
classic example of a function is convex
oh that's bounded below but it doesn't
have any minimizes ok you can't point to
an ex that actually minimizes the
function another important concept is
strong convexity strong convexity is
well recall this is the definition of
convex with a lesson or equal to sign
here strong convexity is where you can
subtract off a strictly convex quadratic
function and it will still be strictly
convex or police convex
alright so if i take the right hand side
here and subtract off a quadratic
strictly convex function at 0 at the two
endpoints it'll still be quadratic okay
sorry it'll still be convex so here's an
example here this is the kite of the
function that I drew before strictly
convex now if I take that linear
interpolant and turn it into a quadratic
by subtracting this time you can see it
still lies above the true function okay
and that turns out to have nice
properties is just saw an in france
thesis talk you're able to say more
about the convergence of algorithms
under strong convexity than you can
understand vexa t so strong convexity
implies trick convexity but not the
other way around you can have strictly
convex functions that are not strongly
convex can anyone think of an example in
one dimension a strictly convex function
is not strongly convex x squared now
that's strongly convex because i can
subtract half of x squared from and it
will still be convex let's close with
that exponent yeah II let's see e to the
minus X would be no e to the X here that
would be strictly convex but not
strongly convex right because as you go
to minus infinity of the curve which he
goes to zero that's true another one is
X to the fourth okay x to the fourth is
strictly convex but not strongly convex
okay it's just a few notes here about
composition of convex functions if you
take the max of a bunch of convex
functions it's still convex if you take
the Conn the composition of a convex
function and a fine function that is a
function of the form ax plus B that's
convex if you take a positive linear
combination of a bunch of convex
functions that's convex and importantly
this is why something I mentioned
earlier if you've got a set a subset of
RN this is very important object called
the indicator function and that's the
function at 0 when X belongs to the set
and infinity when X
doesn't belong to set ok so if C is a
closed convex set it turns out that this
indicator function is a lower semi
continuous convex function and that's a
useful property ok because it means that
sometimes well we can write constrained
optimization problems as unconstrained
problems by simply replacing a
constraint that x belongs to c and i can
take that constraint and replace it with
just adding a multiple of the indicator
function to the objective and I've got
an equivalent problem and if the CEO is
a closed convex set the object that
contribution to the objective is going
to be a convex function ok now if you've
got suppose you've got a nice smooth
function one that you can that's twice
continuously differentiable say you can
sort of see the convexity properties of
the function by looking at the Hessian
ok so if F is a convex function that
means this Hessian is positive semi
definite everywhere if F is strictly
convex then hit session is positive sum
is positive definite for all X ok at
least it's implied by that this is a
sufficient condition not necessary if
it's a strongly convex function you can
say more it's Hashem is bounded below
the eigenvalues of the hash and a
bounded below by some positive constant
ok that's what you need for strongly
convex so again the Hessian can tell you
about properties of strong convexity all
right so let's go back to this problem
of trying to recover the minimum
cardinality solution of a of a linear
system ax equals B so here the notation
is a little bit different and I've sort
of relaxed the condition that ax equals
B I've replaced it with this condition
here that ax minus y aw minus y is less
than or equal to some threshold ok so
that's an np-hard problem it turns out
in general computationally this is very
hard to solve there's a very similar
problem that's just kind of the flip of
this where you try to minimize the two
norm subject to the cardinality being
below some some some threshold that's
also np-hard ok difficult problems
however you can get away with this is a
very important principle and in fact the
central principle
presenting as you can often get away
with replacing this cardinality the zero
norm with a 1 norm ok under certain
circumstances and that turns it from
being a hard problem into an easy
problem in fact a convex problem so you
may have seen this picture already this
this picture is literally on t-shirts
that were produced a few years ago by
colleagues at Rice that illustrate
compressed sensing so here we've got the
setup I showed you earlier you've got
you're making observations why because
an observation matrix a and this is
unknown vector W and in general and if
you know nothing else about W then than
just the observations it's impossible to
recover the W that you really want
there's a whole manifold of w's or a
whole subspace that's satisfying the
giver observations why ok and in fact it
you know as we said we've shown that
this is an np-hard problem however you
can show that you can recover under
certain properties on the noise and the
properties of hey you can in principle
get the the W that you're looking for by
solving this problem which is an np-hard
problem alright but Candace that all
showed in two thousand around two
thousand six candidates Romberg and tau
show that you can replace the zero norm
with a 1 norm and you can suddenly turn
this objective from being discontinuous
and nasty into an objective of that's
convex ok continuous not any continuous
for convex and you can get a convex
optimization problem and if you're if a
satisfies the right properties you can
actually get the same answer ok so what
sort of properties do we need a to
satisfy in order for the substitution to
work well as a whole range of different
properties but they're all basically
closely related ok so if you know for
example that ok so one of them is the
following that if you take all possible
vectors that have at most K non zeros in
them and you form the matrix product of
a times W for those non zero value
is then the norm of a times W can't be
too much different from the norm of W
okay in other words is a constant Delta
between 0 and 1 such that Norm of aw is
not too different from the norm of W
okay difference captured by the Delta
constant Delta and this only has to be
true for w who's that have fewer than K
non-zeros another way to say this is it
if i look at the matrix a which has more
columns and rows and if i take out all
possible column sub matrices of k with
at most K columns okay but that that
column sub matrix were the most K
columns is not too far from having
orthonormal columns okay so any
collection of K columns out of a looks
kind of like a slice from an orthogonal
matrix so that's a very strong property
it's a property that fortunately is
satisfied by randomly generated a so you
can get a's that a high probability will
have this property if you just generate
them by some from the some random
distribution there are similar
properties called spark and a null space
property this one's called restricted
isometry they're all np-hard it's all
it's all difficult to check whether a
matrix satisfies these properties now
evenly what you'd have to do is to go
through all possible collections of K
columns drawn from a drawn from the
total of n columns so naively you'd have
to check all n choose K possibilities
that's obviously hard and in fact it's
provably hard all right but as I said
fortunately these things can be
generated with high probability from
from random distributions all right so
I've got a few slides here actually
proving that for a randomly generated a
using a 1 norm solution will actually
give you the exact solution of the 0
norm problem and I think this is a
remarkable result there are many other
arguments that prove roughly the same
thing this is one of the simpler ones I
think so I want to work through this in
some detail
alright so here is the problem we're
trying to solve I'm assuming there's no
slack here there's no noise that the
wise their exact observations of a times
X and the properties of a I'm going to
talk about in a moment what we use what
exactly what we assume for a in this
setting so this is a problem we really
want to solve and now i'm just going to
replace the zero norm with a 1 norm and
i'm going to talk about solving this
problem okay so let's suppose we know
the solution of this problem let's
suppose it's X bar I want to find out if
I can under what conditions is X bar
also going to solve this problem okay to
prove that x-bar solves this problem I
have to show that if i take x bar and
add any v to it where v is in the kernel
of a that i'm only going to increase the
one norm okay i know because X bar
solves this problem i know that ax bar
equals y okay and so any other feasible
point for this problem is going to
satisfy a times X bar plus v equals y
which means that a times V equals 0 so
to check that X bar is a solution of
this problem i just need to check this
condition here if i add any element from
the kernel of a to X bar I'll increase
its 1 norm okay so this is the this is
what I'm going to focus on here so this
actually came from a paper by ian and
john from 2008 early in the days of
compressed sensing and it was based on
work by work about random matrices from
these from the russian literature guess
by these authors right so here's the
argument this is what i'm trying to
prove again so first of all i'm going to
define s to be the set of indices where
the X bar I is not equal to 0 and z is
everywhere else z is the set of indices
1 through n where x bar i is equal to 0
ok so then given my x bar plus v either
one norm of that i can just break it
into two pieces because the one norm is
just the sum of absolute values i can
take the s part of this factor okay
which is just X by RS plus vs 1 all of
that and add it to the v
the Z part of this vector now the Z part
of this factor the X bar Z is equal to 0
okay so there's no X bar Z in this time
so this expression which I'm trying to
prove stuff about we can break it down
into that form okay now i can use the
triangle inequality point out one of the
fundamental properties of a norm i can
bound this this term below by x by RS
minus v sorry x bar s 1 or minus vs 1
not okay so what I've done there is use
the triangle inequality okay now what
have I done here let me remind myself so
first of all X bar s the norm of X bar s
is the same of the norm as the norm of X
bar okay because the the rest of this
vector is just all zeros so I can just
write x bar there okay what have I done
here well I've said let me write VZ as V
minus vs okay d minus vs and then I'll
apply the triangle inequality again okay
so writing this is V minus vs and then
taking the triangle inequality I can
write V Z 1 as the norm of V 1 as the 1
norm of V minus the one normal vs so
that's how I get that ok now now I've
used this inequality there's an
inequality all norms are related okay
when we're talking about Euclidean and
space so it turns out that the one norm
of any vector in in in the set of n
vectors vectors of length n is bounded
above by the square root of n times the
2 norm ok so I've used that inequality
here to rewrite vs 1 i'm bounding it by
square root of k x vs 2 because remember
s has only K elements in it okay so I'm
not really working in n-space here i'm
just working in k space okay s has only
K elements all right so there's my upper
bound there now remember i'm trying to
prove that this is bigger than that okay
that's going to be true if this term in
red here is guaranteed to be positive
so I will have achieved what I'm trying
to do showing that x-bar achieves the
minimum 1 norm provided I can show that
any vector V that's in the kernel of a
has this thing being positive alright so
just rearranging that a little bit what
I need is that for all these in the
kernel of a I need the ratio of the one
norm of V to the tune on movie times
one-half to be greater than or equal to
square root of K all right now it looks
like that's not going to be possible
because all i can guarantee in general
from when I'm dealing with general
vectors of length n is that the ratio of
the one on to the two norm is between 1
and square root of n okay that's all i
can guarantee that's not enough to
guarantee this here i need it to be
bigger than that i needed to be this
ratio to be bigger than two times square
root of k however i only have to
restrict my attention to the kernel of a
okay this I don't need this to be true
for all vectors V and RN I only needed
to be true for these and remarkably
provided i choose a in a certain way I
can almost guarantee that this will be
true okay so what do we need we need a
to be chosen randomly okay so if a if
the colonel of a is in fact a random
subspace of RN if you if you generate a
by taking its elements to be sampled in
ID from the normal normally distributed
elements from mean 0 and variance 1 then
you can actually show that a high
probability the ratio of the one norm to
the two norm for of vectors V in the
coal ave is bounded below by this number
here okay now remember in general or we
can assert is that it's bounded below by
one but if you generate a in this
fashion and take V in the kernel of a
you can show a much stronger lower bound
okay depends on some constant times the
square root of m m is the number of rows
in a divided by the square root of the
log of the ratio of em into him okay so
you get a better lower bound and that's
good because we wanted a better low
about okay we need the law
to be bigger than two times root k so in
fact if you can show that provided the
number of rows in a is bounded below by
this quantity some constant times K
times log in that that's enough to
almost guarantee to high probability
that this bound will be true okay so
this is the magic of compressed sensing
is that provided you have enough
observations it probably is still a lot
smaller than n you can guarantee that
the solution of the one norm problem
actually solves the zero norm problem
the original apparently np-hard zero
known problem okay so let me show some
pictures that sort of illustrate how
this happened so what I've done here is
I've taken I've got to remind myself
it's a couple of years since I did these
experiments but what I've done is taken
vectors in R seven okay this is a seven
dimensional space unfortunately it's
hard to depict anything bigger than
three dimensions pro taken vectors in R
seven and I've generated a random matrix
with four rows so the kernel of a is
going to be a three-dimensional space
okay which is something I can draw a
picture of so what I've done is
generated this a randomly in the same
fashion that I showed you by picking its
elements to be normally distributed 01
and I'm plotting here the unit ball in
the kernel space so I'm taking all
vectors in the three-dimensional kernel
with it with a 2 norm of one and I'm
color coding it according to this ratio
of the one norm to the tune on well the
two nums always one so I'm just plotting
the one and I'm color coding it so it's
blue if the one norm is close to 1 and
red if it's close to the upper bound of
square root of 7 you can see from this
picture that there's no blue okay in
other words it's well away from its
lower bound there's quite a bit of red
in other words it tends to be closer to
its upper bound and that's exactly the
property that we want okay we want it to
be away from its lower bound we want it
to be bigger than two times square root
of K and that's what we're seeing in
this picture okay
here's a this is how what happens when I
go even more extreme when I take the 20
dimensional space and generate a to have
17 rows okay again I've had to choose
enough Rose that the colonel is only a
three dimensional space and again if I
do that same plot of what is that one
norm versus the two norm over the
colonel you can see that it's almost
always it's almost all red okay so in
other words it's much closer to the
upper bound on the lower bound and
that's a property that we need for
compressed sensing to work okay so there
are many other arguments that are made
they have a I'd say kind of a similar
flavor to that that shows that the one
norm is a good proxy for the zero norm
or for the cardinality count in many
circumstances all right so that was sort
of an idealized situation usually we're
dealing with noise here here is kind of
a depiction of what you get when you
when you do compressed sensing with them
with the one norm so here we've got a
we've got a combination of a fitting
term which is a which is a 2 norm and
the turn on is appropriate because I've
got am assuming here that the noise is
iad Gaussian so it turns out that the
two norm is a good way to measure the
fit between the observations and the
predictions and then the one or Miz is
doing its job as the regularizer here
and you can show if you've got a a code
that minimizes this function and
provided you choose the lander
appropriately that from a set of
observations why you can actually
recover the sparse solution that looks a
lot like the original data vector ok so
this principle has been around for a
while in statistics people are
interested in things like basis pursuit
denoising there was this thing called
lasso that dates to 1996 and came up in
the context of feature selection where
you're trying to find which elements of
X are really important in predicting the
outcomes why again trying to look for
sparse X that satisfy a x equals y
approximately it's been widely used it
was discovered in
many other areas the use of the one norm
to induce sparsity was discovered much
earlier than then it's kind of rigorous
our derivation and compressed sensing
and there's a whole bunch of citations
here where people in other fields radio
astronomy actually geology and
geophysics is one of the first places
this came up when I was writing my
thesis back in the mid-80s I had a
chapter on geophysical inversion and
people there were in this field we're
already using principles of using a one
known to induce some sort of sparsity
regularization okay so why does it yield
sparse solutions I've sort of explained
that a little bit in that idealized
example but here are some pictures that
maybe build the intuition of ghosts away
the solutions that you get from using a
one enormous space going back to those
unit balls that I drew earlier for the
for the one Norman to norm suppose you
solve this sort of a problem you try to
find the W that minimizes the fit the
fitting function a subject to the one
norm being below a certain threshold so
the blue pictures here the contours of
this quadratic function okay they tell
you the fit and this is going to be the
constraint in this particular
formulation so you can see here that
there are many places that I can place
this quadratic function so that it's
constrained minimum will be at one of
the corners of this square ok so if them
if the if the quadratic of course we're
kind of lucky here in the quadratic has
circular contours more generally will
have elliptical contours but there are
many situations where the minimizer will
be exactly at one of the corners of
course there are others where it won't
be at a corner in which case you won't
get a space solution you get a solution
with two non zeros however if you've got
the two norm here you'll almost never
get a solution that's at one of these
four corner points ok and one of the
four points where you've got a sparse
solution it will generally be somewhere
on the surface of the of the ball and
you have to be very lucky for it to land
at one of the corners ok so a little bit
more detail on yl1 yield sparse
solutions
alright if we just ideal as if we break
this down to just a single variable okay
if we have a combination of the two norm
and the one I'm just in a single
variable you can write down in closed
form what the solution of this problem
is so given the why it's now a scalar
the solution of this problem finding the
W that minimizes this is a so-called
soft regularizer okay it's given by this
solution if the way it has absolute
value less than lambda the solution is 0
0 if it's bigger than lambda then the
solution is y plus or minus lambda
depending on the sign of Y so you can
see that when y is close to zero the
solution this problem it actually pulls
it down to zero okay and so and that's
how it's inducing sparsity if it sort of
gets close to zero in this prediction it
pulls it exactly 20 that's what the one
norm does so here is a picture of what
that function is doing there's a whole
range of values here it actually goes to
zero whereas if you're using the 2 norm
here instead of the one norm if your
places with the two norm again you can
solve that in closed form and but the
solution is just a scalar times y okay
so we'll just shrink it towards the
origin but in general how the sparsity
of this solution of that the w here is
just going to be the same as the
sparsity of why okay all right you can
also write down what the solution of
this problem is for the case where
you've got the 0 norm here not really a
norm but suppose you have the
cardinality here you can write that down
as the hard thresholding operator okay
and that operator is again it's just 0
if y is less than square root of two
times lambda and it's y if Y is bigger
than square root of two times lambda so
if I draw a graph of that of the hard
thresholding operator it doesn't look
too much different from the soft
thresholding operator okay out here out
here when y is different from lambda it
looks basically the same it's just that
that one norm is kind of compressed it a
little bit towards the x-axis but in
this range here it's exactly the same
okay so this is one kind of another
indicator that this is a pretty good
proxy for that
even though the problems we have to
solve if we use this guy a convex and
the problems we have to solve if we use
this guy a combinatorial okay okay a
little bit more and I'll say more about
this I think in a last talk today when
we're doing image processing which I
know a lot of people here are interested
in very often images are really sparse
objects in disguise okay there's a sort
of inherent sparsity and images that is
not always apparent from just looking at
them you know as a collection of pixels
so often you can represent images for
example using a wavelet basis and
sometimes if you choose the basis
appropriately if X here is a is the just
the set of pixels in the image with a
value proportional to the the grayscale
intensity of the pixel then you can
sometimes represent the pixel by pixel
count as the wavelet basis time some
coefficient vector and often you'll know
that you can represent the image
adequately as a combination of a fairly
small number of wavelets in other words
you're looking for a coefficient vector
W that has has a relatively small number
of elements okay so you can reformulate
the problem in terms of W and seek a
sparse solution that's one way to deal
with this okay and so if you've got a
problem like this an image
reconstruction you can you can write oh
yeah okay so I've rewritten the the
problem here in terms of the wavelet
coefficients okay so in other words I
get the actual image by taking the
coefficients x times W which takes me
from the wavelet domain into the real
domain and then there might be some
something that happens in the real
domain and the pixel domain like there
might be some sort of convolutional blue
that's going on and so the observations
on making might be some blurred picture
of the true true image and so very often
I can recover a much sharper image by
solving this regular eyes problem where
where I impose some sort of sparsity on
the way
the coefficients so this is an actual
picture of a blurred image where we've
we've solved this problem and recovered
a much sharper image from it of course
here we assume that we know what the
blurring operator is okay and that's not
trivial in in applications figuring out
what the blur operator is but here I've
assumed that that's known here's another
application to magnetic resonance
imaging and here again the trick is to
work in the right basis to impose
sparsity in the right basis so here
we've got a composition of a wavelet
basis it takes me from wavelet space
into real space and sorry into I guess
into frequency space then there's some
sort of DFT going on and then there's a
binary mask so I think this is I don't
know much about this application but I
believe this is typical of MRI and so
again you've got some sort of original
image in the DFT domain how the
acquisition the data that you're
actually observing looks like this then
when you do the reconstruction using
this with an appropriate value of tau
here you get an optimal X an optimal set
of wavelet coefficients you multiply
that by the wavelet basis to get you
back into real space and you get this
image and you can it's actually not
obvious in this resolution what the
improvement is I can't see much
difference maybe you can from a distance
there but believe me this is nicer than
that one okay yeah you'll have to trust
me on this oh I see okay oh good all
right yeah that's true that's true okay
yeah powers of two minutes oh I'm sorry
yeah yeah I went over the break yeah
should we should we stop now briefly
yeah let's have a two minute break yeah
this is great sorry about that I should
have stopped early I've got a bit
I've got about 20 minutes left in the
session is anyone faint people in the
middle should get to say because they're
probably the warmest great ok I can get
a drink too
what's huh ok running
you