  Observations depending on sums of random variables are common throughout many
fields; however, no efficient solution is currently known for performing
max-product inference on these sums of general discrete distributions
(max-product inference can be used to obtain maximum a posteriori estimates).
The limiting step to max-product inference is the max-convolution problem
(sometimes presented in log-transformed form and denoted as "infimal
convolution", "min-convolution", or "convolution on the tropical semiring"),
for which no O(k log(k)) method is currently known. Here I present a O(k
log(k)) numerical method for estimating the max-convolution of two nonnegative
vectors (e.g., two probability mass functions), where k is the length of the
larger vector. This numerical max-convolution method is then demonstrated by
performing fast max-product inference on a convolution tree, a data structure
for performing fast inference given information on the sum of n discrete random
variables in O(n k log(n k) log(n) ) steps (where each random variable has an
arbitrary prior distribution on k contiguous possible states). The numerical
max-convolution method can be applied to specialized classes of hidden Markov
models to reduce the runtime of computing the Viterbi path from n k^2 to n k
log(k), and has potential application to the all-pairs shortest paths problem.
