Location: Hill 525
Date & time: Tuesday, 07 November 2017 at 3:30PM - 4:30PM
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.