cs.LGNov 9, 2026

Pairwise distortion distribution for compression and quantization

Authors: Carl Nuzman, Jeongmin Chae, Kursat Rasim Mestav, Urbashi Mitra

Organizations: Nokia Bell Labs · Department of Electrical & Computer Engineering, University of Southern California

Abstract

Choosing the latent dimension is a critical challenge in data compression, where conventional hyperparameter optimization is costly and ad hoc. Intrinsic dimension provides a good alternative, which connects information-theoretic notions such as Renyi information dimension (RID) to rate-distortion dimension and random codebook compression. In this work, we introduce the pairwise distortion distribution (PDD) and its asymptotic limit, pairwise dimension (PD), which generalize the correlation integral to general distortion measures. We show that PD bounds RID, and PDD provides a lower bound for random codebook quantization performance, which can guide a practical use for compression, quantization, and dimensionality reduction applications.

Figures & tables

Explore similar work

Jul 19, 2026

Rate-Distortion-Perception Theory: Redefining the Fundamental Limits of Information Representation

Classical rate-distortion (RD) theory has long established the fundamental limits of lossy compression by quantifying the minimum number of bits required to represent a source under a prescribed distortion constraint. However, widely used distortion measures such as mean-squared error often fail to capture perceptual quality or semantic validity, which are increasingly central in modern learning-driven applications. Rate-distortion-perception (RDP) theory extends the RD framework by introducing perception as a third fundamental axis, quantified via distributional similarity between the source and reconstructed signals, leading to the rate-distortion-perception function (RDPF). This tutorial provides a structured overview of the coding principles underlying perception-aware lossy compression and surveys recent achievability results under different randomness assumptions. It then presents a unifying optimization viewpoint for computing the RDPF as defined by Blau and Michaeli, for both discrete and continuous sources under broad families of perceptual constraints, including f-divergences, alpha-divergences, and Wasserstein-based metrics. Special attention is given to computational tools such as alternating minimization schemes, Newton-based methods, and convex optimization formulations, as well as to analytically tractable cases such as Gaussian sources and the perfect-realism regime. Unlike recent broad surveys that emphasize generative architectures and AI-empowered communication systems, this tutorial focuses on the coding-theoretic and computational machinery needed to characterize, compute, and interpret the RDP limits. Finally, the tutorial outlines promising research directions at the intersection of information theory, neural compression, robust source coding, and perception-aware networked control systems.
Jun 9, 2026

Minimum Distortion Quantization with Specified Output Distribution

We derive the optimal quantizer of a real-valued random variable WW with distribution PWP_W such that 1) the distribution of the quantization output XX that can take kk values follows any specified distribution PXP_X over {1,…,k}\{1,\ldots,k\}, and 2) the minimum mean squared error (MMSE) of estimating WW from XX is minimized. It is shown that the optimal quantizer takes the form X=σ(Fσ−1(X)−1(FW(W)))X=σ\big(F_{σ^{-1}(X)}^{-1}(F_W(W))\big), where σσ is the optimal permutation of {1,…,k}\{1,\ldots,k\} among all permutations to minimize the MMSE, and FF is the cumulative distribution function. When PWP_W is uniform over an interval or PXP_X is uniform over {1,…,k}\{1,\ldots,k\}, the quantizer takes a simple form X=FX−1(FW(W))X=F_{X}^{-1}(F_W(W)). The concept of majorization plays a key role in the optimality proof. Specifying the output distribution is useful for designing quantizers with explicitly controlled output entropy, maximized mutual information between input and output, tailored output distribution to match channel input requirements for communication, and data anonymization.
Apr 16, 2026

A Synonymous Variational Perspective on the Rate-Distortion-Perception Tradeoff

The fundamental limit of natural signal compression has traditionally been characterized by classical rate-distortion (RD) theory through the tradeoff between coding rate and reconstruction distortion, while the rate-distortion-perception (RDP) framework introduces a divergence-based measure of perceptual quality as a modeling principle, leaving its theoretical origin unclear. In this paper, motivated by a synonymity-based semantic information perspective, we reformulate perceptual reconstruction as recovering any admissible sample within an ideal synonymous set (synset) associated with the source, rather than the source sample itself, and establish a synonymous source coding architecture. On this basis, we develop a synonymous variational inference (SVI) analysis framework with a synonymous variational lower bound (SVLBO) for tractable analysis of synset-oriented compression. Within this framework, we establish a synonymity-perception consistency principle, showing that optimal identification of semantic information is theoretically consistent with perceptual optimization. Based on this result, we further derive a tight-bound synonymous source coding rate characterization and show that its Jensen-limit relaxation leads to a synonymous rate-distortion-perception form for practical optimization. These analytical results show that the distributional divergence term arises naturally from the synset-based reconstruction objective, clarify its compatibility with existing RDP formulations and classical RD theory, and suggest the potential advantages of synonymous source coding.