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 |