Shape Matching and Mapping using Semidefinite Programming

Dec 7

Monday, December 7, 2015

12:00 pm - 1:00 pm
Physics 119


Shahar Kovalsky (Weizmann Institute)

Geometric problems - such as finding corresponding points over a collection of shapes, or computing shape deformation under geometric constraints - pose various computational challenges. I will show that despite the very different nature of these two highly non-convex problems, Semidefinite Programming (SDP) can be leveraged to provide a tight convex approximation in both cases. A different approach is used for each problem, demonstrating the versatility of SDP: (i) For establishing point correspondences between shapes, we devise an SDP relaxation. I will show it is a hybrid of the popular spectral and doubly-stochastic relaxations, and is in fact tighter than both. (ii) For the computation of piecewise-linear mappings, we introduce a family of maximal SDP restrictions. Solving a sequence of such SDPs enables the optimization of functionals and constraints expressed in terms of singular values, which naturally model various geometry processing problems.