0:00:13no
0:00:14to that i'm not going to talk about
0:00:16that a problem and that inverse problem
0:00:18uh i'm actually look at the much simpler problem
0:00:20but i have a perfect set
0:00:22i know exactly but am looking for
0:00:24i put the device in the water
0:00:26okay
0:00:27and then i'm looking for nothing
0:00:29basically i one to reconstruct
0:00:31the what
0:00:31okay
0:00:33um
0:00:34so if i you
0:00:36if i do it before sold december paul inverse problem but they're we'll get its this
0:00:41pretty shocking right
0:00:43it's like finding can walter
0:00:46um
0:00:47in the
0:00:49if you look
0:00:50more careful that if picture of what you see
0:00:53is that with a trace
0:00:54from green to blue
0:00:57we show a basically says that
0:00:59this a in the time of flight
0:01:01probably if we remove
0:01:03this are you know these delay of time of flight we can get
0:01:06to the correct picture do so
0:01:08and what to get
0:01:10is not quite
0:01:11that effect
0:01:12is a lot of uh fluctuations run sense
0:01:15and that this file suggest that the positions
0:01:18um
0:01:19or not correct we have to
0:01:21um estimate this position
0:01:23so or two is to go row uh about it we can send was back to the manufacturer
0:01:27ask them
0:01:28to put them correctly
0:01:30on the circle
0:01:31and um you know it a distance
0:01:34and that they would probably say well uh you know
0:01:37uh on the piece of paper ever these simple but guess what these a physical devices
0:01:41is the best it can
0:01:42so we are
0:01:43start but these do watch
0:01:44okay
0:01:44and then the goal is to find
0:01:46the positions
0:01:48all of these sense
0:01:50um
0:01:52uh so
0:01:53how can we do that
0:01:56um
0:01:56if you are you know
0:01:58homogeneous medium
0:02:00do the simple religion should be didn't time of points and the pay was the senses
0:02:04basically
0:02:05um
0:02:06through this a constant C zero
0:02:10so if you know the time of flight
0:02:12you know the there was sense
0:02:14and what do so than we talk about their what distances
0:02:17um because
0:02:19there is uh
0:02:20very nice there i mean out to a nine john you that says
0:02:23if you put and
0:02:25a a points
0:02:26on the surface
0:02:28and if you for this particular metrics
0:02:31distance squared metrics
0:02:32which is basically
0:02:34the pairwise distances raised to the square
0:02:36that's all only the rank of this matrix is going to be for
0:02:40independent of N
0:02:42it is very easy to actually prove this is always like to three long
0:02:46but um so we're not result how can we use it to is another celebrate celebrated
0:02:50algorithm called multi dimensional scaling
0:02:53which basically through this uh
0:02:55matrix L
0:02:56if you put it on the left and right hand side of this and scored matrix
0:03:00uh applied
0:03:01no single value decomposition can find the exact positions
0:03:06of the sense
0:03:09so uh
0:03:10when i say that you can find exact positions what i really mean
0:03:14is that a can find them all to
0:03:16rigid transformation
0:03:17basically
0:03:18if you only have a pairwise was distances
0:03:21there is no difference between your topology
0:03:23and the one that is reflected
0:03:26okay
0:03:27well the one that is translate there
0:03:30or
0:03:31the one that is rotated
0:03:33so um
0:03:36it seems that the problem is solved
0:03:38because
0:03:40um
0:03:40i know the time of flight
0:03:42i can't D do use the um
0:03:44the pair was is
0:03:46a can use M the S
0:03:48i find a position
0:03:49actually continue stock
0:03:52well apparently um i should
0:03:54and or a couple of challenges head of first
0:03:56which prevents also
0:03:57from using go
0:03:59this met
0:04:01okay
0:04:05first thing all you know
0:04:07the or in you know and
0:04:08oh joint to do signal processing and in signal processing not think he's less
0:04:13so well time of flight are actually not
0:04:16that the first
0:04:17and source of
0:04:18certainty
0:04:19that's not
0:04:20actually
0:04:21the big deal because um
0:04:24well and the F is actually a robust against a a not
0:04:27but the more interesting ones are come
0:04:31the second
0:04:32source of on L certain certainty actually structured missing in trees
0:04:37and what happens here is that
0:04:39when the transmitter here a signal
0:04:42the ones
0:04:43which are in its vicinity can not hear the signal
0:04:47this is one of the limitations of this what
0:04:50so
0:04:52all of these red lines are going to be
0:04:54you right
0:04:55we don't have this information
0:04:58if i put it in a mid trick for
0:05:01well you know what have this use metrics
0:05:03two hundred back to hundred so i can up put actually
0:05:06uh you know numbers here
0:05:07it to take all my
0:05:09so instead i put
0:05:10colours here
0:05:12is top you know these numbers
0:05:14so on the left hand side
0:05:16basically what you know what we should
0:05:20on the right hand thought however
0:05:22the um
0:05:23the central band and these two corners
0:05:26are going to be race and we put zero because we don't know
0:05:30the value
0:05:34another source of uncertainty is actually what we call called right and the missing singing tree
0:05:39what happens is that
0:05:40if you plot the time of flight
0:05:42with the respect to the sensor in texas
0:05:44what you should get
0:05:46um is this news mandy four
0:05:48but
0:05:49what you will get
0:05:51uh
0:05:52we'll have
0:05:53you know a couple of sparks which do not make any sense
0:05:56and these are basically down years
0:05:58you have to discard them
0:06:00so you put zero again here
0:06:02no um
0:06:04if i you list the game means that some almost
0:06:08um
0:06:08pair was these sense are going to be a randomly this on
0:06:12well we seen that are going to be a riesz random of like the model let B C
0:06:15okay
0:06:17now um
0:06:19so we all left be such a picture
0:06:21you no longer have all the pair was this
0:06:25and if that's not enough
0:06:29uh well basically you know
0:06:30well in a
0:06:32okay
0:06:33oh you have to wait
0:06:46um
0:06:47so in a matrix form
0:06:48what it means
0:06:49is that you know you will have a couple of dots
0:06:52you know randomly
0:06:53as yet or
0:06:55you're
0:06:56and if that's not enough
0:06:58well you have these on known like that in the beginning of the talk i uh you know
0:07:02oh i i mention
0:07:05so well the reason here is that um but these are electronic get
0:07:09right
0:07:10and uh
0:07:11oh when you fired the transmitter
0:07:13it's not going to transmit the signal immediately each weights uh for a couple of seconds
0:07:19mark second sir
0:07:21and that but we don't know this V so we have to estimate these as well
0:07:26okay
0:07:27um
0:07:29you know just to uh less first um
0:07:31sort with these um
0:07:33a missing entries forget about this that
0:07:36um shift
0:07:37and time of flight
0:07:39um
0:07:41um so we had
0:07:43these amazing result that this stance squared matrix was ranked for we could use M T S
0:07:48we can no longer use it because may of these that
0:07:51there was these sense are missing
0:07:53now
0:07:54uh the question is there were not we can estimate these missing in tricks
0:07:59well uh
0:08:01this is actually a topic of matrix completion that had recently you know there are a lot of risk uh
0:08:06that's been lot of activities in the past to years
0:08:09and the question is
0:08:10um you know pretty five this state here
0:08:12we have
0:08:13a rank K matrix of dimension and by and
0:08:16some of the injuries are random me
0:08:20and then it turns out that on the the road conditions you can actually
0:08:24find the missing it
0:08:27um the one uh so
0:08:29right now they are you know a lot of uh and is out
0:08:33when we started this work the a couple of them
0:08:36so um
0:08:37we actually
0:08:38use um
0:08:39of the space um um
0:08:41the develop point want to now already and his students at stand for
0:08:46and the way that uh
0:08:47um this algorithm works
0:08:49is basically by projecting
0:08:51the uh at the metrics on the space of rank
0:08:54Q mattresses
0:08:56and then uh doing some kind of great great in these
0:08:59now um
0:09:01do is a catch
0:09:03and them in all these out algorithms
0:09:05that i know
0:09:06um you have to use you
0:09:09that the in trees or
0:09:10you raise randomly
0:09:12okay
0:09:13um so probably do true before i guess
0:09:17um i
0:09:17you know probably you know from of for this problem
0:09:20but uh well to the best of my knowledge
0:09:22this was the case
0:09:24and now um so
0:09:26but as i mentioned we have this structured missing trees
0:09:29these are in trees that we know we will never get
0:09:32a any
0:09:33observations about
0:09:34right so
0:09:36um i to space is not going to work for
0:09:38as a T
0:09:40um
0:09:42so we have to redevelop develop again these all the space to make sure that
0:09:45a a when if we have a structure missing trees
0:09:48this is going to work
0:09:50so before like a you know all these error bounds for
0:09:54uh for the classical a to space is no use for a
0:09:58um um and um well the theory a a is actually quite simple and you can find it in you
0:10:02know paper
0:10:03um i'm not going to bore you with that you know details of the proof sets order sartre
0:10:08but uh let me just mention
0:10:10you know the model that use
0:10:12so we no longer assume that the sensors are are actually say sensor circle
0:10:15you seem that the R
0:10:16uh a on these and we
0:10:19we
0:10:20uh be a
0:10:22and the way that we are going to capture the structure missing trees are great are are
0:10:26but a bit through the use um
0:10:28uh a a and with that if
0:10:31there's the transmitter here
0:10:32all the sensor
0:10:34um in flight three kill or not going to your anything
0:10:38okay
0:10:39so
0:10:41if the sensors
0:10:43uh or
0:10:44you know distributed uniformly at random you sound was
0:10:48and if you see assume
0:10:50that um hmmm the time of lights are going to be a random with probability P
0:10:55fix number
0:10:57and for the structure
0:10:58uh missing trees if we assume that the are fine is going to scale
0:11:02like school root of log over and
0:11:05then our our or and reads as follows
0:11:07that
0:11:09the
0:11:10distance
0:11:11between the
0:11:12um
0:11:13this squared matrix and in its estimate is going to be bound but boy these two true
0:11:19um
0:11:21uh what we should mention is that
0:11:23um
0:11:25we we did a assume anything about the noise
0:11:27so the noise can be deterministic
0:11:29random
0:11:30um you know you name
0:11:32so these bound whole
0:11:34you need full generality
0:11:36um
0:11:38the all that thing that they should mention is that
0:11:41this term goes to zero as an goes to infinity all everyone we control controlled easter
0:11:46in many many cases
0:11:47it goes to zero
0:11:49but i'm pretty sure you can come up with example take doesn't
0:11:52for instance
0:11:53for go in noise
0:11:55uh uh that are
0:11:56now a prior we were not
0:11:58you know interested in a find a distance score metrics what you wanted to do side you know finding to
0:12:03positions
0:12:04but as i said we can find the positions of to transformation
0:12:07and
0:12:08we have to make sure that you know what and uh we we we basically one it
0:12:13uh
0:12:14uh
0:12:15one to define the distance between the estimate
0:12:19and the right one
0:12:20in a way that doesn't depend on the rigid transformation it should be in
0:12:24it turns out the right way to do it is basically
0:12:27these four
0:12:28um which is in barrie
0:12:31on the different formation and
0:12:33it's going to be zero these
0:12:34diff the ins distance
0:12:36even all if E X you equals X i
0:12:39now
0:12:40um if we apply
0:12:42and the S
0:12:44after
0:12:45oh the space
0:12:46uh we can actually bounded if then
0:12:50basically the same rate that B D before
0:12:52is going to be it's same expression
0:12:54okay
0:12:56no uh for the uh
0:12:58so we had another other source
0:13:00of uncertainty which was these to like these constant that to have to measure
0:13:04here we assume that is
0:13:05going to be
0:13:06uh for every want for every transmitter is going to be say
0:13:09okay
0:13:10now
0:13:11a there is going to be a need to about it and that's fine
0:13:14these um this T zero
0:13:16um
0:13:17but the for the sake of them are not be true the details of these out with M
0:13:21uh what they should mention is that is probably is nonconvex
0:13:25so um i it's very difficult to find
0:13:28uh you know to you actually out prove the convergence
0:13:31uh we have if you're if the with and it converges numerically or we don't have any pro
0:13:38uh and the idea is again to use this property of the these sense square metrics metric is rank for
0:13:42wanna make sure that you know what we're fine is actually going to be as close as possible to the
0:13:47right form
0:13:49oh okay
0:13:49so
0:13:50um
0:13:51unofficially we had access to real data what
0:13:54um
0:13:56oh i cannot report these these you know
0:13:58these data as here so what we did is just some simulations that maybe the characteristic of uh the real
0:14:03data
0:14:04and then uh
0:14:05um
0:14:06a diffuse basically you know well what you still before it uh
0:14:10you know the the a or is going to be in the twenties and D meter is the number of
0:14:14them or two hundred and then
0:14:16uh
0:14:16the deviation is going to be half from that are is does that was the D is going to be
0:14:20D the metrics
0:14:22to real matrix if this is going to what
0:14:23to to be able to have
0:14:25and the
0:14:27if the you
0:14:28um you know you actually do well our them
0:14:32uh a fee that there are going to be a lot of deviations
0:14:35uh
0:14:37um
0:14:38from the from the circle so
0:14:41if you got yeah that this is the prince function that it have
0:14:44that all of these sense of are going to be on the thing bill but if we want that are
0:14:47with them see that they are not going to be
0:14:50a you know they're got not be to be place exactly the same
0:14:53so
0:14:54this the last
0:14:57um
0:14:58if you the the picture that we started that of
0:15:02if we actually
0:15:03remove the uh
0:15:06do you lace
0:15:06you know these constant you'll lay set we have to find out
0:15:09we'll get if speech or are you it before
0:15:12if we complete the distance a a three
0:15:15with a a a space
0:15:17you'll get is picture
0:15:19it's not very different from the previous picture
0:15:22a but if you find the positions and then you know a sold the inverse problem
0:15:28you get back into one
0:15:30the
0:15:30it's really important to calibrate the system is really important to find
0:15:35position
0:15:37and the
0:15:38even if all you know beforehand the the um
0:15:41the range was from
0:15:42uh one thousand uh
0:15:44four hundred to one thousand six hundred before the close
0:15:47from
0:15:48you know these value this one
0:15:50then you don't see any deviation a
0:15:52so it eight towards um
0:15:54you
0:15:56yeah thank you very much and i'll be have to answer questions if true or german
0:16:06thank you for this okay and
0:16:08we have time for one question
0:16:09please
0:16:15i
0:16:16um we just some on the might like best aging
0:16:19and and was like given a set up and you make get that yeah so you don and i one
0:16:24writing differentiation between you time at like measurement
0:16:28and and just an eight station at the sense that the "'cause" what we found like if a code is
0:16:32getting good trying to fight management
0:16:34it "'cause" i things like multiple and more fundamental fashion
0:16:37um so i actually the you're not have a seen the time of flights measurements so these there is this
0:16:42yeah
0:16:43these guys they have these estimators for the time of flight
0:16:46right
0:16:46and we seen that what were they you know what where we got from the is actually correct
0:16:51as a how likely as i think you know
0:16:53uh uh what is the and that kind of flight measurements
0:16:56i i get to get good ones because you got a dispersive medium
0:16:59um no i actually don't know the yours
0:17:01K can i think you it seems out
0:17:05okay so let's move to the the second work
0:17:08no the to not be in me