Multi-Perspective, Simultaneous Embedding and Theoretically Guaranteed Projected Power Method for the Multi-way Matching Problem

Tuesday, September 29, 2020 - 1:25pm - 2:25pm
Vahan Huroyan (University of Arizona)

We address two important subproblems of Structure from Motion Problem. The first subproblem is known as Multi-way Matching, where the input includes multiple sets, with the same number of objects and noisy measurements of fixed one-to-one correspondence maps between the objects of each pair of sets. Given only noisy measurements of the mutual correspondences, the Multi-way Matching problem asks to recover the correspondence maps between pairs of them. The desired output includes the original fixed correspondence maps between all pairs of sets. The second subproblem is called Multi-Perspective Simultaneous Embedding (MPSE). The input for MPSE assumes a set of pairwise distance matrices defined on the same set of objects and possibly along with the same number of projection operators. MPSE embeds points in 3D so that the pairwise distances are preserved under the corresponding projections. Our proposed algorithm for Multi-way Matching problem iteratively solves the associated non-convex optimization problem. We prove that for a specific noise model, if the initial point of our proposed iterative algorithm is good enough, the algorithm linearly converges to the unique solution. Numerical experiments demonstrate that our method is much faster and more accurate than the state-of-the-art methods. For MPSE, we propose a heuristic algorithm and provide an extensive quantitative evaluation with datasets of different sizes, as well as several examples that illustrate the quality of the resulting solutions.

I received my PhD in mathematics from the University of Minnesota in 2018, under the supervision of my advisor Prof. Gilad Lerman. Since 2018, I've been working as a Postdoctoral Research Associate at the Department of Mathematics of the University of Arizona.