Probabilistic approaches to high order assignment problems

A gamut of computer vision and engineering problems can be cast as high order matching problems, where one considers the affinity/probability of two or more assignments simultaneously. The spectral matching approach of Leordeanu and Hebert (2005) was shown to provide an approximate solution of this np-hard problem. It this talk we present recent results on the probabilistic interpretation of
spectral matching. We extend the results of Zass and Shashua (2008) and provide a probabilistic interpretation to the spectral matching and graduated assignment (1996) algorithms. We then derive a new probabilistic matching scheme, and show that it can be extended to high order matching scheme, via a dual marginalization-decomposition
scheme. We will present a novel Integer Least Squares algorithm and apply it to the decoding of MIMO and OFDM channels, in the uncoded and coded cases, respectively.