Fast, Exact Synthesis of Gaussian and nonGaussian Long-Range-Dependent Processes
Baraniuk, Richard G.
1/<i>f</i> noise and statistically self-similar processes such as fractional Brownian motion (fBm) are vital for modeling numerous real-world phenomena, from network traffic to DNA to the stock market. Although several algorithms exist for synthesizing discrete-time samples of a 1/<i>f</i> process, these algorithms are <i>inexact</i>, meaning that the covariance of the synthesized processes can deviate significantly from that of a true 1/<i>f</i> process. However, the Fast Fourier Transform (FFT) can be used to exactly and efficiently synthesize such processes in O(<i>N</i> log<i>N</i>) operations for a length-N signal. Strangely enough, the key is to apply the FFT to match the target process's covariance structure, not its frequency spectrum. In this paper, we prove that this FFT-based synthesis is exact not only for 1/<i>f</i> processes such as fBm, but also for a wide class of <i>long-range dependent</i> processes. Leveraging the flexibility of the FFT approach, we develop new models for processes that exhibit one type of fBm scaling behavior over fine resolutions and a distinct scaling behavior over coarse resolutions. We also generalize the method in order to exactly synthesize various <i>nonGaussian</i> 1/<i>f</i> processes. Our nonGaussian 1/<i>f</i> synthesis is fast and simple. Used in simulations, our synthesis techniques could lead to new insights into areas such as computer networking, where the traffic processes exhibit nonGaussianity and a richer covariance than that of a strict fBm process.