An efficient sparse FFT algorithm with application to signal source separation and 2D virtual image feature extraction

摘要

Signal source separation is an important aspect of both measurement and signature intelligence (MASINT) as well as modern commercial smart grid applications. In some MASINT scenarios, real-time signal processing is required in a small physical form factor, which can become prohibitive with the high sample rates required of modern signal identification algorithms. We develop a new Fast Fourier Transform (FFT) algorithm, the Aliased FFT (AFFT), that exploits spectral redundancy and sparsity in the signal to drastically reduce the number of computations required from O(N logN), for the normal FFT, to one that approaches the idealized O(K logK) for a K-sparse signal. We also develop a signal source separation algorithm using harmonically aligned signal projections (HASP) that is useful for transforming a one-dimensional signal of interest (SOI) into a two-dimensional image in such a way to facilitate automated feature extraction. An automated feature extractor is described which can accurately achieve super-resolution far beyond that of the traditional FFT by again taking advantage of the harmonic structure present in the SOI. We demonstrate HASP and this feature extractor for the application of load disaggregation-identifying the presence of certain types of devices connected to a power system.