🔢 mathematics

Cross-Domain Lossy Compression via Constrained Minimum Entropy Coupling

This paper proposes a cross-domain lossy compression framework based on constrained minimum entropy coupling that maximizes source-reconstruction coupling strength under rate and classification constraints, demonstrating through both theoretical analysis and neural experiments that higher rates improve classification accuracy and reconstruction quality.

Original authors: Nam Nguyen, Hassan Tavakoli, An Vuong, Thinh Nguyen, Bella Bose

Published 2026-05-12

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Nam Nguyen, Hassan Tavakoli, An Vuong, Thinh Nguyen, Bella Bose

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a blurry, noisy photo of a cat to a friend. Your friend, however, has a very specific rule: they only want to receive photos that look like they belong in a high-quality, professional art gallery (a specific "target distribution"). Furthermore, your friend needs to be able to tell if the animal in the photo is a cat or a dog (a "classification task").

The problem is that you have a limited bandwidth (a "rate constraint"). You can't send the whole high-definition original file. You have to compress it, but you can't just send a tiny, blurry blob because it won't look like the art gallery photos, and your friend won't be able to tell what it is.

This paper proposes a new way to solve this puzzle. Instead of trying to make the blurry photo look exactly like the original pixel-by-pixel (which is the old way of doing things), the authors use a concept called Minimum Entropy Coupling.

Here is the breakdown using simple analogies:

1. The Old Way vs. The New Way

The Old Way (Pixel Matching): Imagine trying to copy a painting by matching every single brushstroke exactly. If you miss one, the picture is "wrong." This is like measuring error by how different the pixels are (Mean Squared Error).
The New Way (The "Coupling" Dance): The authors suggest a different approach. Imagine you and your friend are dancing. You have a specific rhythm (the noisy source), and your friend has a specific rhythm they want to hear (the clean target). The goal isn't to copy your friend's steps perfectly; it's to find a dance partner (the compressed data) that allows you to move in sync with your friend as much as possible, while still following your own rhythm.
- They call this maximizing the "coupling strength." It's about how much information about the original noisy photo is preserved in the final clean photo, even if the pixels aren't identical.

2. The Three Rules of the Game

The paper sets up a game with three strict rules:

The Rate Limit: You can only send a small amount of data (like a postcard instead of a full album).
The Look: The final image must look like it belongs to the "art gallery" style (the target distribution). It can't just be a random noise pattern.
The Meaning: The final image must still be clear enough that a computer (or your friend) can correctly guess what the object is (e.g., "That is a cat").

3. The Magic Trick: Common Randomness

The authors discovered a mathematical trick to make this work better. Imagine you and your friend both have a secret, shared deck of cards (called Common Randomness).

When you see the blurry photo, you look at a card from your deck.
Based on the photo and that specific card, you decide how to compress the image.
Your friend, seeing the compressed image and holding the same card from their deck, knows exactly how to reconstruct the high-quality image.

The paper proves that you don't need a complex, middle-man "intermediate" step. You can go straight from "Noisy Photo + Secret Card" to "Clean Photo." This simplifies the math and makes the system more efficient.

4. The Results: What Happens When You Send More Data?

The authors tested this on two famous image datasets:

MNIST: Turning tiny, blurry handwritten numbers into big, clear ones (Super-resolution).
SVHN: Cleaning up noisy photos of house numbers (Denoising).

The Findings:

More Bandwidth = Better Guessing: As they allowed more data to be sent (increasing the "rate"), the computer got much better at identifying the numbers or objects.
More Bandwidth = Better Pictures: The reconstructed images looked more realistic and kept more of the original details.
The Trade-off: If you send very little data, the system prioritizes making sure the image looks like the target style and that the object is identifiable, even if some fine details are lost.

Summary

In short, this paper introduces a new rulebook for compressing images. Instead of trying to copy a picture perfectly, it tries to link a bad picture to a good one using a shared secret code. This ensures that even when the file size is small, the image still looks the right way and tells the right story (e.g., "This is a cat"). The math shows exactly how much data you need to send to get a specific level of clarity and accuracy.

Technical Summary: Cross-Domain Lossy Compression via Constrained Minimum Entropy Coupling

Problem Formulation

This paper investigates cross-domain lossy compression, a setting where an encoder observes samples from a degraded source distribution $p_X$ (e.g., noisy or low-resolution images) and a decoder must generate reconstructions following a distinct, prescribed target distribution $p_Y$ (e.g., clean or high-resolution images). Unlike traditional rate-distortion theory, which minimizes sample-wise distortion (e.g., MSE), this work adopts an information-theoretic objective based on logarithmic loss.

The core problem is formulated as a Rate-Constrained Minimum Entropy Coupling with Bottleneck (MEC-B). The goal is to maximize the mutual information $I(X; Y)$ between the source $X$ and the reconstruction $Y$ , subject to three constraints:

Markov Chain: $X \leftrightarrow Z \leftrightarrow Y$ , where $Z$ is an intermediate representation.
Rate Constraint: The entropy of the intermediate representation is bounded, $H(Z) \leq R$ .
Marginal Constraint: The reconstruction must strictly follow the target distribution, $P_Y = p_Y$ .

Furthermore, the paper extends this to include classification constraints, requiring the reconstruction to preserve sufficient information about a downstream label $S$ such that the conditional entropy $H(S|Y) \leq C$ .

Methodology

Theoretical Framework

The authors approach the problem through the lens of Minimum Entropy Coupling (MEC). Since marginal entropies are fixed, maximizing mutual information $I(X; Y)$ is equivalent to minimizing the joint entropy $H(X, Y)$ .

Common Randomness and Deterministic Reduction:
The paper introduces shared randomness $U$ available to both encoder and decoder. It proves (Theorem 1) that the intermediate representation $Z$ can be removed without loss of optimality. The problem reduces to finding a deterministic coupling $Y = f(X, U)$ such that the conditional entropy $H(Y|U)$ satisfies the rate constraint. This transforms the stochastic optimization into a deterministic coupling problem.
Closed-Form Solutions for Bernoulli Sources:
The authors derive closed-form expressions for the optimal mutual information in the Bernoulli case ( $X, Y \sim \text{Bern}(q)$ ):
- Without Classification Constraints (Theorem 2): The solution characterizes the tradeoff between the rate $R$ and the preservation of source information, providing explicit formulas for the optimal coupling probabilities based on the relationship between $q_X$ and $q_Y$ .
- With Classification Constraints (Theorem 3): The formulation incorporates a constraint on the residual uncertainty of a label $S$ (modeled as $S = X \oplus S_1$ ). The paper derives a piecewise closed-form solution that accounts for the interplay between the rate limit $R$ and the classification uncertainty bound $C$ . It establishes feasibility conditions (e.g., $C \geq H_b(q_{S1})$ ) and identifies optimal strategies based on which constraints are active.

Neural Implementation

To address practical, high-dimensional data, the authors implement a neural restoration framework based on a stochastic autoencoder architecture. The system includes:

Encoder/Decoder: Stochastic mappings $f$ and $g$ conditioned on shared randomness $U$ .
Quantization: A quantizer $Q$ to discretize the latent representation.
Entropy Modeling: A learned parametric model to estimate the compression rate $R$ .
Distribution Matching: A WGAN discriminator to enforce the target marginal $p_Y$ via the Wasserstein-1 distance.
Classification Regularization: A classifier $c$ that enforces the classification constraint by minimizing cross-entropy loss (upper-bounding $H(S|Y)$ ).
Objective: The system optimizes a variational lower bound of mutual information $I(X; Y)$ while balancing rate, distribution alignment, and classification performance.

Key Results

Theoretical Findings

Equivalence of Stochastic and Deterministic Coupling: The paper demonstrates that under common randomness, the optimal solution for the rate-constrained MEC problem can be achieved via a deterministic mapping from the source and shared randomness, eliminating the need for an explicit intermediate stochastic variable $Z$ .
Bernoulli Characterizations: The derived closed-form expressions reveal how the achievable mutual information scales with the rate $R$ and the classification constraint $C$ . Specifically, increasing the rate allows the reconstruction to preserve more information about the source while satisfying the target marginal and task constraints.

Experimental Findings

Experiments were conducted on two cross-domain tasks:

MNIST Super-Resolution: Restoring low-resolution digits to high-resolution targets.
SVHN Denoising: Removing Gaussian noise from street view house numbers.

Observations:

Rate vs. Performance: Increasing the available rate $R$ consistently improves classification accuracy and reduces cross-entropy loss for the downstream task.
Reconstruction Quality: Higher rates yield reconstructions that better preserve semantic identity (e.g., digit shape) and align more closely with the target high-resolution or clean distribution.
Limitations: At low rates, reconstructions lose fine details. The authors note that while the information-theoretic objective preserves task-relevant information, it does not uniquely determine low-level visual attributes (such as color statistics) due to the invariance of mutual information under invertible transformations. Consequently, some mild color inconsistencies were observed in denoised SVHN images.

Significance and Claims

The paper claims to provide a useful framework for distribution-constrained and task-aware compression by shifting the paradigm from sample-wise distortion to information-based coupling.

Theoretical Contribution: It extends Minimum Entropy Coupling to a rate-constrained setting with classification requirements, offering the first closed-form characterizations for Bernoulli sources under these combined constraints.
Practical Contribution: It bridges the gap between theoretical information bounds and deep learning implementations, demonstrating that a neural architecture guided by MEC principles can effectively handle cross-domain restoration tasks where the source and target distributions differ significantly.
Modest Scope: The authors position their work as an information-theoretic alternative to distortion-based frameworks (like RDP or RDC). They acknowledge that while their method maximizes task-relevant information, achieving perfect visual fidelity may require additional regularization terms beyond the mutual information objective.

The work suggests that rate- and classification-constrained MEC offers a principled approach to balancing compression efficiency, distributional fidelity, and task performance in modern generative and restoration systems.