A Tensor Train Approach for Deterministic Arithmetic Operations on Discrete Representations of Probability Distributions

Computing with discrete representations of high-dimensional probability distributions is fundamental to uncertainty quantification, Bayesian inference, and stochastic modeling. However, storing and manipulating such distributions suffers from the curse of dimensionality, as memory and computational costs grow exponentially with the number of input distributions. Typical workarounds using Monte Carlo methods with thousands to billions of samples incur high computational costs and produce inconsistent results due to stochasticity. We present an efficient tensor train method for performing exact arithmetic operations on discretizations of continuous probability distributions while avoiding exponential growth in the representation size. Our approach leverages a low-rank tensor train decomposition to represent latent random variables compactly using Dirac deltas, enabling deterministic addition, subtraction and multiplication operations directly in the compressed format. Additionally, we present an efficient implementation strategy based on sparse matrices and specialized data structures that further enhances computational performance. We have designed the representation and distribution arithmetic methods to enable implementation within a general-purpose microprocessor or specialized hardware accelerator.

This article presents theoretical analyses of the memory and computational complexity for common operations that show polynomial scaling under rank assumptions and illustrates how several statistics of the latent variable can be computed in polynomial memory and complexity. Numerical experiments on problems from randomized numerical linear algebra to stochastic differential equations with financial applications demonstrate orders-of-magnitude improvements in memory usage and computational time compared to conventional approaches, enabling tractable deterministic computations on discretized random variables in previously intractable dimensions.