FFAST: An Algorithm for Computing an Exactly $ k$ -Sparse DFT in $O( k\log k)$ Time

It is a well-known fact that the Discrete Fourier Transform (DFT) <inline-formula> <tex-math notation="LaTeX">$ \vec {X}$ </tex-math></inline-formula> of an arbitrary <inline-formula> <tex-math notation="LaTeX">$ n$ </tex-math></inline-formula>-length input signal <inline-formula> <tex-math notation="LaTeX">$ \vec {x}$ </tex-math></inline-formula>, can be computed from all the <inline-formula> <tex-math notation="LaTeX">$ n$ </tex-math></inline-formula> time-domain samples in <inline-formula> <tex-math notation="LaTeX">$O( n\log n)$ </tex-math></inline-formula> operations via a Fast Fourier Transform (FFT) algorithm. If the spectrum <inline-formula> <tex-math notation="LaTeX">$ \vec {X}$ </tex-math></inline-formula> is <inline-formula> <tex-math notation="LaTeX">$ k$ </tex-math></inline-formula>-sparse (where <inline-formula> <tex-math notation="LaTeX">$ k\ll n$ </tex-math></inline-formula>), can we do better? We show that asymptotically in <inline-formula> <tex-math notation="LaTeX">$ k$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$ n$ </tex-math></inline-formula>, when <inline-formula> <tex-math notation="LaTeX">$ k$ </tex-math></inline-formula> is sub-linear in <inline-formula> <tex-math notation="LaTeX">$ n$ </tex-math></inline-formula> (precisely, <inline-formula> <tex-math notation="LaTeX">$ k= O( n^{ \delta }$ </tex-math></inline-formula>), where <inline-formula> <tex-math notation="LaTeX">$0 \leq \delta <1$ </tex-math></inline-formula>), and the support of the non-zero DFT coefficients is uniformly random, the fast fourier aliasing-based sparse transform (FFAST) algorithm, proposed in this paper, computes, with asymptotically high probability, the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> non-zero DFT coefficients of <inline-formula> <tex-math notation="LaTeX">$\vec {X}$ </tex-math></inline-formula> from <inline-formula> <tex-math notation="LaTeX">$O( k)$ </tex-math></inline-formula> samples of <inline-formula> <tex-math notation="LaTeX">$ \vec {x}$ </tex-math></inline-formula> in <inline-formula> <tex-math notation="LaTeX">$O( k\log k)$ </tex-math></inline-formula> arithmetic operations. Further, the constants in the big Oh notation for both sample and computational cost are small, e.g., when <inline-formula> <tex-math notation="LaTeX">$ \delta < 0.99$ </tex-math></inline-formula>, which essentially covers a wide range of sub-linear sparsity cases, the sample cost is less than <inline-formula> <tex-math notation="LaTeX">$4 k$ </tex-math></inline-formula>. Although, in this paper we assume that the samples of the signal <inline-formula> <tex-math notation="LaTeX">$ \vec {x}$ </tex-math></inline-formula> observed by the FFAST are noise-free, a noise-robust extension of the FFAST is provided in a companion (Part II) paper <xref ref-type="bibr" rid="ref1">[1]</xref>. Our approach is based on filter-less sub-sampling of the input signal using a set of <italic>carefully chosen uniform sub-sampling patterns guided by the Chinese Remainder Theorem (CRT)</italic>. The idea is to cleverly exploit, rather than avoid, the resulting aliasing artifacts induced by sub-sampling. Specifically, the sub-sampling operation on the time-domain signal <inline-formula> <tex-math notation="LaTeX">$ \vec {x}$ </tex-math></inline-formula> is designed to create aliasing patterns of the non-zero coefficients of the spectrum <inline-formula> <tex-math notation="LaTeX">$ \vec {X}$ </tex-math></inline-formula> to “look like” parity-check constraints of a good erasure-correcting sparse-graph code. <italic>Next, we show that computing the sparse DFT <inline-formula> <tex-math notation="LaTeX">$ \vec {X}$ </tex-math></inline-formula> is equivalent to decoding of an appropriate sparse-graph code</italic>. The sparse-graph codes further permit a fast peeling-style decoding. Consequently, the resulting DFT computation is low in both the sample and the decoding complexity. We analytically connect our proposed CRT-based aliasing framework to random sparse-graph codes, and analyze the performance of our algorithm using density evolution techniques from coding theory. We provide extensive simulation results, that are in tight agreement with our theoretical findings.