the theory of algorithms. The past two decades have witnessed significant advances in sublinear Fourier algorithms for sparse signals. The first such algorithm (for the Hadamard transform) appeared in Kushilevitz and Mansour [1991] (building on Goldreich and Levin [1989]). Since then, several sublinear algorithms for complex Fourier inputs have been discovered [Akavia et al. 2003, Akavia 2010, Gilbert et al. 2002, Gilbert et al. 2005a, Iwen 2010b, Mansour 1992]. The main value of these algorithms is that they outperform FFT’s runtime for sparse signals. For very sparse signals, the fastest algorithm is due to Gilbert et al. [2005a] and has O(k logc(n) log(n/k)) runtime, for some c > 2. This algorithm outperforms FFT for any k smaller than Θ(n/ loga n) for some a > 1.
Table 1.1 Practical systems developed using the Sparse Fourier Transform
Despite this impressive progress, the prior work suffers from two main limitations. First, none of the existing algorithms improves over FFT’s runtime for the whole range of sparse signals, i.e., k = o(n). Second, the aforementioned algorithms are quite complex, and suffer from large “Big-Oh” constants that lead to long runtime in practice. For example, an implementation of the algorithm in Gilbert et al. [2005a] can only outperform FFT for extremely sparse signals where k/n ≤ 3.2 × 10−5 [Iwen et al. 2007]. The algorithms in Gilbert et al. [2002] and Iwen [2010b] require an even sparser signal (i.e., larger n and smaller k). As a result, it has been difficult to incorporate those algorithms into practical systems.
In this section, we give an overview of our Sparse Fourier Transform algorithms, which address the above limitations of prior work. We start by formalizing the problem. We then describe the algorithmic framework underlying all of our Sparse Fourier Transform algorithms. Once we establish this framework, we describe the different techniques that can be used at each step of a Sparse Fourier Transform algorithm. We finally present the various algorithms that result from using these techniques.
1.1.1 Problem Statement
Consider a signal x of size n whose discrete Fourier transform is x̂ defined by:
x̂ is exactly k-sparse if it has exactly k non-zero frequency coefficients while the remaining n − k coefficients are zero. In this case, the goal of the Sparse Fourier Transform is to exactly recover x̂ by finding the frequency positions f and values x̂(f) of the k non-zero coefficients. For general signals, the Sparse Fourier Transform computes a k-sparse approximation x̂′ of x̂. The best k-sparse approximation of x̂ can be obtained by setting all but the largest k coefficients of x̂ to 0. The goal is to compute an approximation x̂′ in which the error in approximating x̂ is bounded by the error on the best k-sparse approximation. Formally, x̂ has to satisfy the following ℓ2/ℓ2 guarantee:
where C is some approximation factor and the minimization is over exactly k-sparse signals.
In the remainder of this section, we will describe the algorithmic framework and techniques in terms of exactly sparse signals. However, the full details and extensions to the general case of approximately sparse signals can be found in Chapters 3, 4, and 5.
1.1.2 Algorithmic Framework
The Sparse Fourier Transform has three main components: Frequency Bucketization, Frequency Estimation, and Collision Resolution.
1.1.2.1 Frequency Bucketization
The Sparse Fourier Transform starts by hashing the frequency coefficients of x̂ into buckets such that the value of the bucket is the sum of the values of the frequency coefficients that hash into the bucket. Since x̂ is sparse, many buckets will be empty and can be simply discarded. The algorithm then focuses on the non-empty buckets and computes the positions and values of the large frequency coefficients in those buckets in what we call the frequency estimation step.
The process of frequency bucketization is achieved through the use of filters. A filter suppresses and zeroes out frequency coefficients that hash outside the bucket while passing through frequency coefficients that hash into the bucket. The simplest example of this is the aliasing filter. Recall the following basic property of the Fourier transform: subsampling in the time domain causes aliasing in the frequency domain. Formally, let b be a subsampled version of x, i.e., b(i) = x(i · p) where p is a subsampling factor that divides n. Then, b̂, the Fourier transform of b is an aliased version of x̂, i.e.,
Thus, an aliasing filter is a form of bucketization in which frequencies equally spaced by an interval B = n/p hash to the same bucket and there are B such buckets, as shown in Figure 1.1. The hashing function resulting from this bucketization can be written as: h(f) = f mod n/p. Further, the value in each bucket is the sum of the values of only the frequency coefficients that hash to the bucket as can be seen from Equation 1.3.
For the above aliasing filter, the buckets can be computed efficiently using a B-point FFT which takes O(B log B) time. We set B = O(k) and hence bucketization takes only O(k log k) time and uses only O(B) = O(k) of the input samples of x. In Section 1.1.3, we describe additional types of filters that are used by our Sparse Fourier Transform algorithms to perform frequency bucketization.
Figure 1.1 Bucketization using aliasing filter. Subsampling a signal by 3× in the time domain results in the spectrum aliasing. Specifically, the 12 frequency will alias into 4 buckets. Frequencies that are equally spaced by 4 (shown with the same color) end up in the same bucket.
1.1.2.2 Frequency Estimation
In this step, the Sparse Fourier Transform estimates the positions and values of the non-zero frequency coefficients which created the energy in each of the non-empty buckets. Since x̂ is sparse, many of the non-empty buckets will likely have a single non-zero frequency coefficient hashing into them, and only a small number will have a collision of multiple non-zero coefficients. We first focus on buckets with a single non-zero frequency coefficients and estimate the value and the position of this non-zero frequency, i.e., x̂(f) and the corresponding f.
In the absence of a collision, the value of the non-zero
