The Rate-Distortion-Deception Tradeoff
2026-07-28 • Information Theory
Information Theory
AI summaryⓘ
The authors study how to compress data so the reconstructed output is both close to the original data and looks like it came from a different chosen distribution. Traditionally, compression focuses on keeping the output faithful to the original or making it look natural from the same data source. They introduce a new idea called the deception constraint where the output deceives by resembling a different distribution while still being accurate enough. The authors analyze the tradeoffs between compression rate, accuracy, and this deception goal.
data compressionrate-distortion theoryperception constraintrandom variablesreconstruction fidelitydistributiontradeoffdeception constraintinformation theory
Authors
Semih Akkoc, Sahan Liyanaarachchi, Sennur Ulukus, Aylin Yener
Abstract
The problem of finding the optimal compression rate for a given random variable has been traditionally studied under two main constraints: distortion and perception. The distortion constraint enforces the fidelity of our reconstruction with respect to the observed realization of the random variable, while the perception constraint ensures that the reconstruction is close to a sample from the distribution of the random variable of interest. In this work, we explore the possibility of reconstruction, such that the reconstructed sample is still within a desired fidelity level with our original realization of the random variable, but at the same time, it resembles a sample from a different target distribution. We term this criterion as the deception constraint and find the fundamental tradeoffs of rate-distortion and deception.