0:00:16i i think you uh many was out slow be presenting
0:00:19uh paper
0:00:21and title the the group
0:00:23two two of for or as i don't because this problem
0:00:25uh by brian kind of a my adviser
0:00:27uh fess with peter image
0:00:32okay so um a well known problem that's been around a while is uh your a title for "'cause" this
0:00:37problem
0:00:37where we uh C to identify
0:00:40and orthogonal cycle transformation between two data matrices
0:00:43and uh
0:00:44this context we seek to
0:00:46minimize the frobenius norm squared
0:00:49of the difference of a
0:00:51in this case
0:00:52the rows of B with rotated rows of a
0:00:56and and this is useful uh
0:00:58uh it to serve as as a as a geometric
0:01:02uh transformation or a geometric rotation to to correct for
0:01:06uh
0:01:07rotational distortion as
0:01:08uh distortions between
0:01:10i mitch each a and B
0:01:13um
0:01:14uh
0:01:15going going to
0:01:16going to a second order version uh there was there's the two sided or because he's problem
0:01:21or you have to uh
0:01:23symmetric
0:01:25similarity matrices C and C are little are can to give is
0:01:28reference
0:01:29and
0:01:31in this in this problem we have
0:01:33rather than um
0:01:36uh
0:01:36de de de rotation during on one side we have it of on both sides
0:01:40and in the form are transpose
0:01:42C R and and again we're trying to match up
0:01:45um this this this to side rotation with with
0:01:48with some
0:01:50uh
0:01:51some reference
0:01:52uh
0:01:53similarity so
0:01:54uh
0:01:56the says a bunch of applications uh
0:01:59one being a a covariance or or correlation
0:02:02a matrix matching so
0:02:04we eight
0:02:05a data matrix to we've induced
0:02:08uh a double rotation
0:02:10on the covariance matrix
0:02:12um a more interesting problem
0:02:14would be a related to a graph matching problem so in a ice metric graph matching
0:02:20we're given uh two adjacency matrices
0:02:22again C and C R
0:02:24and uh
0:02:25this can be weighted
0:02:26um
0:02:27and and and and the at a is to find a a permutation matrix
0:02:32which
0:02:33best uh
0:02:35which we we which serves to to reorder the the nodes of one graph and to the other man in
0:02:41in the other graph
0:02:42uh again
0:02:43matching in in in the for been used um score different so
0:02:47this is a hard problem big
0:02:48given this combinatorial nature
0:02:51uh there are
0:02:53one one one popular method is
0:02:56when me i'm as method um and
0:02:58involves relaxing this problem
0:03:00to
0:03:01an orthogonal
0:03:03uh constraint
0:03:05and then and then finding the closest permutation matrix
0:03:08as the hungarian algorithm
0:03:13okay so if we go back to the of that don't is problem the set this has a known solution
0:03:17and um
0:03:19given
0:03:20uh the the the right circumstances
0:03:22it's a unique and this given by D
0:03:24uh
0:03:25single value decomposition of A transpose be where
0:03:29a singular values
0:03:30um
0:03:30have to be
0:03:31transform just a
0:03:33all ones
0:03:34oh have for the two sided however
0:03:36it's a it's
0:03:38it's
0:03:38a bit more complicated because
0:03:40uh we have a close form solution but it's really family of solutions so
0:03:44if the eigen decomposition of C is is V
0:03:47lamb V transpose and C are B R and R
0:03:51the are transpose
0:03:52then
0:03:53uh
0:03:54a solution to this problem is given by
0:03:57V V D V are transpose where D is a a is a diagonal matrix where each i an entry
0:04:02is plus one or minus one
0:04:04so
0:04:06um
0:04:07right away we see that we can have know
0:04:09to the N possible solutions
0:04:11at least
0:04:14uh so so so i was a bit of a history um
0:04:17in in in this talk we're going to consider
0:04:21scenario area where
0:04:22a for example a graph verdi sees don't just have
0:04:26similarity measures between nodes but
0:04:29um but also
0:04:31there some side information
0:04:33and and so this paper considers
0:04:35case where
0:04:36the a the seize
0:04:37our are parsley later
0:04:38in to go
0:04:40uh so
0:04:41so for example if uh
0:04:43let's say were modeling a face so
0:04:46so you know certain certain notes belong to the i certain nodes belong to the nose set
0:04:50um or we can think of a a spatial configuration so
0:04:54and uh in uh
0:04:56fmri analysis we might have
0:04:58certain regions of interest
0:04:59so
0:05:00we have kind activity is between
0:05:02of voxels but we also know uh what are our why those walks
0:05:05two
0:05:09okay
0:05:10so suppose
0:05:11are are are data dataset
0:05:12is parsley did in
0:05:14capital "'em" groups
0:05:16but is for each point i there's
0:05:18there's some group that i belongs to and that's uh
0:05:21will note that G of i
0:05:24and uh uh uh the goal is
0:05:26to
0:05:27again
0:05:28estimate an R
0:05:30uh a in in in in the two sided
0:05:32of course this problem but
0:05:33here are is gonna be block diagonal
0:05:36and and and those block diagonals correspond to the
0:05:40nature of of the uh
0:05:41problem
0:05:43so uh because problem the uh
0:05:46groups to sided or that process problem and uh
0:05:50of course when when when M equals one we
0:05:52go back to the original
0:05:54a standard to prior
0:05:59so
0:06:00get
0:06:01given T block tan'll constraint
0:06:02um
0:06:04it essentially introduces
0:06:06some some linear constraints that is the elements of
0:06:10this large matrix R
0:06:12a a such that
0:06:14uh
0:06:15the uh it in X P Q zero if um
0:06:19if uh
0:06:21notes P and Q of the
0:06:25and uh some some benefits of this approach are
0:06:28you know the the
0:06:29these constraints regular as the problem so
0:06:32uh we might be reducing the effects of fitting
0:06:36and also were were we're using prior knowledge that uh
0:06:39we know about a about this graph
0:06:42um
0:06:43also we have uh
0:06:45a few were
0:06:46parameters to estimate so it's uh
0:06:49it's a
0:06:50were dealing with a i
0:06:52a a a a a a lower dimensional problem
0:06:56okay so so for "'em" greater than one we so that it it it does have a
0:07:01a close form family
0:07:02solutions
0:07:03but for "'em" greater than one
0:07:05where we're gonna have to look at an iterative
0:07:07uh technique
0:07:08so that let see i i and C I R denote be with an region or within groups similarity structures
0:07:14uh and
0:07:16see i J where i is not equal to J we'll what we'll do not the cross
0:07:21somewhere structures
0:07:22so
0:07:23again given that this is uh going to be an iterative
0:07:26solution
0:07:27uh we'd like to start from
0:07:29a a a a a good starting point
0:07:31and so
0:07:32a logical starting point would be to just consider the you within group similar
0:07:38so we can start it
0:07:39each block
0:07:40element of our
0:07:42rotation matrix
0:07:43to be
0:07:44uh V M M D M V M M R transpose
0:07:48where
0:07:49uh
0:07:50the V and the Rs
0:07:52correspond to the eigen decompositions of
0:07:55oh of uh
0:07:56of uh a C M M and
0:07:58and and M R
0:08:02so and and so from the starting point our goal is to improve on this initial estimate
0:08:06uh by looking at across region similarities
0:08:09so it's broken out into two step process
0:08:12uh the first is trying to
0:08:15assign appropriate plus one's uh
0:08:17plus one or minus one entries
0:08:19for the uh D matrices
0:08:21and it turns out that
0:08:23um
0:08:24and in in
0:08:25in a in expanding the problem
0:08:27this is um
0:08:29reduces to a quadratic binary optimization problem
0:08:32um
0:08:34and so we can use uh
0:08:36uh we we we can get an approximate solution with
0:08:39the
0:08:40max cut uh but but but by by using the algorithms
0:08:43to solve max cut
0:08:44uh the second step after we've got an R
0:08:48are D matrices
0:08:50wouldn't be to uh
0:08:52fine the or that call
0:08:53estimates
0:08:54uh with a with a greedy uh strategy
0:08:57and the way we do that
0:08:59is by selecting
0:09:01um elements
0:09:02that that are within groups and applying
0:09:05uh appropriate givens rotations to
0:09:07decrease the objective and so this is of a form of a
0:09:11block or set
0:09:16i to just a a a a a bit on a
0:09:18the second step um
0:09:21we can we can view the matrix C as a yeah
0:09:25as
0:09:26a noisy
0:09:28rotated version of
0:09:30of of a C R
0:09:32and
0:09:33and because the noise the the the eigen vectors
0:09:37uh of with a group similarity
0:09:40our berger
0:09:40so
0:09:41um
0:09:43the
0:09:44the uh factorisation we had the for uh of our initial estimate
0:09:47of
0:09:48are M equals
0:09:49the M M
0:09:50and D M V M R transpose
0:09:53uh
0:09:53we introduce
0:09:55another matrix you to get the M M U i'm the M V M M R transpose
0:09:59uh and
0:10:01and
0:10:01we view the U M and the D M
0:10:04as a a corrective measure
0:10:07to decrease the object
0:10:10so
0:10:10the D Ms
0:10:11as that's so so the use in the D uh are
0:10:15uh a there to incorporate
0:10:17the cross region similarities
0:10:19to correct the uh
0:10:21perturbed eigenvector
0:10:27so if we let uh
0:10:29you be D block diagonal
0:10:31uh
0:10:33version of of you want through you M
0:10:35then
0:10:36uh what we do is
0:10:38is is
0:10:39in our really approach is is you generate these givens rotations so we we pick
0:10:43um
0:10:45uh
0:10:45elements uh
0:10:46P T in Q T
0:10:48that belong the same group
0:10:49and we successively apply givens rotations
0:10:53to um at at at iteration C to decrease the object
0:10:58um um
0:10:59and at a a P change you T R
0:11:02are found
0:11:02uh using uh and and and and approximate greedy
0:11:05and and the angle is the sample the line search
0:11:11so
0:11:11uh look at some results
0:11:13uh
0:11:14so this was tested on on two data sets the first is set was the N nist handwritten digits
0:11:19um and second was the L B face day so
0:11:23for "'em" nist we have
0:11:24i ten groups
0:11:25for ten digits and for face database we have fifteen groups for
0:11:29uh a fifteen
0:11:30uh people
0:11:32so each group
0:11:33was
0:11:34uh transformed by by a random orthogonal matrix it's of M
0:11:38and then and and corrupted with noise
0:11:40so
0:11:41and you see before you
0:11:43the the the D block diagonal
0:11:46uh elements of this matrix are the with group similarity structures
0:11:50and the and the off diagonal
0:11:51elements are do you cross group
0:11:53and so you'll see uh
0:11:55you know
0:11:56the covariance of uh
0:11:57digit three and seven
0:11:59here
0:12:01point by the
0:12:05okay case at test accuracy we looked at
0:12:08um
0:12:10the
0:12:11our air estimate to noted uh
0:12:14by what what we're each
0:12:16we're reach block of
0:12:17of that rotation matrix is the dated
0:12:19uh
0:12:20and had uh we looked at
0:12:23the the inner product of um
0:12:26a have with a and uh and uh we took the average so so so this as the figure between
0:12:31minus one and one
0:12:33um
0:12:34and we see that uh
0:12:36that at iteration zero
0:12:39uh
0:12:40this is the result if we just take in
0:12:43to account the within group similarities and then
0:12:47as as a T increases the number of iterations increase
0:12:51uh out knowledge of across region similarities
0:12:54uh help us
0:12:56to teen uh a better match
0:12:59and uh we
0:13:00and this is true for both
0:13:02you know of the M nist
0:13:03and the old
0:13:07um
0:13:08going to the more adjusting problem of graph matching
0:13:11so
0:13:12uh
0:13:13each group in this case was was transformed by by some random permutation matrix
0:13:18and then perturbed
0:13:18with noise
0:13:19and uh
0:13:21the rather than solve for the
0:13:23uh am
0:13:25after after solving for each i M at at every time step you then
0:13:28use the hungarian algorithm
0:13:30to get the uh corresponding
0:13:33um permutation matrix
0:13:34and
0:13:35we can and and and we plot the accuracy
0:13:38uh with the correct number of uh
0:13:41permutation matches
0:13:43and uh
0:13:44for the M this there's there's a uh
0:13:47uh
0:13:47a a a a steeper improvement
0:13:49between only looking at within region two
0:13:53looking at across region
0:13:58a in conclusion oh O
0:14:00we pose the group
0:14:01uh version of the you side for this problem orthogonal cycle is problem
0:14:04uh we write an algorithm that's come to fit efficient given D givens rotations
0:14:09um
0:14:11and uh a simple to implement
0:14:13and
0:14:14there's results show that uh
0:14:16effectively you
0:14:18utilizing both within group but across group structure
0:14:21allows as to
0:14:22the estimation
0:14:23of the
0:14:24um and known
0:14:26orthogonal transformation
0:14:31thanks
0:14:34i
0:14:36sure
0:14:39yeah
0:14:40i i to los the obvious question is what can you say that convergence of the skein
0:14:49i would say that um
0:14:51that
0:14:52there are probably
0:14:54local minima
0:14:55given given
0:14:56given the constraints and so
0:14:59the key starting from that that
0:15:01that good initial
0:15:02and and the initial point
0:15:04so
0:15:05um
0:15:07more than that
0:15:08uh i can say
0:15:13no
0:15:14no