TR-2010-04
Fast Inference with Min-Sum Matrix Product
Pedro F. Felzenszwalb; Julian J. McAuley. 30 August, 2010.
Communicated by Pedro Felzenszwalb.
Abstract
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).
