🔢 mathematics

Lossy Compression, Realism, and Coordination

This paper provides an accessible overview of the rate-distortion-perception trade-off in lossy compression and reveals its deep theoretical connections to distributed coordination under rate-limited communication, demonstrating that both problems share identical information-theoretic characterizations, reliance on common randomness, and analytical tools while proposing to transfer emerging realism paradigms to the coordination domain.

Original authors: Yassine Hamdi, Deniz Gündüz

Published 2026-08-13

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Yassine Hamdi, Deniz Gündüz

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 secret message to a friend using a walkie-talkie that only has a tiny bit of battery left. You can't say everything, so you have to leave out some details. This is the heart of lossy compression: the art of throwing away information you think isn't important so you can send the rest quickly. For decades, scientists have used a rulebook called "rate-distortion theory" to figure out the perfect balance. The rule was simple: keep the message as close to the original as possible. If you were sending a photo, you wanted the pixels to match the original exactly.

But here's the catch: sometimes, when you follow the rules too strictly to save space, the photo looks weird. It might be blurry, the colors might look flat, or the textures might look like plastic. It's technically "close" to the original, but it doesn't feel real. This is where a new idea called realism comes in. Instead of asking, "Is this pixel exactly the same as the one before?", we ask, "Does this look like a real photo?" This is like trying to draw a picture of a cat. If you draw a perfect circle for a head, it's mathematically close to a real cat's head, but it looks like a balloon. If you draw a fluffy, slightly imperfect shape, it might not match the original cat's exact lines, but it looks like a cat.

The paper you are about to read explores this tension between being mathematically accurate and looking natural. It also discovers a surprising secret: the math needed to make a photo look real is almost identical to the math needed to get two robots to work together without talking much. It turns out that teaching a computer to "fake" a realistic image and teaching two drones to "coordinate" their flight paths are actually two sides of the same coin.

The Great Realism Heist: When Faking It Is Better Than Copying It

For a long time, the goal of compression was to be a perfect photocopy machine. If you had a photo of a sunset, the computer's job was to shrink the file size and then rebuild the photo so every single pixel matched the original. The problem? To save space, the computer often had to smooth out the rough edges. The result was a sunset that looked like a watercolor painting that had been left in the rain—technically the right colors, but blurry and lifeless.

The authors of this paper, Yassine Hamdi and Deniz Gündüz, argue that we need a new goal. Instead of trying to copy the exact pixels, we should try to copy the vibe. They call this realism. A realistic reconstruction doesn't have to match the original pixel-for-pixel; it just has to look like it could have been a real photo. If you showed a realistic reconstruction to a human, they shouldn't be able to tell the difference between it and a genuine photo.

To do this, the paper introduces a three-way tug-of-war called the Rate-Distortion-Perception (RDP) trade-off.

Rate: How many bits (words) you are allowed to send.
Distortion: How different the new image is from the old one.
Perception: How "real" the new image looks.

The big surprise is that you can't have it all. If you demand a photo that looks super realistic (high perception), you often have to accept that it will be a bit different from the original (higher distortion). It's like a chef trying to make a dish that tastes exactly like a famous restaurant's meal. If they use the exact same ingredients (low distortion), they might run out of money (high rate). If they use cheap ingredients to save money (low rate), the taste might be off. But if they want it to taste exactly like the real thing (high perception), they might have to use a secret spice that changes the recipe slightly, making it technically different but deliciously real.

The Robot Dance: A Surprising Twin

Here is where the story gets really wild. The authors realized that this problem of making a "realistic" fake image is mathematically the same as a problem called distributed coordination.

Imagine two drones flying in a forest. They need to work together to cover the whole area, but they can only send each other very short text messages. They can't send a full map. So, Drone A has to send a tiny code to Drone B, and Drone B has to decide where to fly next. The goal is for them to coordinate perfectly so they don't crash into each other and cover the most ground.

The paper shows that the math for making the drones coordinate is nearly identical to the math for making a realistic image.

In the image problem: You want the output (the fake photo) to look like it came from a real camera.
In the drone problem: You want the output (Drone B's flight path) to look like it was planned to match Drone A's path.

The authors found that if you swap the words in the math equations, the two problems are twins. In the image problem, you are trying to match the distribution of the output to the source. In the drone problem, you are trying to match the joint distribution of the input and output to a target plan. It's like realizing that the recipe for baking a perfect cake is the same as the recipe for building a perfect bridge, just with different ingredients.

The Secret Ingredient: Common Randomness

There is one more twist. To make these realistic images or coordinated drones work perfectly, you need something called Common Randomness (CR).

Think of CR as a secret codebook that both the sender and the receiver have before they even start talking. It's like if two spies agreed on a random number generator before they met. When the sender wants to send a message, they use this shared randomness to pick a specific "fake" image or flight path that looks real.

The paper proves that without this shared randomness, you simply cannot achieve the highest level of realism or coordination. You need a huge amount of this shared secret data. In fact, the math suggests that the amount of shared randomness you need might be much larger than the message you are actually sending. It's like needing a library of random numbers just to send a single text message that says "Go left."

This explains a puzzle in the real world: Why don't the AI image generators we use today seem to need massive shared secret codes? The paper suggests that maybe the way we currently measure "realism" isn't strict enough. If we only check a few images at a time, we don't need the secret code. But if we check a huge batch of images all at once to see if they look real, then the secret code becomes absolutely necessary.

What This Means for the Future

The paper doesn't just solve a math puzzle; it opens a door to new ideas. Because the two problems (making real images and coordinating robots) are so similar, scientists can use the tools they built for one to solve the other.

For example, the paper suggests using a new way to test realism called batched critics. Instead of looking at one image and saying, "Does this look real?", you look at a whole batch of images at once. If you look at enough of them, you can catch patterns that a single image hides. The authors suggest that we can use this same idea for the drones: instead of just checking if two drones are coordinated once, check if their whole history of movements looks coordinated.

The paper concludes that this connection is a goldmine. By understanding that "faking reality" and "coordinating actions" are the same game, we can invent better compression systems for our phones and smarter, more efficient ways for robots to work together. It's a reminder that in science, sometimes the most useful discoveries come from realizing that two things you thought were totally different are actually best friends.

Technical Summary: Lossy Compression, Realism, and Coordination

Problem Statement
Classical rate-distortion theory, established by Shannon, characterizes the fundamental limits of lossy compression by minimizing a distortion function (e.g., Mean Squared Error) between a source and its reconstruction. However, minimizing distortion often yields reconstructions that are perceptually unsatisfying—characterized by blurriness, over-smoothed textures, and unnatural artifacts—particularly at low bit rates. This discrepancy has motivated the study of compression under realism constraints, where the goal is not merely to be close to the source in a point-wise metric, but to produce reconstructions that are statistically indistinguishable from natural signals.

This paper addresses the Rate-Distortion-Perception (RDP) trade-off, which posits that achieving high perceptual quality (realism) generally requires introducing distortion beyond the minimum achievable at a given rate. Furthermore, the paper investigates the deep structural connections between RDP problems and distributed coordination (specifically channel synthesis), where agents must coordinate actions under rate-limited communication to match a target joint distribution.

Methodology and Framework
The authors develop a unified mathematical formalism that encompasses classical rate-distortion theory, the RDP trade-off, and distributed coordination as special cases. The framework is built on a point-to-point communication system (extended to remote sources and side information) involving an encoder and a decoder that may utilize Common Randomness (CR).

Key methodological components include:

Constraint Taxonomy: The paper categorizes constraints into:
- Distortion Constraints: Parametric constraints on the expected point-wise difference (e.g., $E[d(X, Y)] \le \lambda$ ).
- Realism/Coordination Constraints: Distributional constraints requiring the induced distribution of the output (or joint input-output) to match a target distribution. These are further divided into Strong (matching the full sequence distribution), Per-Symbol (matching marginals), and Empirical (matching empirical statistics).
- Realization-Based Constraints (Batched Critics): A newer paradigm where a "critic" function evaluates a batch of $B_n$ samples. This interpolates between single-sample evaluation and full distributional matching.
Stochastic Mappings: Unlike classical theory where deterministic codes suffice, the analysis of strong distribution matching constraints necessitates randomized encoders and decoders. The role of CR (shared random seeds) is central to the analysis.
Analytical Tools: The proofs for achievable regions rely heavily on the Soft Covering Lemma and the Likelihood Encoder technique, which ensure that random codebook selection induces the desired output distribution.

Key Contributions and Results
The paper's primary contribution is revealing that RDP with strong realism constraints and distributed coordination (channel synthesis) are two manifestations of the same underlying information-theoretic phenomenon: inducing a target probability distribution through rate-limited communication.

Structural Parallels: The authors demonstrate that the achievable regions for RDP and channel synthesis are nearly identical. The only substantive difference is the substitution of the output variable $Y$ with the joint pair $(X, Y)$ .
- RDP (Strong Realism): Requires the marginal distribution $p_Y$ to match the source $p_X$ .
- Channel Synthesis: Requires the joint distribution $p_{X,Y}$ to match a target $q_{X,Y}$ .
- Consequently, the achievable rate regions differ only by this substitution (e.g., $R + R_c \ge I(Y; V)$ vs. $R + R_c \ge I(X, Y; V)$ ).
The Necessity of Common Randomness (CR):
- For strong distribution matching (where the target distribution must be matched exactly, $\lambda=0$ ), deterministic codes are insufficient because they cannot generate output entropy exceeding the input message entropy.
- Optimal performance requires CR. The paper derives expressions for the minimum CR rate ( $R_c$ ) needed to achieve the minimum compression rate ( $R$ ).
- A critical finding is that in the lossy compression regime ( $R \ll H(X)$ ), the required CR rate can far exceed the communication rate ( $R_c \gg R$ ). This theoretical prediction contrasts with practical neural codecs, which do not explicitly report large CR requirements.
Extensions to Complex Scenarios: The parallel holds for Remote Source Compression (where the encoder observes a noisy version of the source) and Compression with Side Information. In these cases, the achievable regions for RDP and coordination remain structurally analogous, with the joint distribution constraints appropriately modified.
Algorithmic Realism and Batched Critics:
- The paper surveys recent work on algorithmic realism, which uses a family of computationally bounded tests (critics) to define realism.
- A key result from [10] is that if the batch size $B_n$ of the critics does not grow exponentially with the blocklength $n$ , deterministic schemes can achieve the optimal trade-off, and CR is not required.
- Only when $B_n$ grows sufficiently large (effectively inspecting the full distribution) does the problem revert to the strong distribution matching case, necessitating CR. This offers a potential resolution to the "CR puzzle" in practical codecs.

Significance and Claims
The paper claims that the connection between perceptual compression and distributed coordination is not merely aesthetic but concretely productive.

Unification: It provides a unified language for understanding fundamental limits across compression and coordination, suggesting that insights from one domain can directly inform the other.
Generative Insight: The transfer of proof structures (e.g., using channel synthesis proofs to characterize the role of CR in RDP) has already yielded new characterizations for RDP problems with side information.
New Research Directions: The paper proposes transferring the paradigm of batched critics from the RDP domain to coordination theory. This suggests a new class of coordination problems where the requirement for CR depends on the "batch size" of the coordination test, potentially bridging the gap between empirical coordination (which often suffices with deterministic codes) and strong coordination.

The authors conclude that as AI systems increasingly involve multiple interacting agents, the theory of distributed coordination, linked here to compression theory, offers a principled framework for understanding fundamental limits under communication constraints. The paper positions itself as a reference for researchers at the intersection of lossy compression, distributed coordination, and generative modeling.

The Great Realism Heist: When Faking It Is Better Than Copying It

The Robot Dance: A Surprising Twin

The Secret Ingredient: Common Randomness

What This Means for the Future

More like this