Quantization of Probability Distributions via Divide-and-Conquer: Convergence and Error Propagation under Distributional Arithmetic Operations

2025/05/21 by Bilgesu A. Bilgin, Olof Elias, Bilgin, Bilgesu Arif +5 · 4 citations
Computer Science · #Computational Engineering #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Finance #Numerical Analysis (math.NA) #Probability (math.PR) #and Science (cs.CE)

paper · pdf · doi:10.48550/arxiv.2505.15283

openalex publication_date 2025/05/21 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

This article studies a general divide-and-conquer algorithm for approximating continuous one-dimensional probability distributions with finite mean. The article presents a numerical study that compares pre-existing approximation schemes with a special focus on the stability of the discrete approximations when they undergo arithmetic operations. The main results are a simple upper bound of the approximation error in terms of the Wasserstein-1 distance that is valid for all continuous distributions with finite mean. In many use-cases, the studied method achieve optimal rate of convergence, and numerical experiments show that the algorithm is more stable than pre-existing approximation schemes in the context of arithmetic operations.

Citations

• Optimal estimation of high-dimensional location Gaussian mixtures
• Optimal estimation of Gaussian mixtures via denoised method of moments
• What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?
• Uncertainty propagation with functionally correlated quantities
• Convex optimization

Cited by

• Approximating Analytically-Intractable Likelihood Densities with Deterministic Arithmetic for Optimal Particle Filtering
• Efficient Digital Methods to Quantify Sensor Output Uncertainty
• A Tensor Train Approach for Deterministic Arithmetic Operations on Discrete Representations of Probability Distributions
• Dynamic Online Processor-Native Inference for State Estimation

Related

• Quantization for a set of discrete distributions on the set of natural numbers
• Uniform decomposition of probability measures: quantization, classification, rate of convergence
• Optimal quantization for nonuniform discrete distributions
• discretize_distributions: Efficient Quantization of Gaussian Mixtures with Guarantees in Wasserstein Distance
• Quantization of Discrete Probability Distributions