The problem of matching representations of one set of objects, e.g., their images, to representations of another set of objects that achieves an optimal global measure of overlap (goodness of match) is ubiquitous in computer science, and remains a fundamental challenge in areas such as machine learning, computer vision, and computational biology. While some cases are solvable in polynomial time, a majority of those encountered in practice are computationally intractable - NP-hard. This research will exploit the fact that in many matching problems of interest the space to be optimized over has the (algebraic) structure of group, which allows one to leverage an entire spectrum of ideas from abstract algebra, including non-commutative harmonic analysis and fast Fourier transforms on groups. In addition to yielding efficient optimization schemes in several important cases, this algebraic approach has the potential to serve as a basis for developing novel matching algorithms and suggest new approaches for certain classes of combinatorial optimization problems.
The proposed research has four main goals: to design faster general purpose harmonic analysis-based quadratic assignment problem (QAP) solvers and apply these to alignment and matching problems; to develop "tailored" QAP solution methods by coupling them to a learning component, which leverages training data to solve subsequent QAP instances much more efficiently; to design multiresolution analysis-based algorithms which yield global solutions to multi-object tracking and matching problems; and, to implement a flexible open-source library which offers a wide variety of harmonic analysis functionality (with support for wavelet and other transforms) to encourage experimentation on a broad class of inference and optimization problems. This project will yield a powerful set of algorithms and open-source software that can be used by researcher in areas of machine learning, computer vision, and optimization.
