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