Past Event: Oden Institute Seminar

Robust map synchronization via constrained matrix optimization

Qixing Huang, Toyota Technological Institute, Chicago

Abstract

Establishing maps (e.g., point-wise correspondences or transformations) among multiple objects is connected to a wide range of scientific problems, including fusing partially overlapped range scans, structure from motion using internet images, re-assembling fractured objects, analyzing/organizing image/shape collections, and multiple sequence/network alignment. So far most existing methods have focused on matching pairs of objects in isolation. However, due to limited information presented between pairs of objects, there exists a significant gap between what state-of-the-art pair-wise methods produce and what is required in various applications. In contrast to pair-wise methods, a recent interest in map computation is to solve the so-called map synchronization problem. The key principle is to utilize a generic cycle-consistency constraint among maps, e.g., composite maps along cycles are identity maps, to improve pair-wise maps. Several empirical studies have shown the potential of map synchronization in various applications. Yet the theoretical understanding of this problem remains limited. In this talk, we will present an optimization framework for map synchronization. The key idea is to establish the equivalence between cycle-consistency of maps and low-rank and/or SDP properties of the matrix that encodes pair-wise maps in blocks. This leads to a constrained matrix optimization formulation for map synchronization. We study both convex and non-convex techniques for optimization, and analyze exact and stable recovery conditions in both cases. We also demonstrate the effectiveness of this new formulation in several applications. Bio: Qixing Huang is a research assistant professor at TTIC. He obtained his PhD in Computer Science from Stanford University. He received his MS and BS in Computer Science from Tsinghua University. He has also interned at Google Street, Google Research and Adobe research. Dr. Huang’s research spans computer vision, computer graphics and machine learning. In particular, he is interested in designing algorithms that process big geometric data (e.g., 3D shapes/scenes) and utilize big geometric data to solve core problems in computer graphics and computer vision. He is also interested in statistical data analysis, compressive sensing, low-rank matrix recovery, and large-scale optimization, which provides theoretical foundation for much of his research. He receives the best paper award at Symposium on Geometry Processing 2013.