Group-theoretic Algorithms for Matching Problems with Applications to Computer Vision

Friday, March 4, 2016 - 1:25pm - 2:25pm
Lind 305

Matching one set of objects to another is a fundamental problem in computer science. In computer vision it arises in the context of finding the correspondences between multiple images of the same scene taken from different viewpoint. In machine learning one often needs to align examples
before a meaningful similarity measure can be computed between them. These problems often reduce to some form of combinatorial search problem, various classes of which are polynomial time solvable whereas many others are NP-hard. Therefore, most successful methods take heuristic approach with no
optimality guaranteed. The fundamental difficulty in solving matching problems is that the solution space is exponential in size. In her thesis, Deepti considered a different approach for these intractable problems. She leveraged the algebraic structure of the solution of a matching problem i.e., a permutation. A permutation of order n is a candidate in the Sn, called the Symmetric Group of degree n. The high degree of regularity of the symmetric group allows us to unleash a wide range of mathematical tools on
matching problems. Her dissertation studied matching problems from the following perspectives: 1) How to take advantage of the fact that any finite group supports a notion of Fourier transformation, and hence Harmonic Analysis; 2) How to extend the notion of regularity in output space of matching problems to solve multi-way matching problem; 3) How to organize matching instances and construct meaningful metric for such data. Proposed approach is fully general and equally applicable to matching problems in
domains other than computer vision such as social networks.

Deepti Pachauri is a Research Scientist in the Advance Technology Group at 3M Corporate Research Lab since April 2015. Her research interest and 3M projects lies at the intersection of mathematics, computer vision, 3D analytics, and machine learning. Prior to 3M, she obtained PhD from the Department of Computer Sciences - University of Wisconsin Madison. In her PhD thesis, she explored the role of geometry, group theory, and statistics in matching problems that are ubiquitous in computer sciences, ranging from computer vision to networks to bioinformatics. Her thesis work was instrumental to a successful NSF award. Pachauri published in highly cited conferences including ICML, NIPS, JMLR and IEEE TMI. She has been on the program committee and reviewer for many international conferences including CVPR, ECCV, ICCV, NIPS, IJCAI, Medical Physics. Indian Institute of Technology - Delhi and the University of Wisconsin Milwaukee are her alma maters where she studied Physics.