RDD Function: A Tradeoff Between Rate and Distortion-in-Distortion

Lingyi Chen, Haoran Tang, Shitong Wu, Jiakun Liu, Huihui Wu, Wenyi Zhang, Hao Wu

This paper introduces the Rate Distortion-in-Distortion (RDD) function, a novel extension of classical rate-distortion theory. By replacing standard point-wise distortion constraints with Gromov-type structural constraints, the authors create a framework that can evaluate information processing across spaces of different dimensions or where no direct metric exists between the source and the reproduction.

TL;DR

The RDD function generalizes classical rate-distortion theory by using Gromov-type distortion to measure how well the internal relationships of a data source are preserved during compression. This allows for a formal information-theoretic treatment of scenarios where the source and compressed output live in entirely different metric spaces (e.g., different dimensions).

What Problem Does This Paper Address?

In classical Rate-Distortion (RD) theory, we aim to find the minimum bit rate required to represent a source such that the expected "distance" (distortion) between the original and the reconstruction is below a threshold. This requires a well-defined distortion measure, like Mean Squared Error, between the source space and the reproduction space.

However, this approach fails in two common modern scenarios:

  1. Dimension Mismatch: How do you measure point-wise distortion if you are compressing a 3D point cloud into a 2D representation?
  2. Unknown Correspondence: What if there is no natural way to "pair" points between the source and the output?

Existing extensions, such as the Rate-Distortion-Perception (RDP) function, address visual quality but don't solve the fundamental problem of comparing disparate geometric structures. The authors address this gap by focusing on structural consistency—ensuring that if two points are "close" in the source space, their representations are "close" in the reproduction space, regardless of the coordinate systems used.

Methods

The core of the paper is the RDD function, which uses the Gromov-Wasserstein (GW) distance as its foundation.

  • The RDD Function: Like the standard RD function, the objective is to minimize mutual information $I(X; Y)$. However, the constraint is a "Gromov-type distortion." Instead of measuring $d(x, y)$, it measures the difference between $d_X(x, x')$ and $d_Y(y, y')$.
  • Coding Theorem: The authors provide a theoretical proof (a coding theorem) showing that the RDD function isn't just a mathematical curiosity; it represents the actual operational minimum rate for real-world source coding tasks under these structural constraints.
  • AMD Algorithm: Calculating Gromov-type distortion is computationally expensive (quartic complexity, $O(N^4)$). The authors develop an Alternating Mirror Descent (AMD) algorithm. By using linearization and relaxation techniques, they reduce the complexity to cubic ($O(N^3)$), making it numerically feasible.

Datasets

The paper focuses on theoretical validation and numerical simulations rather than large-scale empirical datasets. The authors evaluate their algorithm using:

  • Synthetic Sources: Gaussian, Laplacian, and Uniform distributions.
  • Geometric Grids: Uniform 1D, 2D, and 3D grids.
  • Non-Euclidean Surfaces: Discrete distributions on a circle (2D) and a sphere (3D) to demonstrate the algorithm's flexibility across different geometries.

Key Insights and Ideas

  • Relational over Point-wise: The "aha moment" is that for many tasks, the relationships between data points are more important than their absolute coordinates. RDD captures the "intrinsic geometry" of the data.
  • Dimension Agnosticism: Because the distortion measure compares distances to distances, the source can be 10-dimensional and the output 2-dimensional. The RDD function handles this naturally.
  • Bridging Fields: The work successfully bridges Optimal Transport (specifically Gromov-Wasserstein theory) with Information Theory, providing a new tool for the "Information Bottleneck" community.
  • The RDD-RD Tradeoff: In the appendix, the authors introduce a hybrid model using a parameter $\theta$ to balance traditional point-wise distortion with structural distortion, showing that as you demand more structural consistency, the required bit rate increases.

Key Results

  • Monotonicity: Numerical results confirm that RDD curves behave similarly to classical RD curves—as you allow for more distortion, the required rate decreases monotonically.
  • Algorithm Efficiency: The AMD algorithm successfully converges for various source types and dimensions, proving that the structural distortion constraint can be handled numerically.
  • Structural Sensitivity: Experiments on spherical surfaces show that the RDD function is sensitive to the underlying geometry of the space, which traditional RD measures might overlook.

Limitations and Future Work

  • Complexity: While $O(N^3)$ is better than $O(N^4)$, it is still computationally heavy for very large-scale applications like high-resolution video compression.
  • Convexity: The authors note that it is not yet mathematically proven whether the RDD function is always convex, though numerical results suggest it behaves as if it is.
  • Practical Applications: The paper is primarily theoretical. The authors suggest future work should apply RDD to specific fields like point cloud compression, radio map representation (for wireless networks), and generative AI models where structural integrity is paramount.

Summary updated

BibTeX
@inproceedings{chen2025rdd,
  author = {Lingyi Chen and Haoran Tang and Shitong Wu and Jiakun Liu and Huihui Wu and Wenyi Zhang and Hao Wu},
  title = {{RDD Function: A Tradeoff Between Rate and Distortion-in-Distortion}},
  booktitle = {Itw},
  year = {2025},
  doi = {10.1109/itw62417.2025.11240347},
}
Figure