On Solving Probabilistic Linear Diophantine Equations

Multiple methods exist for computing marginals involving a linear Diophantine constraint on random variables. Each of these extant methods has some limitation on the dimension and support or on the type of marginal computed (e.g., sum-product inference, max-product inference, maximum a posteriori, etc.). Here, we introduce the trimmed p-convolution tree an approach that generalizes the applicability of the existing methods and achieves a runtime within a log-factor or better compared to the best existing methods. A second form of trimming we call underflow/overflow trimming is introduced which aggregates events which land outside the supports for a random variable into the nearest support. Trimmed p-convolution trees with and without underflow/overflow trimming are used in different protein inference models. Then two different methods of approximating max-convolution using Cartesian product trees are introduced.

Automated summary

Various methods exist for computing marginal involving a linear Diophantine constraint on random variables, each with limitations. This study introduces a new approach, the trimmed p-convolution tree, which generalizes the applicability of existing methods and achieves better runtime. Additionally, two different methods for approximating max-convolution are introduced using Cartesian product trees.