0:00:13the Q for you a production and
0:00:16that you
0:00:18all you hear
0:00:19in this talk um talk uh we go but a lower be just completion a john magic approach
0:00:25and the corresponding performance going
0:00:28on this work
0:00:30is a joint work with a come and and a an echo beach
0:00:34both school as those from your you C
0:00:39in the introduction hard
0:00:40oh would discuss
0:00:42what is missing
0:00:44for the run could be just compression
0:00:47once we figure out what is missing
0:00:49we would like to to you the gas
0:00:52however the the natural approach
0:00:54does not a work at all
0:00:57to address this problem we propose a new more
0:01:01but john much come home
0:01:02and based on this john can norm
0:01:04we are able to obtain some strong them is going T
0:01:11what to get to me for go image of completion
0:01:15ms start waves
0:01:17compress a compressed sensing
0:01:19comes at the is taken on its that the hand of sparse signals
0:01:23a signal X
0:01:24a set to be case sparse if they are owning kate on the those in X
0:01:29and being we perform you i'm and
0:01:31why are to five X
0:01:33uh the reconstruction problem is should be come from the eggs
0:01:37based on our my and the back to one
0:01:41the ninety but coach
0:01:42but compressed sensing
0:01:44it is to do every the also search
0:01:46oh exhaustive search basically we
0:01:48try all possible locations
0:01:51for long rose
0:01:53but i or all
0:01:54but as a we know that the complexity is huge
0:01:57so it was you search is not to go
0:02:01to reduce the complexity
0:02:02we can use a a one minimization of greedy i
0:02:09lower run image is can be seen
0:02:10is also a tech that the and a sparse signals
0:02:13now this
0:02:14signal
0:02:15is a matrix
0:02:16and the sparsity
0:02:18is in the space
0:02:20now the X
0:02:21yeah and by and matrix
0:02:25that's consider use
0:02:26think low value of decomposition
0:02:28if you could do you tend to ace them
0:02:30we each has close
0:02:32yeah a
0:02:33is that and image case
0:02:34containing
0:02:35singular value
0:02:37we say X has to right are you and only of they are exactly are mining
0:02:43singular values
0:02:44not they don't
0:02:46has the stigma sparsity it's in the egg space
0:02:51the lower an image of completion
0:02:53is great are we assume that we do not know the order entries
0:02:57we only know some of them
0:02:59yeah of media
0:03:01is the index set
0:03:02of all of the of the of the entries
0:03:05it's a me is the part of the vision
0:03:08we would like to you for the missing entries
0:03:10based um
0:03:11the of the the entries
0:03:13and the low rank structure
0:03:15so mathematically we would like to find a estimate if hack such that the right
0:03:19is at the most are
0:03:20and we have the data consistency
0:03:27because of the similarity be um between
0:03:31come processing and a low of images is seem many methods
0:03:34can be used it for example a one we have a why mean magician we we replace the
0:03:40it when norm where is the nuclear more
0:03:42which is just a
0:03:43the L one norm of the signal as
0:03:46well so can try some ah a can use then some greedy rooms
0:03:50for comes sensing to the mitch is seen
0:03:53a a second will however
0:03:56the is uh one thing missing
0:03:57in this pure
0:04:00that you
0:04:01L would all search
0:04:04income sensing with screen we can to all possible locations for non the hours
0:04:09we can do exhaustive search even though the compressed these huge
0:04:13but he me to of in problem
0:04:15as we were sure what is shortly
0:04:17we are looking at
0:04:18a complete space
0:04:20it but it makes sense to talk about exhaustive search you a in this space at all
0:04:26that means even do we can is then to and Y mean an and a greedy i them from comes
0:04:30thing to low up average accomplishing we can not extend tend the all search
0:04:36and a a this search is
0:04:38the main topic
0:04:40of
0:04:40this top
0:04:42to define a of those search are we need some definitions
0:04:47is is U you are the set
0:04:50containing all the matrix a
0:04:54containing
0:04:55exactly are are in also normal colours
0:04:59for any given
0:05:01matrix you
0:05:02in this but to you in a market guess bad and are T in no subspace
0:05:07in this to okay are we have to just you and you plan from from this but you uh and
0:05:12you and R
0:05:13and they is spent to different
0:05:15subspace a
0:05:17no
0:05:18given a image to X
0:05:20suppose all the columns of X
0:05:22like in the subspace spanned by you
0:05:25the in this span you can be viewed as a colour space
0:05:28of eggs
0:05:29and the right of X
0:05:30it's added
0:05:31uh use exactly are
0:05:35with this can to a we are able to if why it would all search
0:05:40is a point in given just you in this but to you M R
0:05:45we look at of all possible six
0:05:47generated from you
0:05:49and which choose the wine
0:05:51that it is more uh than most
0:05:53cost isn't
0:05:54with all possible of the visions
0:05:57then the uh object function if a if you it depend as
0:06:01this a out of will be as one
0:06:03of the different
0:06:07the lower the is are comforting
0:06:09it then you couldn't to minimize this object function
0:06:12on on you
0:06:13as if you they don't
0:06:14was as if if the real in
0:06:17you means a we know that
0:06:18the could the be meetings
0:06:20has rock are
0:06:22and
0:06:22it is consistent and with all part of the vision
0:06:28in this talk we'll focus on how to fly it this
0:06:31global minimizer used star
0:06:34we were lost talk about
0:06:36under which conditions
0:06:37the global mean meant is unique
0:06:42and a K O i would like to as a fundamental question why we have about
0:06:46L was your search for she's completion
0:06:48as a first space because you know
0:06:50in sensing in it the all search
0:06:53is used this
0:06:54but here what mission of completion problem
0:06:57and we can see this may this site you but in you and R is that
0:07:02can the space
0:07:03it is actually a smooth manifold
0:07:05so we are doing of them addition
0:07:07all a sum was mine for
0:07:09the come by C time know
0:07:11actually a to our team can use your ins
0:07:14would your search in most cases i would also so she can be finished in just twenty of P D
0:07:19O fifty iterations
0:07:21it just uh
0:07:23the was station
0:07:24uh i want to playing the details but a P a we look at a modified a it will new
0:07:29search
0:07:30and ah
0:07:32the right the like he's
0:07:33the performance of the modified it would also so she and the house a kobe is the to the performance
0:07:38is
0:07:39and you can see
0:07:40the modified a L the also it the actually um P mining as in the are true
0:07:46so the key message to pay i is that
0:07:49for me completion problem they was search
0:07:51mel be very good
0:07:52pixel
0:07:56okay
0:07:57however
0:07:58it just mentioned some ones of every this that's but
0:08:02it does not what
0:08:03why that's and card
0:08:05um
0:08:06a some example
0:08:08recall that the that from thing is so whether probably small
0:08:12it the can be written as
0:08:14a sum of money atomic functions and each at coming function "'cause" the two
0:08:18one column
0:08:20of the a low of the vision
0:08:23alright right
0:08:23in this example we only look at the one column
0:08:27we suppose that are we know that
0:08:30second and is that and entry the for centuries miss
0:08:33do we assume that we know the rank it's one
0:08:36the for the comes space
0:08:38can be friend
0:08:39to to by a contract
0:08:41and we are interested in
0:08:43the comes space
0:08:44um permit
0:08:45part of it to by T in this
0:08:48by by four
0:08:51note that we have a one one here we have to keep hey
0:08:55as long as T is nonzero
0:08:57then
0:08:59the object function
0:09:00it would be don't
0:09:01we can choose a probably as well that E
0:09:04but
0:09:05if a you personally L
0:09:07no matter what probably we choose
0:09:11observe function it's a two
0:09:14i
0:09:16that means
0:09:17the object function defined in the problem is more
0:09:21a is not continuous added to see if they
0:09:24as we all know in the optimization problem if the objective function is not continuous
0:09:30then we instill strap
0:09:32in most cases we can not get any of them is currently
0:09:38to address this problem
0:09:39we propose a geometric objective function to replace
0:09:43the previous work is more
0:09:46to define the
0:09:48oh and so much more
0:09:49that's use the reason is that okay
0:09:51we look and one column
0:09:54and we even have to be the key and the subspace
0:09:57spent about all the vectors
0:09:59such that
0:10:00the second and as the entries assume as our part of the vision
0:10:05and we choose
0:10:06the first entry actually
0:10:07because we do not know the centre
0:10:09so we can treat it actually
0:10:11and we look at the subspace spanned by
0:10:13this time
0:10:16for given
0:10:17column space
0:10:19represented by you
0:10:21we look at the
0:10:22minimum principal angle between the subspace E
0:10:26and the column space
0:10:28they'll
0:10:28i
0:10:29what about the detailed
0:10:31definition about the principal and go but
0:10:33basically a principal and go
0:10:34just a the and does
0:10:36between two planes
0:10:38and we only and at of the minimum present fine go
0:10:41because
0:10:43this and but you've to the know if and only if
0:10:46to subspace
0:10:47in the
0:10:48non triple
0:10:52now we are able to define the john mentioned function point to call we define
0:10:56a is john mentioned function as sense well
0:10:59overall all comes in the thought of this are coming
0:11:03function
0:11:05and that it was this
0:11:06the of those search
0:11:07problem becomes
0:11:09minimize this
0:11:10john match
0:11:11object function
0:11:12i to you if G
0:11:14you was to deal
0:11:18this much
0:11:20from we we are give us many in S properties
0:11:23but
0:11:24it is can you know
0:11:25yeah we simply to all the come tools
0:11:27of the four B small
0:11:29and the john at mall
0:11:31and you can say
0:11:33the probe is norm
0:11:34a discontinuous
0:11:36and as a region
0:11:37well the job much norm its continuous
0:11:40everywhere
0:11:42more importantly we have the following zero
0:11:46the set and the left
0:11:48is the
0:11:49it things
0:11:50all the colour space ace
0:11:51that a all magically
0:11:53consistent
0:11:54with all possible of the regions
0:11:55yeah if a you put it
0:11:57the set on a right
0:11:59contains all that comes with bases
0:12:01that are probably is
0:12:03cost this and
0:12:04with without that
0:12:05part of the vision here if F you put a little
0:12:08i'll rooms is that because
0:12:10the for is small is not continuous
0:12:13this set is not close
0:12:15but
0:12:16the level set
0:12:18it is a closure
0:12:19but with the right side
0:12:21what does this mean is a means out john might function
0:12:25can be viewed as a
0:12:27some new supporting of the forty some more
0:12:29up to a scale
0:12:34is on this fact we are able to obtain some strong performance score and he's
0:12:39what two scenarios
0:12:40what's general
0:12:41are run to one matrices
0:12:43with up to re that thing happen
0:12:46second as in not real for them any matrices with up to rewrite
0:12:51for this tools
0:12:52so on rows we are able to prove that
0:12:54if we use a re didn't is in the mess it
0:12:57to optimize to minimize of jeff from if G
0:13:00then with a probability one
0:13:02we are able to each
0:13:03a global
0:13:05minima
0:13:09a first point i would like to mention that um
0:13:12because you know a the object function is not a convex
0:13:17but to
0:13:18lyman than is
0:13:19we are able to
0:13:21a what are we are we are able to prove that there is no and the local minimum
0:13:26oh set of all
0:13:30second
0:13:30what we see out of "'em" this drawn a performance guarantees are use one because
0:13:35different from a standard to re
0:13:38we do not require in queens
0:13:39condition
0:13:42oh and we dollars
0:13:43how with the probably D one and the body after a image size
0:13:47it does not require the image size is
0:13:49so if you know a large
0:13:54just
0:13:54very improve fully close through the
0:13:56a key ideas behind a to
0:13:59so in a a a a new star be a global minima the
0:14:03P are are we may have a much a global minimizer
0:14:06the in which just choose one of them actually
0:14:10because if a you the L
0:14:12every
0:14:13a a function should be uh you post to the zero at will
0:14:18in this to to the what line it's uh
0:14:21so we is that for the i-th column
0:14:23the right the line it is a set of a just column
0:14:26the
0:14:26global minimizer of must lie in the section
0:14:30of this one
0:14:33not for P given um one than they choosing
0:14:37can space
0:14:38you "'cause" to by you the or we compute the we didn't
0:14:42respect to every
0:14:43a coming function
0:14:46we project and then team weekend um
0:14:49to the back to used are a you the deal
0:14:52we are
0:14:52it but to prove that this protection
0:14:55is always nonnegative
0:14:57if you but to the deal if and only if the
0:15:00at time from if be do all right
0:15:04know that
0:15:05the overall all gradient
0:15:07it the summation of the gradient and for every a functions
0:15:11if we put down to the negative of of all weekend
0:15:14to the fact that your stop minutes you the you know
0:15:17then we are able to show that
0:15:19this projection is also active
0:15:22it it you but to the all if and only if
0:15:25if a G you put the all that means
0:15:27you the arrow is alright
0:15:29a a you met
0:15:32so
0:15:33we do not have any local minimum
0:15:36oh set up for
0:15:38the greedy in you put it on price
0:15:40we have already reach a global in
0:15:45in summary
0:15:47in this talk
0:15:48the main has to the main message is
0:15:50that in no so that each me it's
0:15:53actually can be very good
0:15:55for completion problem
0:15:58and we propose a a that you go object from chain
0:16:01to or of what is the technical details of difficulty ah a with the natural
0:16:06formulation
0:16:08and based on that we are able to
0:16:11proof strong of and got he's for two special case is
0:16:15we do not to weak well in with condition
0:16:18our our problems and that's it has with probably to one
0:16:21and a body
0:16:22but a tree which to size
0:16:24a to to work
0:16:25we would like to prove some of similar results for
0:16:29the more general okay
0:16:31thank you for you
0:16:31at
0:16:37questions
0:16:40like
0:16:49are
0:16:49actually to me
0:16:51questions
0:16:52for for this question is what's to prove but model
0:16:55mm
0:16:55because it is proved to one
0:16:58and the second question is one regarding the performance can
0:17:02what happens for example if you take only
0:17:05one samples to match
0:17:07okay
0:17:08so on
0:17:11first sparse was uh about the probability models basically will assume that a we only assume that
0:17:17um
0:17:18biz a we to all the in on the can space
0:17:22we only assume assume that
0:17:23as the E initial state we run a peak
0:17:27a space
0:17:28uniformly
0:17:29on this
0:17:30a a compact set on a all possible call
0:17:34uniformly distributed
0:17:36as the initial state
0:17:37after that we just use optimization estimate message
0:17:41so method is
0:17:42what about we only have one them one and two of the from the matrix
0:17:47as i as a mission
0:17:48and we do not talk about the unique an yes
0:17:51of the source of which and so in that case
0:17:53actually we have a you a need to mining comes space that the can out of the day
0:17:58that's white i the a given didn't machine before but
0:18:02that's why a you can uh you can you you you look at the estimation we out
0:18:06yeah
0:18:08you can see it with a
0:18:09then close
0:18:10the number of them hoes either the by some more
0:18:12and so we are able to
0:18:15for
0:18:16a column space
0:18:17that match all of the vision
0:18:22yeah
0:18:25oh okay
0:18:27uh oh that's about the um uh us space you in R
0:18:32yeah um you have markham's consists of the spy of four
0:18:36you know so the much is well as the columns are
0:18:38or not
0:18:39right
0:18:40yeah
0:18:40so much as
0:18:41so
0:18:42is just lose its is robust many many so
0:18:45yeah yeah i i and emission algorithm i'm info photo he because or i wanna have any minute
0:18:50so actually a a is you we back a comes space and that that's can space it's at and and
0:18:56uh in the grassmann manifold
0:18:58and all lined as is down
0:19:00not
0:19:01um you in R i is actually down on the grassmann manifold
0:19:04but i just a a to those details
0:19:06i'm sorry but yeah
0:19:07or do so
0:19:08it's it's about the runs was amount of use that to the images with the projects i
0:19:14uh right
0:19:15so you can define five your a fines is on the circle
0:19:18yeah yeah
0:19:20i
0:19:33i was just wondering what the circuit to serialise my son
0:19:37really
0:19:38them or yeah yeah yeah observing the entire matrix
0:19:41yeah exactly
0:19:42i
0:19:43okay two
0:19:44this triggers but are
0:19:46what is an antibody that's
0:19:48we use the gradient descent
0:19:49method are
0:19:51the manifold then we would do fine
0:19:53that right from space
0:19:54that part is not true
0:19:56because uh in terms of image accomplishing this it's you know we
0:19:59we need to do anything
0:20:01we we need to do nothing
0:20:02because we have the ball under
0:20:06i