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