Přepis řeči - SPARSE SPECTRAL FACTORIZATION: UNICITY AND RECONSTRUCTION ALGORITHMS

0:00:13	a
0:00:21	i
0:00:29	that's doesn't
0:00:30	a uh as i would like to apologise for in
0:00:34	but do you a low for not be here but the and the
0:00:36	problems coming here today
0:00:38	i your in the and work in the same subject and in a file
0:00:41	a to with much but the and
0:00:43	also so with the U
0:00:45	and uh in this talk okay we will uh
0:00:47	present the some results about
0:00:49	a classical problem problems speced of that addition
0:00:52	and look at the problem uh looking at that vacation and seen that there is a sparse a
0:00:57	the prior available
0:00:58	and we learn a lot of the problem of sparse like the position
0:01:01	we we present some sufficient condition
0:01:04	which allows us to know that the solution is unique
0:01:07	we prove use the would be we i would it would be give a sketch of the proof
0:01:10	and we present our reconstruction algorithm which works we really well
0:01:16	or or or that the position is we one known problem
0:01:19	where are we want to
0:01:21	we want to
0:01:23	uh uh recover a signal X of and no not from a control version of it the but using the
0:01:27	autocorrelation function
0:01:29	which is a convolution between the signal and its time for
0:01:32	we in the same problem in that the main where we have a a you to let this indicates a
0:01:37	for this form
0:01:38	where we have that the correlation function and therefore we have described also value of that well correlation
0:01:43	oh a of the signal
0:01:44	if to a cover the phase information from this uh
0:01:48	um um an information
0:01:49	we can sum or role
0:01:52	is is not really a only my mother got all in there are an application in which this problem is
0:01:55	a a real haven't
0:01:57	first of all of this bunch channel estimation if you have a channel H of fan
0:02:00	uh which is a no we would like to get
0:02:03	uh the closest response in order to improve the communication over channel
0:02:07	and we can only some me data for the input X and and measure the output
0:02:11	if we sum me white noise in the channel using the filter a a we know that
0:02:15	they so uh that what is gonna be that
0:02:17	absolute value of the uh with the of the channel
0:02:20	therefore
0:02:22	if if a cover the face C we got a of the impulse response of the channel
0:02:26	and the problem so
0:02:28	and of the five is a problem or rising up text
0:02:30	and then it back to got we are it as the next expect a lot of E
0:02:34	if where where we have a an cool and want them this and the fact that the shape because the
0:02:38	shape
0:02:39	yeah the term and the time means the function in biology most of the most cases
0:02:43	then for with that been i the monocle and putting it into a crystal a a we that and we
0:02:47	put the quickly a an X ray B
0:02:50	what we measure what we can measure that the faction that of the crystal which by the backs slow it's
0:02:54	that have with us from of the crystal
0:02:57	but the probably as that
0:02:58	if you we if we use for the rest a for the feel more C C D's
0:03:02	we can only measure think this of the light and therefore we lose the "'cause" information if we the domain
0:03:06	and if we can recover the fees we can also recover them
0:03:11	and
0:03:11	uh they original money
0:03:15	yeah a a result is really come on in uh which is a a really one no it's its a
0:03:20	uh this fact that that the addition that the same
0:03:22	we have a the correlation function that the main
0:03:24	uh we've tried to find the remotes and does that the main using for addition
0:03:28	but the problem is uh a how to assign each got or fruits so between the but inside and outside
0:03:33	the unit equal to the signal X of that
0:03:36	here since we assume the signal X of that to be a real their roots up using incredible
0:03:41	if we are aware that our signal is a a i mean phase is a we we can take just
0:03:45	the roots it's set of the unit to call
0:03:47	and we are sure that that of destruction is gonna be unique
0:03:50	is a good solution
0:03:53	otherwise if we don't have this prior about minimum phase a
0:03:56	we can't we have just to
0:03:57	try all the possible combination between inside and outside roots
0:04:00	you know to find our possible solution and therefore for is a common or number of possible solution
0:04:05	and uh there are known all algorithms to find a good so uh the resolution
0:04:10	what we can say that since the the tool because which we are interested rest have a sparse prior because
0:04:15	channel else usually can be modelled using multi about
0:04:19	fading channels which are sparse in the for the main
0:04:22	and also i them sink with still lower
0:04:23	results are sparse because the model just you want to so that is that is a complete
0:04:28	and the for and interesting to understand
0:04:30	which implies that sparsity in that
0:04:32	uh
0:04:34	reconstruction construction up to the an extension of the solution of the set of the vision problem
0:04:38	and moreover if we can say something about the you a be
0:04:41	because without
0:04:42	uh mean of a solution the number of solutions can or you want to avoid this situation
0:04:47	a a small hint about why spice D can be helpful can be here from these example when we have
0:04:51	a sparse signal
0:04:52	made of for example you have four components out of them
0:04:55	and we
0:04:57	a good the that the main and we embarked the route with the respect you
0:05:00	root outside only so that the sink was not a room
0:05:03	what that is that most likely if you try to you the month of a image that the uh
0:05:08	signal is not a more sparse that for that is a strong correlation to is a sparsity
0:05:12	and uh yeah yeah
0:05:14	and the remote in that the main
0:05:17	is also a negative to result that is a a a really one know where if we have to uh
0:05:21	a signal which are are a sparse signal
0:05:23	therefore for all the components are you from these that from each other
0:05:26	if if should down sampled sequence C K and D K
0:05:29	and the same old correlation function also that room
0:05:32	signal X N and Y and have the same at or some function and the for we know that the
0:05:36	solutions of taken a more
0:05:39	in this paper we present a a a a to look a a a a a a the which stays
0:05:43	that up to you condition sufficient condition the construction an unique
0:05:48	and when we are a far the term unique a clearly we talk about a make up the sign change
0:05:52	of a a a a a no shift
0:05:54	at time reversal because this information are completely hidden than to the phase information the for one with the face
0:05:59	is lost
0:06:00	we can recover anymore
0:06:03	and this to condition are
0:06:04	the following one the first or first the support of the autocorrelation correlation function
0:06:09	that's a so we have a signal X which a discrete and real often said before
0:06:13	and it may have that for a likely combination of the amplitudes of the signal X and
0:06:17	we use the coefficient in that course of function
0:06:20	which for as the it's
0:06:21	uh a some information
0:06:23	we want them like that in order to describe is mathematically we take that
0:06:27	and to get a function of the support of X and
0:06:30	and we check that or some function uh indicator function
0:06:33	it that of support
0:06:34	of the
0:06:35	to of course some function at the same
0:06:37	the condition one is satisfied
0:06:39	in are all the support function of a of a and is a a a small or or equal to
0:06:43	this
0:06:45	this condition is not really started all
0:06:46	because if you pick out to the weeks N which are normal is to boot the uniform is to board
0:06:50	all these to put in a nice way
0:06:52	it the was usually uh would probably probability one
0:06:55	the second condition or a first to uh from a but which is used in the
0:07:00	right extraction and that proof of the in city
0:07:02	and it's and in this way where we have a a a a and by M yeah a matrix
0:07:06	and we choose the columns uh in a particular way
0:07:10	we take the support of that core function is still that
0:07:12	and we on the columns point but this support
0:07:16	from this support to be build this frame a that is a or which is called at
0:07:21	a particle i think we have to this frame is that you want every possible back the which is in
0:07:24	the range of a must be unique to the mine from the that values
0:07:28	this work this condition to as been a third can investigated by but i "'cause" that's and that in in
0:07:33	this in a set of paper regarding a three maybe to the frame extraction from method
0:07:38	and uh they proposals also some algorithms which of this problem but they works only for some particular kind of
0:07:43	meat she's which are really to
0:07:45	this uh a big are we also impose a
0:07:48	not that algorithm little with these general and works for a possible
0:07:51	uh frame
0:07:54	our main result is the following suppose that can one a commission to are
0:07:57	uh us this fight i then for a possible signal
0:08:00	which is supported on the indicator function one and
0:08:03	we can uniquely need the a
0:08:05	signal X N from that course some function
0:08:08	in the following two slide so we give a small a uh sketch of the proof of the theorem
0:08:13	because it allows us to define a a a at the same time a algorithm of construction
0:08:18	and will do starting the finding a a new sequence G M which is in the range of a for
0:08:22	a to we define before
0:08:24	and
0:08:25	we are cool a G M from its up through by it is possible but condition to
0:08:30	and then we saw was more right one problem
0:08:32	which allows us to of being a a a a partial information of the free that's from up so uh
0:08:37	to some feasibility ambiguities
0:08:39	i we so this phase is by alignment
0:08:41	we take the inverse free of just from of the result and the proof is gonna be
0:08:45	in
0:08:46	so we have a
0:08:47	uh the input to lower our thing is that that uh are that's absolute values of the fourier efficient of
0:08:52	and
0:08:53	and we have only their i need to solve this
0:08:55	uh sequence
0:08:58	and initially we define a new sequence G M which is a multiplication of two free coefficient
0:09:02	and K E we don't know this sequence because we don't know that terms what we know the absolute values
0:09:06	of the signal
0:09:08	and we can also prove that this sequence are in this uh are in the same support of the
0:09:12	autocorrelation function and by conditional one also on the support of
0:09:16	and the support S
0:09:18	therefore this vector a is in the range of the frame of uh and that is a operator a
0:09:23	and that condition to we also the a cover this
0:09:25	but is is sick we just the find
0:09:28	a the known pretty C C using a conditions
0:09:33	now with that obtained that that which is the squared absolute value of the for those for which is given
0:09:37	at the beginning of the problem
0:09:38	and then new see C M with the uh phase factor C
0:09:42	we can be a this matrix one for every possible index a
0:09:45	if you factor right this may we can obtain easily to vectors
0:09:49	which are the same and the for these matrix of is a one
0:09:51	and that's a vector or uh the again but or are the our
0:09:55	solution one F and that's and plus one up to a a phase a
0:09:59	X C
0:10:00	since since we D E is uh uh this solution a C D is uh
0:10:04	given that to a phase and B did that them or
0:10:06	for a possible index and we have this phase ambiguity
0:10:10	therefore we have a a and we should is B with D C last
0:10:13	i i that is a big at that time for a possible index M
0:10:16	first a uh before obtaining the solution need to solve these make it is
0:10:20	you close so we take
0:10:22	and a solution for any coefficient that um help put the solution the row and we and then in this
0:10:27	way is is
0:10:28	the solution for the first problem is which of the second problem
0:10:31	and you can see that in this case for example data
0:10:33	uh
0:10:34	uh the double seat signal to that
0:10:37	and therefore we can define a new sequence in which is a line is exploited
0:10:41	and then new segment is F and Q that
0:10:43	where there is only one is um
0:10:46	i'm be D
0:10:47	taking the bus with a some of these uh uh sequence yeah allows us to recover ten
0:10:51	how to the no she does we define in the beginning
0:10:54	while the remaining problem is that yes we know that we can cover from the from operator at that
0:10:59	C C M from them the needed
0:11:01	the problem is that
0:11:03	we don't know how
0:11:04	yeah we propose a algorithm with
0:11:06	this of the probably in a high dimensional space
0:11:08	is i in just is a particle or best space where the problem is a trace of multiplication duplication to
0:11:13	make six
0:11:14	and or to C is we start first from the definition of G M which is a multiplication between the
0:11:19	m-th row of V
0:11:20	and that unknown vector C
0:11:23	if you take the square or so but you of of this a sequence
0:11:26	we obtain that this is a trace of to this is a a and that i am and C
0:11:30	a am is no because is the frame operator we have built and the beginning
0:11:33	why this is a no
0:11:36	and am are to right are matrices
0:11:38	and these are going to the previous definition of the bird space
0:11:41	it's a it's a a set of in recreation
0:11:44	therefore we can have to solve this a a set of your creation
0:11:47	but to be problematic because tended to mean
0:11:50	the for what we can do is that
0:11:52	and we can exploit the fact is a matrix C is a a rank one make
0:11:56	so uh that are them we propose a solve of these is a problem of recovering a a G M
0:12:00	from eight samples was also but use
0:12:02	goes uh as follows
0:12:04	we first project the solution until
0:12:06	that you know a fine space the fine by the set of you know which
0:12:10	and then and we take the estimation of their uh C matrix
0:12:13	uh uh which is a rank one using as D in this case but you can use any possible a
0:12:17	mix of the problem
0:12:20	we you need to make these to process to until convergence
0:12:23	but mean here that proving convergence for a possible signal is not uh we don't have a proof for yet
0:12:28	because this that design of comics
0:12:30	and therefore we are not sure about the correct uh we can prove convergence
0:12:34	but in practice in the signal a to sparse
0:12:37	is uh uh uh uh the calm the i agree that leads to the correct solution
0:12:42	a the last of like to present a small example but we take a signal
0:12:46	and
0:12:47	which is a uh six sparse signal
0:12:50	which is a a which satisfies going to one and two and therefore as unique solution
0:12:54	and we generate the input and correlation sequence and we try to recover
0:12:59	this C know from that for some sequence
0:13:00	this kind of algorithm works in this case that works in the most of the cases
0:13:04	when the sparsity is a a a a at most around ten percent of the
0:13:08	or the uh that and uh length of the signal
0:13:12	so this paper we investigate the problem of spec that put addition from
0:13:16	uh and another point of view
0:13:18	what the our prior is not a mean phase but just sparsity
0:13:21	which is a a a a a a uh
0:13:23	very good prior in our to where we are interested in sparse channels or increased still
0:13:28	a solution in that are is not an eight but including this sparsity prior
0:13:31	we can and if i i uh we can define and you the are which and two sufficient condition for
0:13:36	which we can prove the you of the solution
0:13:38	a and the proof for that you need the a we can also the i've
0:13:41	a a an algorithm which in practice works where well
0:13:44	and at the moment
0:13:46	uh we don't have any come just proves but we're working on
0:13:49	oh
0:14:07	you
0:14:16	have one to down
0:14:20	well was very interesting have spectral factorization rates a city
0:14:25	a a i guess the number of questions might be a one is what do you think is the problem
0:14:29	i you're indicating that is you
0:14:31	i have a less less tasks
0:14:34	signal that your your algorithm is gonna be able to handle at side what one because
0:14:39	uh basically
0:14:41	we had uh doubt question function is not a morse is sparse echo uh as a node of K square
0:14:47	therefore it gets less possible so that's sparse
0:14:50	is also trying to use all the algorithms
0:14:52	one that of course function is almost full use up the problem is because it's really hard to do we
0:14:57	need to five different come
0:14:59	and and it's really hard to the find a good a dish algorithm because these are collected in nature
0:15:04	side of the spec of some problem
0:15:06	the for it's we hard to the it's a five in a proper way
0:15:09	okay can another obvious you is no noise there uh
0:15:12	sound applications where you would have a clean what a correlation function that there are as where you were
0:15:17	a he looked at what happens then
0:15:19	no although the one that we just looking at this quite we had you have a low very case where
0:15:22	you have come signal
0:15:24	because an X the lower fee you have basically
0:15:27	uh can a signal and you measure
0:15:29	when a discrete the because of the been see this show that was crystal
0:15:33	and uh they are you have a also all the problems so as uh i'm using and the gets the
0:15:37	more complicated the or guy you work on this problem but it's not so so for more than
0:15:41	i i trying to rest in and that's and each problem and he is a lot of structural information that's
0:15:46	traditionally used in that hearing yeah
0:15:48	yeah i
0:15:49	and the you probably need to bring in
0:15:51	no yeah but that nobody really use the the by of the sparse
0:15:54	the use different priors
0:15:56	are we believe that to using this possible was problem can you yeah but you can
0:16:00	we we are starting are so different that will are present in was the fee
0:16:04	but for none of the algorithms that are
0:16:06	um um
0:16:07	let's say that are not many proves of convergence of or
0:16:10	uh a good the uh to bit the results
0:16:12	use so the does the
0:16:14	so they just the uh that's a sec the uh working in practise
0:16:18	and for it's really hard to define money course so not or
0:16:22	uh uh what time or what they will i
0:16:24	okay i i i i i'm guessing um
0:16:27	a a lot of the structural constraints that use my have sound
0:16:31	a interpretation
0:16:33	a because you now have certain kinds of my molecules stick together
0:16:36	yeah yeah but that's even for a we are looking more and more that it was more more to the
0:16:40	beginning
0:16:41	i i because a big more close you don't use a standard a lot of can use different techniques like
0:16:46	uh
0:16:47	ask uh a and a a number of the little scattering a you a more complicated techniques so where you
0:16:51	don't have a you know where more information so okay
0:16:54	why if you try to check for uh a model in the model
0:16:56	but keep the model uh i
0:16:59	you would like to use the methods
0:17:00	which i
0:17:01	at the moment is basically a projection that we that mean was of the mean right in the constraints which
0:17:06	are a it's a kind of like with a little in image extraction
0:17:09	uh
0:17:10	is it a from problem most of information
0:17:12	okay
0:17:13	or i thanks very that's
0:17:15	i think we have to maybe which
0:17:19	could you know
0:17:22	but
0:17:28	so
0:17:30	i and
0:17:32	uh could you never to a little bit and how you construct your on the basis matrix P can send
0:17:36	new
0:17:38	i do you did come you so you don't know that you got to the signal them and use and
0:17:42	is a very you need to a a a way of constructing matrix it
0:17:47	the support of the virtual function
0:17:49	as to for the for for for while i support as the support of a course of function
0:17:54	and i condition or on it's also support of on is uh in to get out the correlation of the
0:17:58	a function
0:17:59	i is one of no because we measured of or from function
0:18:02	that for we got the column of the for testing there
0:18:06	i would be this frame operator
0:18:08	oh i i also a in the previous question
0:18:10	why for that out a crucial part is not a anymore
0:18:13	we don't have any more than a and uh
0:18:16	frame and i a period and the for you
0:18:18	where the partial
0:18:19	for for is
0:18:25	i think you know much i think

SPARSE SPECTRAL FACTORIZATION: UNICITY AND RECONSTRUCTION ALGORITHMS

Compressed Sensing and Sparse Representation of Signals

Přednášející: Juri Ranieri, Autoři: Yue Lu, Harvard University, United States; Martin Vetterli, Ecole Polytechnique Fédérale de Lausanne, Switzerland