Exact recovery with symmetries for procrustes matching

DOI10.1137/16M1078628zbMATH Open1376.90042arXiv1606.01548OpenAlexW2962954307MaRDI QIDQ5348459FDOQ5348459

Authors: Nadav Dym, Yaron Lipman 

Publication date: 16 August 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: The Procrustes matching (PM) problem is the problem of finding the optimal rigid motion and labeling of two point sets so that they are as close as possible. Both rigid and non-rigid shape matching problems can be formulated as PM problems. Recently [Maron et al.] presented a novel convex semi-definite programming relaxation (PM-SDP) for PM which achieves state of the art results on common shape matching benchmarks. In this paper we analyze the successfulness of PM-SDP in solving PM problems without noise (Exact PM problems). We begin by showing Exact PM to be computationally equivalent to the graph isomorphism problem. We demonstrate some natural theoretical properties of the relaxation, and use these properties together with the moment interpretation of [Lasserre] to show that for exact PM problems and for (generic) input shapes which are asymmetric or bilaterally symmetric, the relaxation returns a correct solution of PM. For symmetric shapes, PM has multiple solutions. The non-convex set of optimal solutions of PM is strictly contained in the convex set of optimal solutions of PM-SDP, so that `most' solutions of PM-SDP will not be solutions of PM. We deal with this by showing the solution set of PM to be the extreme points of the solution set of PM-SDP, and suggesting a random algorithm which returns a solution of PM with probability one, and returns all solutions of PM with equal probability. We also show these results can be extended to the almost-exact case. To the best of our knowledge, our work is the first to achieve exact recovery in the presence of multiple solutions.

Full work available at URL: https://arxiv.org/abs/1606.01548

Recommendations

• Exact recovery with symmetries for the doubly stochastic relaxation
• On convex relaxation of graph isomorphism
• Global registration of multiple point clouds using semidefinite programming
• Structural, Syntactic, and Statistical Pattern Recognition
• On spectral properties for graph matching and graph isomorphism problems

zbMATH Keywords

exact recoveryshape matchingsemidefinite program (SDP)global registration

Mathematics Subject Classification ID

Semidefinite programming (90C22) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites Work

• Title not available (Why is that?)
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Positive definite completions of partial Hermitian matrices
• Problems of distance geometry and convex properties of quadratic maps
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Theory of semidefinite programming for sensor network localization
• Graph isomorphism in quasipolynomial time (extended abstract)
• Phase retrieval via matrix completion
• On convex relaxation of graph isomorphism
• On spectral properties for graph matching and graph isomorphism problems

Cited In (2)

• Global registration of multiple point clouds using semidefinite programming
• Exact recovery with symmetries for the doubly stochastic relaxation

Uses Software

• YALMIP
• Mosek
• SCAPE
• PhaseLift

This page was built for publication: Exact recovery with symmetries for procrustes matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5348459)