0:00:13thank you
0:00:17yeah so uh
0:00:18i should apologise if i'm gonna be able to
0:00:21incoherent uh in this talk is met mention that just came from the airport
0:00:25um there was
0:00:26tornado in the midwest so i slept last night and dallas
0:00:30kind of debating whether to
0:00:32come here and a
0:00:34um so that so that is the good news is you know this is a simple paper um it has
0:00:38a single uh message um and i should
0:00:42and by that can that be so
0:00:44uh this is joint work with my students summit and i mean and as was mentioned
0:00:49weighted compressed sensing
0:00:51and a little bit with right
0:00:53um so here's the outline of the talk so what we want to look at is compressed sensing when you
0:00:57have some sort of prior information i mean in particular
0:01:01we assume that if you look at your your signal you can break it into partitions and you know something
0:01:06about roughly the sparsity of each partition so
0:01:10you're not assuming that sparse it is uniform over your uh signal you know what differs in different different chunks
0:01:16and we want to exploit that information
0:01:19i'll talk a little bit about to related work to not formally define the problem
0:01:23and then basically um the contribution of this paper as a said it's a simple thing we give a simple
0:01:28an explicit rule for doing a weighted compressed sensing weighted L one minimization
0:01:33um and that say a few words about how to extend this to rank minimization problems and i won't
0:01:39say a whole lot of about
0:01:42um so again
0:01:46okay i guess i need you know
0:01:50map type to make sense in the absence of math type of those squares are supposed to be i guess
0:01:55bold face are so X is that
0:01:57you know N dimensional vector this is uh just introduce the notation so the be a dimension is little and
0:02:03the number of measurements is am so is an him by and may
0:02:07um um
0:02:08and uh in compressed sensing of course the goal is to recover a a a sparse uh
0:02:13the signal X using you know if measurements than yeah been dimension and L one minimisation of all part of
0:02:19and there's a great could of work it's been done
0:02:21um people have looked at various algorithms um various models you know the previous top was a different algorithm the
0:02:28top with
0:02:29a statistical models
0:02:31and this star i want to focus on a trying to do compressed sensing with signals that have a certain
0:02:37which is i set is this um just structure with not
0:02:42um which is the following
0:02:44um if you look at the
0:02:52so if you look at you know the signal here that the conventional assumption is that you know the signals
0:02:57that one does that one minimisation on are uniformly sparse
0:03:01but there are many applications one can think of for example in the N a micro is if you know
0:03:05something about to a
0:03:07the gene expression are so of what you looking at a
0:03:10or other examples um
0:03:12that i've mentioned your some network problem
0:03:15uh sometimes you do compressed sensing iteratively and so you have prior information or you know there people have done
0:03:21pressed sensing in conjunction
0:03:23like all filters when you have
0:03:28you know time variations and on so many cases you might actually know all a lot more about you know
0:03:33what the sparsity structure is
0:03:35and so in particular what will assume here is that you know your signal you might be able to break
0:03:40up and to channels
0:03:42and you might know this chunk
0:03:43less sparse
0:03:44and that chunk is more again you don't know where the
0:03:47zeros and ones are
0:03:49entries trees are
0:03:50but you may have prior information
0:03:53okay and so a actual thing to do um
0:03:56if you have say
0:03:59a collection of T partition
0:04:04which partition i guess the ambient dimension into T disjoint sets
0:04:08um in each partition might you know have a different sparsity a natural thing to do if you want to
0:04:13stay within L one optimization is just the way
0:04:18partition with a different way
0:04:20so this notation means that this is all X is that have support on partition
0:04:25set aside in this particular
0:04:28and i'm adding up the one norm weighted to buy particular double so this a different weight
0:04:33for each of the set
0:04:35a part ish
0:04:36okay so we we do a weighted L one
0:04:41um and so the problem setting think that i wanna look at so we can do some analysis
0:04:46is that a less you on that we know either you know and uh all here it's mentioned deterministic leap
0:04:52but this also probabilistic so
0:04:54you might to see "'em" that the fraction of nonzero entries
0:04:58in each
0:04:59set set S i of the partition to be some point
0:05:02which you know
0:05:04a that would be kind of a deterministic assumption all the analysis um going to in the results i'm going
0:05:10extend to the case where this is actually probability
0:05:13so what that means is that each
0:05:15and tree
0:05:16um in this particular set
0:05:19is nonzero probability P
0:05:22that would be a
0:05:24you will
0:05:25a stochastic care
0:05:26session but as as the results for
0:05:28okay and so we assume knowledge both of where these
0:05:31sets are and what the probability of
0:05:34them being nonzero what that
0:05:35a portion of
0:05:36a nonzero
0:05:39um again
0:05:41the aim here is to minimize the number of measurements
0:05:44that we need to recover
0:05:46it's so the question is given knowledge of the peace and S
0:05:50how should we choose these weights
0:05:52to recover X from the fewest number of measure
0:05:54so how can be map P and asked to do
0:05:59so people have looked at this there's this prior or work that is
0:06:03a work of us one
0:06:04a low uh
0:06:05think of modified
0:06:08i where they kind of look at this problem using a right P type results
0:06:12um there is an earlier
0:06:14per of hours uh i mean as
0:06:16may main off
0:06:18where we actually answer this question
0:06:20um exactly if you were using grass
0:06:23angle met
0:06:24so we can actually
0:06:26essentially if you choose a particular weights we can compute
0:06:30what a threshold uh in terms of the number of measure
0:06:33you need to recover
0:06:36um it's a very
0:06:38a detailed analysis you know uh
0:06:40we can you know do things
0:06:42more or less if you have two sets in your partition but once it goes beyond two to three or
0:06:48it becomes
0:06:51a you can do it
0:06:52i wouldn't ever right
0:06:54um and so the goal of this paper really was
0:06:58a um some how to give some insight to out to come up
0:07:02a can so what is the approach
0:07:04um so we as well as you on that the measurements are go
0:07:08this allows us to push to some
0:07:10uh and i alice
0:07:12and so rather than go to this class can angle stuff we we employ other technique it was introduced
0:07:17by rack
0:07:18the a and myself to look at right
0:07:20as a or
0:07:22um it's an approximation
0:07:24well not an approximation of
0:07:26it's not a type around it
0:07:30and not an upper bound if you will and we use that to
0:07:35and so the interesting thing is that we we end up with the very simple uh result essentially the weight
0:07:41for each set
0:07:42a one mine
0:07:44a probability of being nonzero
0:07:48so intuitive this makes sense because we're punishing these sparse or
0:07:53you will set
0:07:54a sparse you are
0:07:56the the larger the weight it is
0:07:58so we're can lies think you know actually
0:08:01the the cost function
0:08:04as we probably should
0:08:06um for those
0:08:08um so it's very simple thing that one can use an show you results of this and of course
0:08:13the the drawback is that this is suboptimal we can claim
0:08:18the awful thing
0:08:22um so what is the strategy to to recover this result what we first look and find a condition for
0:08:27covering signals when you do weighted
0:08:31L one optimization and the time
0:08:36this condition and so for those of you are familiar with null space condition
0:08:41for recovering um signals with L one up
0:08:44as a in the weighted case you get a very
0:08:47similar results
0:08:48except that you know the weights now play a role and so it turns out that you can recover a
0:08:53signal and
0:08:55and uh if and only if
0:08:56for all vector
0:08:58in the null space of your measurement make
0:09:00following following inequality hold
0:09:02um this is the sum
0:09:04over the you know space and trees
0:09:07so assuming the the signal has
0:09:09or case
0:09:10he's on
0:09:11intersection i guess of the S size
0:09:13and the complement of K
0:09:15um and this is over the set
0:09:17the difference you
0:09:23but in any event this is an inequality that should hold for every the the null space
0:09:28and that's why
0:09:29cool to analyse
0:09:34and so
0:09:35uh what we've done is we replace this with a simple condition
0:09:39which one
0:09:42and that's the following things so that one to T we have to guarantee
0:09:46to be positive for all W use in the null space of a
0:09:50um can be replaced by this quantity
0:09:53which no longer an as the in it and if this is
0:09:58it's it's actually a
0:09:59a lower bound on this
0:10:01it's lower bound with high probability on a
0:10:03so almost
0:10:04any any you choose
0:10:06um this will be a lower bound on
0:10:09um and the good thing about this is that you know um
0:10:13there no randomness in it it depends on the weights W depends on these are our which are be
0:10:19fractions of these sets relative to the ambient dimension it also depends on you know which is the
0:10:25ratio between the measurements
0:10:30so once you have a this new note easy so that you want this be positive and an to make
0:10:35this part
0:10:35probably want the maximise so
0:10:40what will do in a moment but you know for those of your into
0:10:43in know
0:10:44a paper but
0:10:46based on some results of court on um
0:10:50a a and actually invoking some lip should
0:10:57uh of of of uh
0:11:01once you really that then it turns out it's easy to optimize over W and what happens as we get
0:11:06the result
0:11:07the i mentioned earlier
0:11:08and what's interesting about the result is that it depends only on the probability P doesn't
0:11:13and on side
0:11:18um um
0:11:19a few other things that i can mention again this is all approximate so if you believe these approximation
0:11:25then i can look at this quantity are which is the dimensionality reduction
0:11:31um in terms of recovering my signal so i'm look yeah dimension minus number of measurements i need to recover
0:11:37however it
0:11:37for regular L one minimisation in the context that we have
0:11:41the problem
0:11:43T and the al
0:11:44being size
0:11:46this is how much dimensionality reduction we get
0:11:49for the weighted L one when you choose
0:11:52these where
0:11:53uh this is what you get
0:11:55convexity of a
0:11:56some of things where
0:12:01um it's clear
0:12:03you you get more
0:12:09so this is just to give some in
0:12:11that's all
0:12:12is optimal
0:12:16uh you can look at um
0:12:19i guess
0:12:21this ratio so how much improvement you get
0:12:26these are different
0:12:27as i
0:12:28a detail
0:12:29and it on this scenario now
0:12:34um um
0:12:35here's another part i want to show as i mentioned in an earlier paper we
0:12:39actually actually to this class when angle stuff can exactly
0:12:42compute the W so that's look at a scenario your
0:12:45um so this is a scenario where
0:12:47we have i guess to that's i think but that's or equal size and ones said
0:12:52you know a point or
0:12:54sent of everything is nonzero on others
0:12:56point five
0:12:57we need to choose W one
0:12:59um to W you want
0:13:01one i T here or make a a is W to W one
0:13:05and so it any omega it you choose
0:13:09it's a different way to that one up
0:13:10as a you might ask what is the minimum number of measurements a need to recover the
0:13:15and that's what the why
0:13:17so for example if i two
0:13:19and one optimization that U W Z equal
0:13:22and i ni
0:13:27um um
0:13:32a point fifty five yeah
0:13:35where is a by use the a are about which you get from
0:13:38computing this for each
0:13:40curve requires a grass mind or a compression each point on or
0:13:44you get something around really and some improvement
0:13:47uh this is another example
0:13:52uh you are
0:13:55if you use
0:13:56the form of that we derive your which
0:14:00the ratio should use the following in this example it's point nine five
0:14:05and one
0:14:07here and you know that
0:14:09um so this is one point five maybe it's a
0:14:11a off the optimal which
0:14:13i two and three
0:14:14but in terms of how much you lose on the measurements
0:14:18point five
0:14:26so it
0:14:26actually a
0:14:30close to
0:14:34and alice
0:14:34switch you can
0:14:35extend as i said you um
0:14:37two sets were
0:14:41um here again some simulation results of this is the signal
0:14:45um where i is you know
0:14:48so it's a different model of assume here that the signal
0:14:52i'm a
0:14:57whatever whatever you you use so this
0:14:58signal i'm assuming an of that's probably T for each
0:15:01and be non zero and this probably
0:15:06i you i one optimization a signal with
0:15:11and you
0:15:15if i break it into two channel
0:15:18and you a way with the or weighting that we describe really only for each of these two then i
0:15:23get the right
0:15:25break for john like a night
0:15:28and so this sure that you know even though we're not be
0:15:33a small you're even going for
0:15:34one one two show
0:15:43and the gains get less and less
0:15:50i'm probably short on time i you know i could said something about right minimisation but
0:15:56yeah that pretty much everything that i mentioned
0:15:59um can apply two
0:16:01a a nuclear norm
0:16:07minimization in this
0:16:08should i know your math
0:16:10is not your where you nuclear norm minimization so
0:16:16linear constraints
0:16:17you can do a similar thing if you have an idea of
0:16:20where you think your um
0:16:23you know so you know looking for a low right mate
0:16:25you have an idea of where maybe
0:16:27the subspace spaces that these things lie what the probabilities are way problem
0:16:33you know look at a weighted
0:16:34um nuclear norm minimization
0:16:39through it there's an analysis
0:16:40a very similar and you get a most
0:16:43a little more involved almost identical as O
0:16:46in terms of how to come up with the your
0:16:49is i said the details are are are are more in the paper and as i said again
0:16:52the the the the message is very simple
0:16:56for the weighted
0:17:02for the way to problem this is a way
0:17:05as this it doesn't depend on how many
0:17:07sets we have a what the set sizes or
0:17:14that we have
0:17:34i i
0:17:35i i i don't think so i as um you know if if you estimate a little that all
0:17:40you know where the boundaries are means you'll be a little that often terms
0:17:45set a say that you know
0:17:47but it means you're often
0:17:50and it doesn't seem to be a a whole you know i i should show
0:17:54you could already see here
0:17:57you know
0:17:58it's not a sense
0:18:01a is are of a little bit
0:18:03um this for you know
0:18:05even though you're you're your relative weights might change but both of them as long as you're not too close
0:18:11to the a one
0:18:15um but i i i haven't done analysis but in terms what we see in and i up there are
0:18:19more plots than these that we
0:18:21that but today
0:18:37so we we have a look at is you know
0:18:39when we been doing
0:18:41a it's right
0:18:44and suppose you have a signal that
0:18:46sparsity beyond on say a traditional one
0:18:51so you can do it out one optimization
0:18:53you'll get something that's not
0:18:57if you look at the larger
0:19:01and you can rig or this
0:19:03um it turns out that
0:19:05where the larger coefficients are there is a better chance of those are actually a nonzero ones and where you're
0:19:10at smaller coefficients a better chance
0:19:13so you can use that as your prior
0:19:16i way
0:19:18and you can
0:19:19um so there are
0:19:21situations like this
0:19:22again you know uh when you have time variations of you have something like a time series that
0:19:27you know
0:19:27sparse in time
0:19:29um you can always use your prior estimate
0:19:33to give