Speech Transcript - GENERALIZED RESTRICTED ISOMETRY PROPERTY FOR ALPHA-STABLE RANDOM PROJECTIONS

0:00:14	they don't uh
0:00:16	uh
0:00:16	and
0:00:20	i
0:00:22	then you are there
0:00:25	oh
0:00:27	i
0:00:30	right and see
0:00:31	uh you know
0:00:33	i
0:00:34	be overwhelming majority work
0:00:36	has has a a they'll with construct a matrix
0:00:39	that are sub gaussian
0:00:41	it's are made are gaussian
0:00:44	or or
0:00:45	a a binary and in some some fashion or or or or partial
0:00:48	uh
0:00:49	for matrix
0:00:50	and and the like
0:00:52	so that special export here
0:00:54	is uh
0:00:56	thank you
0:00:57	so the but the the question away
0:01:00	is what happens if that the the
0:01:03	matrices that we using compressive sensing
0:01:05	uh are not so cows
0:01:07	and there some uh uh interesting a statistical and and uh a geometrical characteristics that but
0:01:13	it will in march out of of a of of those uh
0:01:16	prop
0:01:17	so we will
0:01:19	the first point we will motivate the we will uh
0:01:21	some right of characteristics when these matrices are are not so gaussian
0:01:25	uh we will talk about stable run process that are to one class of four
0:01:30	or for all variables that are are not sub gaussian in the uh we'll will go for some
0:01:35	uh rap
0:01:36	equivalent characteristics of a piece of compressive measurements
0:01:40	and show some computer simulation
0:01:44	um
0:01:46	so in compressive sensing the uh
0:01:48	fundamental property the alright you the right
0:01:51	uh
0:01:52	uh
0:01:53	shows how these dimensional reduction that is achieved when you look
0:01:56	pressure
0:01:57	upper side information in space
0:01:59	right in there and several people in this uh
0:02:02	so i should have talked about uh information per server
0:02:06	uh_huh
0:02:06	the different space
0:02:08	and uh technical sub gaussian the uh measurements you got you have these uh
0:02:13	i some a three
0:02:14	you have the a some entry
0:02:17	let you go from
0:02:18	uh the L two space
0:02:19	and when you of the projections you're are you have it's as a matter of preservation on L to specs
0:02:24	as well
0:02:25	um
0:02:26	but i has to be uh
0:02:28	gaussian or
0:02:29	or something like that
0:02:32	uh
0:02:34	a chart tried of and the calling of is uh a generalized this idea to say okay well
0:02:40	uh how modified look at this as a sum to still on the L two based but i could the
0:02:44	regularization right
0:02:46	in an L P
0:02:47	and uh you could uh
0:02:51	get that
0:02:52	more sparse characteristics and in the in in this just
0:02:56	so using this this came right yeah what we will do is we will uh generalise it
0:03:00	to apply to a um
0:03:02	compressive scenario
0:03:04	where R is no longer
0:03:06	so gaussian in in in fact be a very
0:03:09	uh i'm whole save or are rich wrote a novel impulsive also characteristics
0:03:13	it will will show that the use somewhat tree that is preserved here is uh and that a L to
0:03:17	space it's and
0:03:18	um
0:03:20	and uh and L P space L L P uh metric
0:03:23	going to uh and L L from metric and these are very well
0:03:27	very distinctly
0:03:29	related
0:03:31	uh key will be less less in L two
0:03:35	that's a correct
0:03:36	so of
0:03:36	and to uh can go from one to two
0:03:40	um and and a stable distributions uh
0:03:43	how have determines the uh uh
0:03:45	the level of the degree of um that
0:03:48	gaussian at
0:03:49	if you will
0:03:49	uh to meaning gaussian uh um
0:03:52	and the
0:03:53	the lower the out of the more impulsive characteristics you will have a
0:03:56	and of course the that the ripple also give you
0:03:59	at uh uh
0:04:00	probability of of reconstruction and also a number of measurements
0:04:03	you need
0:04:05	i
0:04:11	yes
0:04:11	well it's of this
0:04:14	a i i a more
0:04:17	now this this is the geometric interpretation
0:04:19	um
0:04:21	um
0:04:23	in a
0:04:23	in compressive sensing typically
0:04:26	you have a uh that the L two
0:04:28	is uh
0:04:29	if you have the L two distance in uh in the original space you are going to preserve these
0:04:34	L two distance in the in the project space
0:04:37	uh in in in a
0:04:38	i in the image on a reduction actual literature uh
0:04:42	there's a lot of interest in doing that this the mitchell i reduction
0:04:45	in uh uh uh north that are not L two
0:04:48	uh maybe the L one
0:04:50	that that out maybe more uh a truck before the application
0:04:54	and B for the image processing literature
0:04:56	is well known that the L two um norms based consider are are very and you may wanna go to
0:05:01	other other more
0:05:04	so that was a motivation here you know can we get
0:05:06	a other uh L two distance preservation in this in in this compress sense
0:05:11	so in this case for instance of were talking of the L one norm here how i how maybe preserving
0:05:16	in that the projections on the and this L P more
0:05:21	and the associate with this the main char with action then you will have the uh
0:05:26	a or the restricted isometry property
0:05:29	on the reconstruction you would like to get the
0:05:31	construction back
0:05:33	so uh the that two to the result that we will look at two is basically this result here which
0:05:38	is
0:05:39	in since a uh
0:05:40	there similar to the traditional additional right P
0:05:43	when set the L two norm few we're gonna have the L L P
0:05:46	a P more
0:05:49	so what are the what are the things that
0:05:51	this will
0:05:52	will uh will get gain if you use this uh
0:05:55	projection rather than that are not to a L C
0:05:59	uh
0:06:00	one is a you will preserve distances in in space is are not L L two
0:06:04	uh but there's also the properties that are interest
0:06:07	um
0:06:08	uh we know when you pray when you process data with that
0:06:13	uh a more that are lower than L two but the processing a lot is a lot more robust so
0:06:18	that's form dress as one of the parks of what's
0:06:20	given here by or real and bar
0:06:22	that if you have a is in your in your observations that are not
0:06:26	uh gaussian
0:06:27	then you were uh a reconstruction gonna be much more robust than what you would get with
0:06:33	can in projection
0:06:35	uh you use L P therefore you you per are more the sparsity of the reconstruction
0:06:40	and but um as i said that that the
0:06:43	but distant reservation is is a different
0:06:45	or space
0:06:48	okay so in in a stable when we talk about a a stay uh a sub gaussian projections what is
0:06:53	key is that
0:06:54	if you print if you're generating a round on uh make trick
0:06:58	rather than having a a a a uh the entries in B of a gaussian distribution they're gonna be an
0:07:03	alpha stable distribution
0:07:04	which uh have pales we're than than the gaussian so for instance here
0:07:09	the uh as you change the parameter uh i'll cycle two with this this black
0:07:14	of which is the gaussian
0:07:15	if you have a a a a a i'll think with one point five is gonna be used blue curve
0:07:18	and so on so as as you lower the L are you gonna have a have your heavy tails
0:07:22	uh to generate that that the projection matrix
0:07:26	um
0:07:27	be a characteristic function of all stable the distributions have a this have the shape
0:07:32	uh is
0:07:33	a class of uh uh density functions of distributions
0:07:37	uh a characteristic function is very well to if is very compact very nice but that dish regions are not
0:07:43	that's very interesting class
0:07:46	um here the out that if you put of equal to two that's a characteristic function of a gaussian
0:07:50	so in general this is the easiest way to
0:07:52	cracked tries that the of or stable distribution
0:07:56	and i think that's very interesting that with the stable distributions it it has a a a a stability property
0:08:01	much like the gaussian has a a is gaussian central in your
0:08:06	uh stable distribution have a a generalized central
0:08:09	limit your
0:08:10	or or stable wall you will
0:08:12	and it's that that it it's interesting because if you have a
0:08:15	um
0:08:16	uh
0:08:17	let this are
0:08:19	be a stable distributions you stable distribution with some
0:08:23	that
0:08:24	this this this this five i'll of uh in this fight
0:08:27	this partial and so you don't have the the if you have person
0:08:31	uh if you have a a a bunch of them uh
0:08:33	the output what also be stable of the same
0:08:37	parameter alpha
0:08:38	and but of this portion will be and and so like an L P
0:08:42	uh
0:08:44	a metric of of the dispersion
0:08:47	right so
0:08:48	uh for instance if the it if all of these have a a a a uh this person one
0:08:52	and you are and you out all of this the N
0:08:54	the the output the why
0:08:56	which is the sum of all of these will be um
0:08:59	a of the E the L A of a more of four
0:09:02	of of of the data
0:09:04	so that was partial power captures the that the of
0:09:06	the other or
0:09:10	um
0:09:12	it is an example what you have a a a cat can data if you do the cal you random
0:09:16	the projections in
0:09:17	the output will be that cal she with that of the L one this
0:09:22	this is a special case of
0:09:24	i is stable distribution
0:09:28	okay um
0:09:30	so when you tack of a stable distribution since are heavy tails
0:09:33	uh you can use second or or or second order moments are second or statistic because they're very heavy tails
0:09:39	and the means and variances are that where will find so what you have to use
0:09:44	is you have to have
0:09:45	what you have to use you have to uh use fractional uh mode
0:09:50	so
0:09:51	uh if if uh X is a uh
0:09:53	stable distribution
0:09:55	then the expected value of X to the P so that X of the P
0:09:58	has uh
0:10:01	you compute the the
0:10:02	the moments
0:10:03	then you will this will be related to the dispersion the P
0:10:07	and uh therefore if you have
0:10:09	the L P more
0:10:11	oh of these this is a of the sum of a a lot of these terms
0:10:14	then the expected value of that the they'll P then it'll be another constant that term
0:10:19	a variable P and alpha
0:10:20	in L so the dispersion of the of the very
0:10:24	so this can be used in order to do the analysis that we need for the
0:10:28	for the uh are i P that would will go to
0:10:32	so this is a a that they are we were gonna we gonna look for is uh we're gonna have
0:10:37	a
0:10:37	run the matrix that again but like you generate
0:10:40	uh
0:10:41	compressive random the to see that are gaussian that we gonna be generating
0:10:45	i got
0:10:46	matrices was is that are of the stable
0:10:48	i at uh with out between one and two
0:10:53	and you will
0:10:54	uh a show that if you have a
0:10:56	K A the dimension of is matrix B
0:10:58	well sir it than the mentioned
0:11:00	uh which is as
0:11:02	uh a and of over S a very similar to that
0:11:05	for a traditional are P where is that the sparsity
0:11:08	then this this uh
0:11:10	um distance card to station will be preserved
0:11:13	and with a given problem
0:11:18	a came to do that to prove that we will use this are similar steps as as as we do
0:11:21	in the in the uh traditional are P construction
0:11:25	except that we will be using these other
0:11:28	uh different than for and the uh
0:11:30	uh
0:11:31	fractional moment
0:11:32	and that the procedure is of course to look at the probability probabilistic approach that for a fixed X
0:11:40	in uh that is sparse uh
0:11:42	that the rip hold
0:11:44	then we will look at the uh
0:11:46	that the rip
0:11:47	uh
0:11:48	uh
0:11:49	i
0:11:50	is achieved
0:11:51	for any X in a in our and the S and then for any submatrix of B R are so
0:11:56	it's very similar to be other
0:11:58	or just on the traditional
0:11:59	on the traditional um
0:12:01	alright are P the relations so we will just get
0:12:03	how we do this
0:12:06	um so the first lemma tell so that if you have the index of uh
0:12:11	uh
0:12:12	S being the sparsity
0:12:14	and uh oh we're we're looking at
0:12:17	this uh be a submatrix of K by ace
0:12:20	uh of these uh projection matrix
0:12:23	then uh this will hold this this will whole whole these are are some constants that we will derive
0:12:28	in in a wheel
0:12:29	with this will hold with a given probability
0:12:33	and uh
0:12:34	the problem that is is uh are related to the to them up the fractional moments we went uh
0:12:39	we just discussed uh
0:12:41	a minute ago
0:12:42	we you have a i is equal to the projection major
0:12:46	each of the interest of these why will be the linear combination of the X with the stable
0:12:52	components
0:12:53	therefore for this uh a random variable Y to inter a projection will be alpha stable with a zero mean
0:12:59	but the
0:13:00	dispersion of uh
0:13:02	yeah uh the the L L
0:13:05	right the
0:13:06	uh the L P L of the of Y
0:13:09	then is
0:13:11	um
0:13:12	we know that by this somewhere where you have each of these is the i is uh
0:13:16	is given there
0:13:18	so one um
0:13:19	this is just a that the sum of this
0:13:22	elements of of the why way of the of the people are
0:13:26	and that you can then take the expected value of of the projection
0:13:31	which um is just uh
0:13:34	again it's a this are
0:13:36	uh
0:13:36	the P uh
0:13:38	uh
0:13:39	the the the out of an a normal of the of of of the back
0:13:46	oh so we have a then is is we have the expected value of and then we have the variance
0:13:52	in in the variance you can
0:13:53	similarly divide there so you have a you have the mean and you have a variance and you trying to
0:13:57	get this bound
0:13:58	in order to detect the probabilities that
0:14:00	that that the distance
0:14:01	as will be preserved in that this
0:14:05	um um
0:14:07	then if you approximate of the distribution of of of these uh P more by an inverse gaussian
0:14:14	then you will have a a of by bound that you can then relate how likely use
0:14:19	how like there these distances to be in that in that in a given "'em" ball if you will
0:14:25	in that will be a function
0:14:26	well this parameter a to we'd be parameter at the the distribution of these me are
0:14:30	and signal that we just
0:14:32	review in the previous slide
0:14:34	and the
0:14:35	but
0:14:35	the turn of band provides as that probability um
0:14:39	which uh will be a function of the K right
0:14:42	that will tell you for a given probably that i i'm within the ball and need so many projections
0:14:46	the
0:14:47	on the uh set
0:14:50	the
0:14:50	but on the compressive sensing measure
0:14:55	so a uh
0:14:56	we then general that not just for a given X but for any arbitrary X that could but that preserves
0:15:02	that uh it'll P norm
0:15:04	in that does just changes this probability
0:15:06	you just have to be a little more
0:15:08	i don't the on the
0:15:10	uh
0:15:11	on the distances in then
0:15:13	for any submatrix
0:15:14	i you just change also the
0:15:15	but
0:15:16	the constants that
0:15:18	an N to prove the that the or and then you just have to
0:15:21	uh
0:15:22	many P like the constants to put in to this form
0:15:25	which is what we you what will do
0:15:28	but in in and at the same time that in says the minimum number of measurements
0:15:32	to it's to attain the rip which is again uh
0:15:35	a function of these S slot and
0:15:40	so this is an example what happens if you can if you if you um
0:15:44	if you do these projections so you have the the shall reduction you you have this matrices that satisfy this
0:15:50	is the this reason
0:15:52	uh and then you can do the reconstruction that only just mitchell to but you wanna to the reconstruction
0:15:58	but when you do the be a a reconstruction
0:16:01	you're project thing with this uh
0:16:03	not some gaussian sub gaussian entries
0:16:06	in therefore for you can not use traditional compressive sensing algorithms
0:16:10	uh like the L two a one or or uh
0:16:14	methods that are rely on and to uh
0:16:16	distance distances
0:16:19	um point of the greedy out within
0:16:21	to is you really with ends would fail
0:16:23	uh because of the impulsive nature of that the measure
0:16:27	so in this uh in this uh example uh oh we're gonna we getting um compressive measurements Y
0:16:33	where are are are the alpha stable uh projections
0:16:37	without equal to one point two
0:16:39	uh well the noise is one
0:16:41	what one point two and um
0:16:45	and
0:16:46	then you have this is a density function
0:16:49	a number of measurements is four hundred K is the number measurements
0:16:53	S is the sparsity
0:16:54	and
0:16:55	this is a uh uh um reconstruction algorithms that
0:16:59	are not develop in this paper but in different paper that uses
0:17:02	uh
0:17:02	uh not L two
0:17:04	data fitting uh
0:17:07	uh terms uh but uses a a um
0:17:11	uh i L L lorentzian regular say
0:17:14	a lorentzian based metrics to do the the
0:17:17	the data fit
0:17:19	then you can see that the the data that is the original or the circles blue circles
0:17:24	bin them cover data is is
0:17:26	is well preserved
0:17:28	if you the L one a is you will week
0:17:30	we curve or we cover the sparsity terms
0:17:33	you will have a lot of a ears uh
0:17:35	it's star
0:17:38	and then you can do that and you can
0:17:40	test the
0:17:42	um
0:17:43	the number of uh measurements that the you require and
0:17:46	again for these method we have
0:17:48	a the medical uh K that you need to to fit the in this construction you you were able to
0:17:54	uh do the inversion
0:17:56	uh
0:17:57	in a within the bounds of
0:17:59	the tip that they L C
0:18:02	so in summary O
0:18:04	what uh
0:18:05	what if you use uh
0:18:06	if you don't use of gaussian
0:18:08	a measurement
0:18:10	uh we we explore that you can get a a a uh this is trees trees or these distances in
0:18:15	a in a not an end to but another another other uh
0:18:20	norms or
0:18:22	and uh uh at the same time you will you will find that the they're more last
0:18:27	you have a lot more robust
0:18:28	against noise that very close it
0:18:30	and uh uh also we use you yeah
0:18:33	the
0:18:33	sparsity inducing a a a more that but you want for
0:18:40	question
0:18:53	i
0:19:06	well you're
0:19:07	what you're but your uh
0:19:09	you're using your use in the journal bounds on the L
0:19:13	on that uh
0:19:13	uh
0:19:15	fractional
0:19:16	uh tire
0:19:17	so you're doing
0:19:18	the close to the
0:19:19	P
0:19:20	so or you can use a
0:19:21	approximations matt not couch in that
0:19:24	right him where you can put inverse gaussian or other channel out some of that is true
0:19:28	a well the a
0:19:34	sure because you do your use using those on the on the L P type
0:19:38	uh very
0:19:41	he is uh
0:19:42	yes
0:19:43	yes
0:19:50	yeah yes
0:20:13	yeah what happens is a um
0:20:17	you generate you generate your your matrices using a stable distribution right so you have
0:20:22	some that is not gaussian you generate the projections for you gonna get a vector of measurements
0:20:27	but these measurements are are are
0:20:30	linear combination alpha stable distributions so they're not
0:20:34	uh they're not so gaussian than i gauss
0:20:36	right
0:20:36	so the inverse a algorithms can use traditional uh L two
0:20:42	uh data fitting terms
0:20:44	with the regular right so you have to use norms that are robust you have to use norms
0:20:49	perhaps like the ones they what they were
0:20:50	mentioned the
0:20:52	later or earlier
0:20:53	but are are one or or a more robust and you're of
0:20:56	so in this case
0:20:58	uh this illustrates that if you if you norms of data fitting that are
0:21:02	are there are more robust like the L L the or in that was uh
0:21:18	yes yes uh
0:21:19	yes that that will be that will double will you will get a good result if you do yes
0:21:24	within that the in the algorithm the that we use as a lorentzian type
0:21:28	but we could that derive an algorithm that uses and an L
0:21:31	a people less than
0:21:43	i
0:21:44	i
0:21:45	yeah well the L one is the approximation for the for the right
0:21:55	um
0:21:57	i we have really run run that experiment because are to turn right there there's the data fitting "'em" which
0:22:02	is the that one that you were used
0:22:04	put a zero point six
0:22:06	in and there's the sparsity term which
0:22:07	could be the L zero
0:22:09	even the L one
0:22:10	right so if if you if you if you can but without of them that was the and the data
0:22:14	fitting normal zero point six and use the L zero we a very good
0:22:18	or or L
0:22:19	so point six of than then one maybe
0:22:22	fine
0:22:23	but he these odd with them the you we try
0:22:25	was one that was somewhat to double that that we could go down
0:22:29	to that as as was presented with a more in more
0:22:33	uh in this here shows you that if you the the L two
0:22:36	they are fading
0:22:37	you can of the port you gonna get a lot of spurs result because of that
0:22:40	because of the structure of the projection
0:22:42	which is not
0:22:43	some gauss
0:22:53	yes that's a good question um
0:22:55	uh well we explore where the fun that the goal um
0:22:59	characteristics of of such mate
0:23:02	uh a to generate them and how do you uh a user in practise that's that's something to be explored
0:23:07	uh a sort you you could try
0:23:10	uh
0:23:11	for a gaussian mixtures are easy
0:23:13	a very good approximation of of not sub gaussian uh
0:23:17	majors but in general to be in practice you have to to come up that's an open open question
0:23:25	okay thank

GENERALIZED RESTRICTED ISOMETRY PROPERTY FOR ALPHA-STABLE RANDOM PROJECTIONS

Compressed Sensing: Theory and Methods

Presented by: Gonzalo R. Arce, Author(s): Daniel Otero, Gonzalo R. Arce, University of Delaware, Colombia