Probabilistic approach to high order assignment problems

-
Yosi Keller, Bar-Ilan University (Israel)

A variety of computer vision and engineering problems can be cast as high order matching problems, where one considers the affinity 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 a probabilistic interpretation of spectral matching and derive a new probabilistic matching scheme. We show how our approach can be extended to high order matching scheme, via a dual tensor marginalization-decomposition. Last, we present an Integer Least Squares algorithm and apply it to the decoding of MIMO channels and the solution of Suduko puzzles. Joint work with Amir Egozi, Michael Chertok and Amir Leshem