At first glance, data compression and optimal transport appear to belong to entirely different mathematical worlds. Data compression—governed by Shannon’s Rate-Distortion (RD) theory—asks a fundamental question: How many bits must we store to reconstruct a source signal within an acceptable level of distortion? Optimal transport (OT), on the other hand, asks a geometric question: What is the most efficient way to move mass from one probability distribution to another given a specific transport cost?
A powerful realization has emerged across information theory and machine learning: lossy data compression is mathematically equivalent to an entropy-regularized optimal transport problem. By viewing compression through a geometric lens, researchers have unlocked faster algorithms, tighter theoretical bounds, and new ways to compress data without destroying its underlying statistical structure.
Two Sides of the Same Coin
To understand why this connection works, consider what a lossy compression scheme actually does. An encoder takes a source sample $X$ (drawn from a distribution $P_X$) and maps it to a compressed representation $\hat{X}$. Because the compression is lossy, this mapping is often stochastic, defined by a conditional probability $P_{\hat{X}|X}$. Together, the source distribution and the compression mapping form a joint distribution, or a coupling, between the original data and its reproduction.
In the language of information theory, we want to choose this coupling to minimize the expected distortion $\mathbb{E}[d(X, \hat{X})]$, subject to a constraint on the mutual information $I(X; \hat{X}) \le R$, which represents our bit budget.
In the language of optimal transport, this coupling is a transport plan. The distortion function $d(X, \hat{X})$ acts exactly like the transport cost. The mutual information constraint—which penalizes the statistical dependence between $X$ and $\hat{X}$—acts precisely like the entropic regularization term used in modern, computationally efficient optimal transport.
As shown by Lei et al., classic problems like scalar quantization are fundamentally equivalent to minimizing the Earth Mover’s Distance (Wasserstein distance) between a continuous source distribution and a discrete target distribution made of a fixed number of points, or "atoms."
The Extremal Twist and Computational Superpowers
If rate-distortion and entropic optimal transport are so similar, what sets them apart? The key distinction lies in the constraints on the target distribution.
In standard optimal transport, both the source distribution $P_X$ and the target distribution $P_Y$ are fixed in advance. You are simply finding the best way to route mass between two known shapes. In rate-distortion theory, however, the target reproduction distribution $P_{\hat{X}}$ is unknown; it is a free variable that we optimize over to achieve the best possible compression.
Lei et al. proved that the rate-distortion function is an extremal version of entropic optimal transport, where the transport plan and the target marginal are optimized simultaneously.
Standard Entropic OT: Fix Source (Px) ──> Fix Target (Py) [Optimize Transport Plan]
Rate-Distortion Theory: Fix Source (Px) ──> Free Target (P_X̂) [Optimize Plan AND Target]
This formulation yields a massive computational advantage. Historically, calculating the fundamental limits of a compression system required the Blahut-Arimoto algorithm, an iterative optimization technique that scales poorly to high dimensions and struggles when the underlying optimization landscapes contain non-concave segments.
By reframing the problem as entropic optimal transport, researchers can exploit highly parallelizable transport solvers. Wu et al. introduced the CommOT framework, which represents the unknown reproduction distribution using "slackness variables." This allows the rate-distortion problem to be solved via a novel Alternating Sinkhorn algorithm, achieving speedups of 10x to 18x over traditional methods.
Similarly, Chen et al. leveraged a Generalized Alternating Sinkhorn algorithm to map out the entire trade-off curve of the Information Bottleneck problem, successfully navigating non-concave segments where traditional algorithms fail.
When dealing with continuous distributions where neural networks are typically required, Yang et al. demonstrated that the rate-distortion function can be estimated by treating the reproduction distribution as a cloud of moving particles optimized via Wasserstein Gradient Descent. This neural-network-free approach yields tighter bounds and converges up to 100x faster than deep learning alternatives.
Preserving Geometry under Distribution Shifts
Standard lossy compression algorithms minimize average distortion (like Mean Squared Error), which frequently results in blurry reconstructions or "statistical warping." For example, a highly compressed image of a grassy field might preserve the overall green color but completely smooth away the texture of the grass. This happens because the compression scheme forces the output to an average state rather than preserving the true geometric distribution of the data.
By framing compression as optimal transport, we can explicitly force the compressed output to adhere to a specific target probability distribution. Saldı et al. established a rigorous mathematical framework for this concept, proving that optimal quantizers with strict output distribution constraints exist and obey fundamental "output-constrained" rate-distortion limits. This ensures that the compressed data retains its original perceptual characteristics or texture.
This distribution-preserving property is essential when compression is paired with generative modeling or signal restoration (such as denoising or super-resolution). Liu et al. modeled simultaneous compression and restoration as an entropy-constrained optimal transport problem. By treating the bit-rate limit as a constraint on the transport plan between a degraded source distribution and a clean target distribution, the authors established the fundamental mathematical limits of restoring data while compressing it.
Degraded Source (Px) ──[Entropy-Constrained Transport Plan]──> Clean Reconstruction (Py)
│
(Bit-Rate Constraint)
This concept extends naturally to machine-to-machine communication. In modern AI pipelines, an image might be compressed not for human viewing, but for a downstream computer vision model. Nguyen et al. developed a framework for cross-domain lossy compression that uses constrained optimal transport to simultaneously optimize three competing objectives: the transmission bit-rate, the reconstruction fidelity, and the downstream task utility (such as classification accuracy).
Bounding Information with Geometric Distance
The marriage of information theory and optimal transport also provides deep theoretical tools for proving bounds on channel capacities and entropy.
Traditional information theory relies heavily on the Kullback-Leibler (KL) divergence to measure the distance between distributions. However, KL divergence is notoriously sensitive to local fluctuations and becomes infinite if two distributions do not share the same mathematical support. The Wasserstein distance (the objective function of optimal transport) is far more robust because it incorporates the underlying geometry of the space, measuring how far mass must be moved rather than just comparing density values point-by-point.
By using transportation-information inequalities (such as Talagrand's inequality), researchers can translate geometric Wasserstein distances into rigorous bounds on entropy:
- Continuity of Entropy: A long-standing challenge in multi-user communication was proving whether a small change in a signal causes a small change in its differential entropy. Polyanskiy et al. settled this by proving the Wasserstein continuity of entropy, showing that differential entropy is stable under small Wasserstein perturbations. This geometric stability allowed them to solve open capacity problems for multi-user interference channels.
- Tighter Channel Bounds: When calculating the capacity of complex communication networks, traditional "genie-aided" proofs often provide loose bounds. Yang et al. applied quadratic Wasserstein distances to establish uniformly tighter outer bounds for state-dependent Gaussian multiple access channels where inputs and noise are dependent but uncorrelated.
- Mismatched Decoding: In practical communications, a receiver might not perfectly know the channel characteristics, a scenario known as mismatched decoding. Ye et al. showed that calculating the information-theoretic lower bound for these channels (the LM rate) can be reformulated as an optimal transport problem, enabling specialized transport solvers to estimate channel capacity over 100x faster than standard optimization toolboxes.
- Downstream Estimation Risk: When data is compressed before the final estimation task is known, a system incurs "compress-and-estimate" risk. Kipnis demonstrated that if the rate-distortion achieving distribution satisfies a transportation-cost inequality, this practical risk converges directly to the theoretical rate-distortion limit, proving that transport-based constraints guarantee robustness across unknown downstream tasks.
Even the physical limits of computing fall under this umbrella. Erasing a bit of information inevitably dissipates a small amount of heat, a fact known as Landauer's principle. By using Wasserstein distances to quantify the divergence between probability states in finite time, Melbourne et al. bridged non-equilibrium thermodynamics and optimal transport to derive refined energy dissipation bounds for real-world, finite-time computing systems.
Ultimately, treating rate-distortion theory as entropic optimal transport reveals that compression is not merely about removing redundancy. It is the geometric science of moving probability mass as efficiently as possible under an information bottleneck.
Key Foundational Work
Randomized Quantization and Source Coding With Constrained Output Distribution (2014) — contributed 3 concept elements to this direction.
Learning Probability Measures with respect to Optimal Transport Metrics (2012) — contributed 1 concept elements to this direction.