Abstract
This paper establishes the fundamental limits of how efficiently Lévy processes—a broad class of stochastic processes including Brownian motion and jump processes—can be compressed or coded. We provide tight asymptotic formulas for coding complexity, demonstrating that the difficulty of representing these processes is determined by two specific functions of their underlying characteristics: the Gaussian component and the jump measure. We introduce an explicit coding strategy and prove its weak optimality through rigorous lower bound analysis.
Introduction
In information theory and signal processing, the discretization of continuous signals for storage or transmission is a central problem known as quantization or source coding. While the coding complexity of Gaussian processes, such as standard Brownian motion, is well-understood, Lévy processes present unique challenges. These processes often contain a "jittery" continuous component alongside a random number of jumps of varying magnitudes. This work aims to characterize the distortion-rate function: the minimum achievable error (distortion) $\epsilon$ given a fixed bit budget (rate) $r$, particularly in the high-resolution limit where $\epsilon \to 0$.
Methodology
Defining Complexity Functions
The core of our theoretical framework involves two crucial functions, $F_1(\epsilon)$ and $F_2(\epsilon)$, which together characterize the total coding complexity. $F_1$ captures the complexity arising from the Gaussian (smooth) component and the accumulation of very small jumps. In contrast, $F_2$ accounts for the complexity of encoding the heights and locations of "large" jumps.
Explicit Coding Strategy
To establish upper bounds, we design a specific "corridor-based" algorithm. The scheme monitors the process over time, recording a new value whenever the process exits a small corridor of width $\epsilon$. It utilizes prefix-free codes to efficiently store the jump heights and their corresponding timestamps.
Lower Bound Proofs
To demonstrate the tightness of our results, we employ Shannon lower bounds and change-of-measure arguments. These proofs show that no coding algorithm can achieve a lower bit rate than our derived formulas (up to a constant factor), leveraging the standard Lévy-Khintchine triplet $(\sigma^2, \nu, b)$ that uniquely defines any Lévy process.
Key Results and Insights
Dominance of the Gaussian Component
A primary finding is that if a process possesses any Gaussian component ($\sigma > 0$), its coding complexity is dominated by that component. In the high-resolution limit, such processes behave similarly to Brownian motion, requiring a rate proportional to $\epsilon^{-2}$.
Complexity of Jump Processes
For pure jump processes, such as the Gamma process, the complexity is significantly lower than that of Gaussian processes. The difficulty lies not just in the frequency of jumps, but in the resolution required to describe their heights relative to the total error budget. For an $\alpha$-stable process, the distortion $D(r)$ scales as $r^{-1/\alpha}$, confirming that "smoother" processes (higher $\alpha$) are more difficult to compress.
Weak Optimality and Robustness
Our coding scheme is "weakly optimal," meaning the upper and lower bounds match in their order of magnitude. Furthermore, the scheme is robust; it does not require precise knowledge of the underlying process parameters, as they can be estimated directly from the observed data.
Conclusion
This research provides a comprehensive characterization of the coding complexity for the entire class of Lévy processes. While we have established the correct scaling laws, future work remains to determine the exact optimal constants. Additionally, extending these results to multi-dimensional Lévy processes and analyzing the formal computational complexity of the proposed algorithms are promising avenues for further study.
Summary updated