Probabilistic complexity analysis for a class of approximate DFT algorithms

We present a probabilistic complexity analysis of a class of multi-stage algorithms which incrementally refine DFT approximations. Each stage of any algorithm in this class improves the results of the previous stage by a fixed increment in one of three dimensions: SNR, frequency resolution, or frequency coverage. However, the complexity of each stage is probabilistically dependent upon certain characteristics of the input signal. Assuming that an algorithm has to be terminated before its arithmetic cost exceeds a given limit, we have formulated a method for predicting the probability of completion of each of the algorithm's stages. This analysis is useful for low-power and real-time applications where FFT algorithms cannot meet the specified limits on arithmetic cost.