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.
Speaker Biography
Shahar Kovalsky is a PhD student in the department of Computer Science and Applied Math at the Weizmann Institute of Science, Israel. His main research interests are in numerical optimization, computer graphics and vision, and in particular, applications of convex optimization to geometry processing. Shahar holds a B.Sc. in Mathematics and B.Sc. and M.Sc. in Electrical Engineering from Ben-Gurion University.