IDeAS Seminar: Provably good convex methods for mapping problems

Speaker: 
Nadav Dym, Weizmann Institute
Date: 
Nov 8 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Computing mappings or correspondences between surfaces is an important tool for many applications in computer graphics, computer vision, medical imaging, morphology and related fields. Mappings of least angle distortion (conformal) and distance distortion (isometric) are of particular interest. The problem of finding conformal/isometric mappings between surfaces is typically formulated as a difficult non-convex optimization problem. Convex methods relax the non-convex optimization problem to a convex problem which can then be solved globally. The main issue then is whether the global solution of the convex problem is a good approximation for the original global solution. In this talk we will discuss two families of convex relaxations.

Conformal: We relax the problem of computing planar conformal mappings (Riemann mappings) to a simple convex problem which can be solved by solving a system of linear equations. We show that in this case the relaxation is exact- the solution of the convex problem is guaranteed to be the Riemann mapping!

Discrete isometric: for perfectly isometric asymmetric surfaces, the well known doubly-stochastic (DS) relaxation is exact. We generalize this result to the more challenging and important case of symmetric surfaces, once exactness is correctly defined for such problems. For non-isometric surfaces it is difficult to achieve exactness. Several relaxations have been proposed for such problems, where the more accurate relaxations are generally also more time consuming. We will describe two algorithm which strike a good balance between accuracy and efficiency: The DS++ algorithm, which is provably better than several popular algorithms but does not compromise efficiency,  and the Sinkhorn-JA algorithm, which gives a first-order algorithm for efficiently solving the strong but high-dimensional JA relaxation. We utilize this algorithmic improvement to achieve state of the art results for shape matching and image arrangement.

Nadav Dym received his Bsc and Msc degrees in mathematics from the Hebrew University.  His Msc thesis was on the topic “spatial recurrence for ergodic fractal measures “. He is currently pursuing his PhD degree in the department of computer science and applied mathematics in the Weizmann Institute, on the topic “convex methods for shape matching and related problems“ . His research interests include convex optimization, analysis and geometry and their applications.