Fast Inference with Min-Sum Matrix Product

Pedro F. Felzenszwalb; Julian J. McAuley. 30 August, 2010.
Communicated by Pedro Felzenszwalb.


The MAP inference problem in many graphical models can be solved efficiently using a fast algorithm for computing min-sum products of n by n matrices. Although the worst-case complexity of the min-sum product operation is not known to be much better than O(n^3), an O(n^{2.5}) expected time algorithm was recently given, subject to some constraints on the input matrices. In this paper we give an algorithm that runs in O(n^2 \log n) expected time, assuming the entries in the input matrices are independent samples from a uniform distribution. We also show that two variants of our algorithm are quite fast for inputs that arise in several applications. This leads to significant performance gains over previous inference methods in applications within computer vision and natural language processing.

Original Document

The original document is available in PDF (uploaded 30 August, 2010 by Pedro Felzenszwalb).