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

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

Abstract

Classical rate-distortion theory relies on point-wise metrics that require the source and reproduction spaces to share the same dimensions and a well-defined correspondence. This paper introduces the Rate Distortion-in-Distortion (RDD) function, a novel framework that replaces standard point-wise constraints with Gromov-type structural constraints. By leveraging the Gromov-Wasserstein distance, the RDD function enables the evaluation of information processing across disparate metric spaces, providing a formal information-theoretic treatment for scenarios where traditional distortion measures fail.

Introduction

In the foundation of information theory, Rate-Distortion (RD) theory defines the fundamental limit of lossy data compression. It quantifies the minimum bit rate required to represent a source such that the expected distortion—typically measured by point-wise distances like Mean Squared Error (MSE)—remains below a specific threshold. While robust, this classical approach assumes a direct mapping between the source $X$ and the reproduction $Y$.

Modern data processing often challenges this assumption. For instance, compressing a high-dimensional 3D point cloud into a 2D representation or mapping data between spaces where no natural coordinate alignment exists makes point-wise comparison impossible. To address these gaps, this research proposes the RDD function, focusing on the preservation of internal relationships rather than absolute coordinates.

The Limitations of Classical Rate-Distortion

Classical RD theory encounters two primary obstacles in complex geometric tasks:

  1. Dimension Mismatch: If the source space $\mathcal{X}$ and reproduction space $\mathcal{Y}$ have different dimensions, a standard metric $d(x, y)$ is not naturally defined.
  2. Unknown Correspondence: In many unsupervised learning or cross-domain tasks, there is no inherent way to "pair" a point in the source with a point in the output.

While existing extensions like the Rate-Distortion-Perception (RDP) function incorporate visual quality and distribution matching, they do not resolve the fundamental geometric problem of comparing disparate structures. The RDD function solves this by ensuring structural consistency: if two points are close in the source space, their representations should remain relatively close in the reproduction space, regardless of the underlying coordinate systems.

The RDD Framework

The core innovation of this work is the application of Gromov-Wasserstein (GW) distance principles to information theory.

The RDD Function Definition

Similar to the standard RD function, the RDD objective is to minimize the mutual information $I(X; Y)$. However, the constraint is replaced by a "Gromov-type distortion." Instead of measuring the distance $d(x, y)$ between points, the function measures the discrepancy between the internal distances: $|d_X(x, x') - d_Y(y, y')|$. This allows the source and reproduction to exist in entirely different metric spaces.

The Coding Theorem

The authors establish a theoretical coding theorem, proving that the RDD function is not merely a mathematical abstraction but represents the operational minimum rate for source coding under structural constraints. This provides the necessary theoretical grounding to apply RDD to real-world communication and compression systems.

Computational Approach: The AMD Algorithm

Calculating Gromov-type distortion is computationally intensive, typically involving a quartic complexity of $O(N^4)$. To make the RDD function practically applicable, the authors developed the Alternating Mirror Descent (AMD) algorithm. By employing linearization and relaxation techniques, the AMD algorithm reduces the complexity to $O(N^3)$. This improvement allows for numerical simulations across various geometries and distributions.

Key Insights and Results

Through numerical validation on synthetic sources (Gaussian, Laplacian, Uniform) and geometric grids (1D, 2D, and 3D), the research yielded several critical insights:

  • Relational Priority: The RDD function captures the "intrinsic geometry" of data. It prioritizes the preservation of the data's shape and relational structure over absolute positioning.
  • Dimension Agnosticism: The framework naturally handles scenarios where the source is, for example, 10-dimensional and the output is 2-dimensional, as the distortion measure compares distances to distances rather than points to points.
  • Monotonicity: Numerical results confirm that RDD curves follow the expected behavior of classical RD curves—as the allowed structural distortion increases, the required bit rate decreases monotonically.
  • Structural Sensitivity: Experiments on non-Euclidean surfaces, such as discrete distributions on a sphere, demonstrate that RDD is sensitive to underlying geometry that traditional RD measures often overlook.

Conclusion and Future Work

The RDD function bridges the gap between Optimal Transport and Information Theory, offering a new lens for the Information Bottleneck community and geometric data analysis. While the $O(N^3)$ complexity remains a challenge for high-resolution applications like video compression, the framework provides a rigorous path forward for point cloud compression, radio map representation in wireless networks, and maintaining structural integrity in generative AI models.

Future research is expected to address the mathematical proof of the RDD function's convexity and explore further optimizations to bring structural rate-distortion theory into large-scale practical applications.

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