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

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

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

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

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

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