Probabilistic complexity analysis of incremental DFT algorithms

We present a probabilistic complexity analysis of a class of multi-stage algorithms for computing successive approximations to the DFT. While the quality of the approximate spectra obtained after any stage of these algorithms can be readily quantified in terms of commonly used input-independent metrics of spectral quality, each stage's arithmetic complexity is dependent on the nature of the input signal. Modeling the input signal as a stationary Gaussian-distributed random process, we obtain estimates of the distribution of the number of arithmetic operations required to complete any algorithm stage. This enables the derivation of important design information such as the probability with which a desired quality of approximation is achieved within a given arithmetic bound. Our results are verified using a Monte Carlo analysis.