3:30 pm Tuesday, October 27, 2015
ICES Seminar: Robust map synchronization via constrained matrix optimization by Qixing Huang (Toyota Technological Institute, Chicago) in POB 6.304
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. Submitted by
|
|