value of the bucket it hashes to since all other frequencies that hash into the bucket have zero values. Hence, we can easily find the value of the non-zero frequency coefficient in a bucket. However, we still do not know its frequency position f, since frequency bucketization mapped multiple frequencies to the same bucket. The simplest way to compute f is to leverage the phase-rotation property of the Fourier transform, which states that a shift in time domain translates into phase rotation in the frequency domain [Lyons 1996]. Specifically, we perform the process of bucketization again, after a circular shift of x by τ samples. Since a shift in time translates into a phase rotation in the frequency domain, the value of the bucket changes from b̂(i) = x̂(f) to b̂(τ)(i) = x̂(f) · ejΔϕ where the phase rotation is
Hence, using the change in the phase of the bucket, we can estimate the position of the non-zero frequency coefficient in the bucket. Note that the phase wraps around every 2π and so the shift τ should be 1 to avoid the phase wrapping for large values of f.1 Since there are k non-zero frequency coefficients, this frequency estimation can be done efficiently using at most O(k) computations. In Section 1.1.3, we describe additional techniques that are used by our Sparse Fourier Transform algorithms to estimate the values and positions of non-zero frequency coefficients.
1.1.2.3 Collision Resolution
Non-zero frequency coefficients that are isolated in their own bucket can be properly estimated, as described above. However, when non-zero frequencies collide in the same bucket, we are unable to estimate them correctly. Hence, to recover the full frequency spectrum, we need to resolve the collisions.
To resolve collision, we need to repeat the frequency bucketization in a manner that ensures that the same non-zero frequencies do not collide with each other every time. The manner in which we achieve this depends on the type of filter used for bucketization. For example, with the aliasing filters described above, we can bucketize the spectrum multiple times using aliasing filters with co-prime sampling rates. This changes the hashing function from h(f) = f mod n/p to h′(f) = f mod n/p′ where p and p′ are co-prime. Co-prime aliasing filters guarantee that any two frequencies that collide in one bucketization will not collide in the other bucketization. To better understand this point, consider the example in Figure 1.2. The first time we bucketize, we use an aliasing filter that subsamples the time signal by a factor of 3. In this case, the two frequencies labeled in red and blue collide in a bucket whereas the frequency labeled in green does not collide, as shown in the figure. The second time we bucketize, we use an aliasing filter that subsamples by 4. This time the blue and green frequencies collide whereas the red frequency does not collide. Now we can resolve collisions by iterating between the two bucketizations. For example, we can estimate the green frequency from the first bucketization, where it does not collide.2 We subtract the green frequency from the colliding bucket in the second bucketization to obtain the blue frequency. We then go back to the first bucketization and subtract the blue frequency from the bucket where it collides to obtain the red frequency.
Figure 1.2 Resolving collisions with co-prime aliasing. Using two co-prime aliasing filters, we ensure the frequencies that collide in one filter will not collide in the second. For example, frequencies 5 and 9 collide in the first filter. But frequency 5 does not collide in the second which allows us to estimate it and subtract it.
Iterating between the different bucketizations by estimating frequencies from buckets where they do not collide and subtracting them from buckets where they do collide, ensures that each non-zero frequency will be isolated in its own bucket during some iteration of the algorithm. This allows us to estimate each non-zero frequency correctly. Thus, at the end of the of the collision resolution step, we have recovered all non-zero frequencies and hence have successfully computed the Fourier transform of the signal.
1.1.3 Algorithmic Techniques
The previous section established a general framework for computing the Sparse Fourier Transform and gave one example of a technique that can be used in each step of this framework. In this section, we describe a more comprehensive list of techniques that are used by different Sparse Fourier Transform algorithms.
Figure 1.3 Filters used for frequency bucketization shown in the time (upper row) and the frequency (lower row) domain.
1.1.3.1 Frequency Bucketization Techniques
As described earlier, bucketization is done using filters. The choice of the filter can severely affect the running time of a Sparse Fourier Transform algorithm. Ideally, we would like a filter that uses a small number of input time samples to hash the frequency coefficients into buckets. For example, the rectangular or boxcar filter shown in Figure 1.3(a), uses only B time samples to hash the frequency coefficients into B buckets which is ideal in time domain. However, in the frequency domain, it is equal to the sinc function,3 which decays polynomially as shown in Figure 1.3(a). This polynomial decay means that the frequency coefficients “leak” between buckets, i.e., the value of the bucket is no longer the sum of n/B coefficients that hash to the bucket. It is a weighted sum of all the n frequency coefficients. Hence, a nonzero frequency coefficient can never be isolated in a bucket and estimated correctly. One the other hand, a rectangular filter is ideal in the frequency domain since it has no leakage, as shown in Figure 1.3(b). However, it is sinc function in the time domain and hence requires using all n input samples which take at least Ω(n) time to process.
In this book, we identify several efficient filters that use a small number of samples in time domain and have minimal or no leakage in the frequency domain and as a result can be used to perform fast bucketization.
Flat Window Filter. This filter looks very similar to a rectangle or box in the frequency domain while still using a small number of time samples. An example of such filter is a Gaussian function multiplied by a sinc function in the time domain which is shown in Figure 1.3(c). Since the Gaussian function decays exponentially fast both in time and frequency, the leakage between buckets in this filter is negligible and can be ignored. Similarly, the filter is concentrated in time and hence uses only a small number of time samples. The resulting hash function of such filter can be written as h(f) = ⌈f/(n/B)⌉. Gaussian is only one example of such functions. One can potentially use a Dolph-Chebyshev or a Kaiser-Bessel function as we describe in more detail in Chapter 2.
Aliasing Filter. We presented this filter in the previous section. It is simply a spike-train of period p in time domain since it subsamples the time domain signal by a factor of p, as shown in Figure 1.3(d). It is also a spike-train in the frequency domain since it sums up frequency coefficients that
