Fast Inference with Min-Sum Matrix Product
Authors:
- 9 June 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 33 (12) , 2549-2554
Abstract
The MAP inference problem in many graphical models can be solved efficiently using a fast algorithm for computing min-sum products of n × n matrices. The class of models in question includes cyclic and skip-chain models that arise in many applications. Although the worst-case complexity of the min-sum product operation is not known to be much better than O(n3), an O(n2.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(n2 log n) expected time, assuming that 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 methods in applications within computer vision and natural language processing.Keywords
This publication has 19 references indexed in Scilit:
- More algorithms for all-pairs shortest paths in weighted graphs2007
- Predicting 3D People from 2D Pictures2006
- Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images2002
- Fast approximate energy minimization via graph cutsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- The generalized distributive lawIEEE Transactions on Information Theory, 2000
- Graphical templates for model registrationIEEE Transactions on Pattern Analysis and Machine Intelligence, 1996
- Using dynamic programming for solving variational problems in visionIEEE Transactions on Pattern Analysis and Machine Intelligence, 1990
- A generalization of Dijkstra's algorithmInformation Processing Letters, 1977
- General context-free recognition in less than cubic timeJournal of Computer and System Sciences, 1975
- Gaussian elimination is not optimalNumerische Mathematik, 1969