Content area
The two pillars of information theory, data compression and channel coding, are often considered as having reached maturity a long time ago. Our research brings fresh perspectives to both these areas by challenging long-standing assumptions and introducing new frameworks.
The Shannon entropy and rate-distortion function characterize the theoretical performance limits in loss-less and lossy data compression, respectively. Rate redundancy measures how quickly practical compression algorithms converge to these limits as the number n of encoded symbols increases. Since the 1980s and 1990s, the optimal rate redundancy has been established as Θ (log n/n ) in both lossless and lossy compression, specifically in the universal setting where the source distribution is unknown.
However, the minimax universal setting, which accounts for the worst-case performance of universal compression schemes over all source distributions, is the gold standard because it gives uniform convergence guarantees, even under adversarial conditions. In the minimax universal setting, the same Θ (log n/n ) rate redundancy result has been proven for lossless codes since 1981. However, minimax universal results for lossy compression remained elusive until 2023, when our work broke new ground. Our work proved that the optimal rate redundancy for lossy compression under the minimax universal framework is actually Θ˜ ( 1/√n) . This contrasts sharply with the prior Θ (log n/n ) results in lossy compression, which only gave pointwise convergence guarantees. We further showed that the Θ˜ ( 1/√n) rate redundancy result holds even when the source distribution is known (the non-universal setting). We provided a detailed study showing how regularity conditions imposed in prior works led to the faster Θ (log n/n ) pointwise convergence because they did not account for all i.i.d. sources and distortion measures. Even with the regularity conditions in place, the minimax convergence rate remains at Θ˜ ( 1/√n) .
In another work, we introduced a new variant of lossy compression called universal distortion, in which the distortion measure—traditionally fixed—is now a runtime input only to the encoder along with the source data to be compressed. Naturally, this framework has added complexity and thus a priori is expected to have slower convergence speeds to the theoretical limit than traditional lossy codes where the distortion measure is fixed and known beforehand. Our first contribution here was to prove that there is no such slowdown. Additionally, we proved rate redundancy results under the combined framework of minimax and universal distortion, providing uniform convergence guarantees over all i.i.d. sources and all distortion measures.
One of the primary motivations behind our work on lossy coding with universal distortion was to introduce greater versatility in compression systems to meet the needs of a variety of end-users who may have discordant notions of distortion. Another critical motivation stems from modern compression algorithms, which apply nonlinear transforms to the source data before compression. Optimal compression then corresponds to adjusting distortion in the transform domain in such a way that the source-reconstruction distortion in the original domain is minimized. Due to nonlinear transforms, optimal distortion “minimization” in the transform domain has to be adapt to the input source data. The universal distortion framework provides just the right model to study this problem because the distortion measure is a runtime input and is not known until the input source data is also known.
In our work on channel coding, we introduced two innovations. First, we developed a cost model that supersedes the two cost constraints that have dominated the literature: the strict almost-sure (percodeword) constraint and the weaker expected cost constraint. Our new cost formulation constrains the cost (or power) of the transmission both in expectation and variance. With a variance parameter V , our mean and variance (m.v.) cost constraint generalizes the existing frameworks, with V → 0 recovering the (first-and second-order) coding performance of the almost-sure constraint and V → ∞ recovering the expected cost constraint. Beyond generalization, we showed that the m.v. cost constraint for 0 < V < ∞ has practical advantages over both prior cost models. Unlike the almost-sure constraint, it allows for an improved coding performance with feedback; even without feedback, the coding performance under the m.v. cost constraint is superior. Unlike the expected cost constraint, it enforces a controlled, ergodic use of transmission power. This is essential for several practical reasons such as operating circuitry in the linear regime, minimizing power consumption, and reducing interference with other terminals.
Our second innovation was in feedback communication, where we unveiled new ways in which feedback can improve communication performance. For any V > 0, we showed that feedback improvement is possible for a significantly larger class of channels than in the prior study on unconstrained channels. Additionally, we proved that for a broad class of channels, feedback improvement is possible if and only if V > 0. Thus, our results reveal the critical role of cost variability V in enabling feedback mechanisms to improve coding performance. These are also the first results to establish second-order feedback improvement for discrete memoryless channels (DMCs) with cost constraints, thus providing a broader understanding of how and when feedback improves coding performance.
