n/p. The aliasing filter is ideal both in time and in frequency since it only uses B time samples and has zero leakage between buckets. Unfortunately, we will later show that the aliasing filter does not lend itself to powerful randomization techniques and, as a result, can only be shown to work for average case input signals as opposed to worst case.
Fourier Projection Filter. This filter is a generalization of the aliasing filter to higher dimensions. It is a direct result of the Fourier Slice Projection Theorem which states that taking the Fourier transform of samples along a slice (e.g., a 1D line in 2D time signal or a 2D plane in a 3D signal) results in the orthogonal projection of the frequency spectrum onto the corresponding slice in the Fourier domain. For example, if we sample a row in a 2D time domain signal and then take its 1D Fourier transform, each output point of the Fourier transform will be the sum of the coefficients along one column, as shown in Figure 1.4(a). Alternatively, if we sample a column, each output point will be the sum of the coefficients along one row, as shown in Figure 1.4(b). This also holds for any discrete line, as shown in Figure 1.4(c,d). Thus, if we sample a line with slope equal to 1 or 2, we get a projection in the frequency domain along lines with slopes equal to −1or −1/2. Note that discrete lines wrap around and hence can generate non-uniform sampling, as shown in Figure 1.4(d).
Figure 1.4 Fourier projection filters. The top row of figures shows the sampled lines of the time signal and the bottom row of figures shows how the spectrum is projected. Frequencies of the same color are projected onto the same point: (a) row projection, (b) column projection, (c) diagonal projection, and (d) line with slope = 2.
1.1.3.2 Frequency Estimation Techniques
Recall that the goal of the frequency estimation step is to compute the positions f and values x̂(f) of the non-zero frequency coefficients that have been hashed to non-empty buckets. In what follows, we will present the techniques used by the Sparse Fourier Transform algorithms to perform frequency estimation.
Time-Shift/Phase-Rotation Approach. In this approach, which we have previously described in Section 1.1.2, we repeat the bucketization after shifting the time signal x by a circular shift of τ samples. For buckets with a single isolated non-zero frequency coefficient, this results in a phase rotation Δϕ of the complex value of the coefficient. Δϕ = 2πfτ/n which we can use to compute the frequency position f. Since the frequency is isolated, its value can be immediately computed from the value of the bucket as described in the previous section. This is an extremely efficient approach since it requires constant O(1) time to estimate each non-zero frequency. For noisy signals, we repeat this process for multiple different time shifts to average the noise. The details of how we average the noise to ensure robust recovery can be found in Chapter 4.
Voting Approach. This is a non-iterative streaming approach where we repeat the bucketization few times while changing the hashing function. For each bucketization, the non-empty buckets vote for all the frequency coefficients that hash into those buckets. Non-zero frequency coefficients will get a vote from every bucketization with high probability. On the other hand, zero and negligible frequencies are unlikely to get many votes. Hence, after repeating the bucketization and this voting procedure a few times, the k non-zero frequency coefficients will have the largest number of votes and can be identified. In Chapter 3, we will show that this approach is more resilient to signal noise. However, this comes at the cost of increased runtime which we prove to be
1.1.3.3 Collision Resolution Techniques
Collision resolution is achieved by repeating the bucketization in a manner that changes the way frequency coefficients hash into buckets so that the same coefficients do not continue to collide.
We can randomize the hashing function if we can perform a random permutation of the positions of the coefficients in x̂ before repeating the bucketization. This can be achieved by rearranging the indices of the input time signal x and rescaling it in the following manner:4
where σ is a random integer invertible modulo n and β is a random integer. This results in a random linear mapping of the positions of the frequency coefficients: f → σ−1f + β mod n. The proof of this can be found in Chapter 2. While this randomization is a very powerful collision resolution technique, it only works with the flat window filter and does not work with aliasing filters as we will show in Chapter 3. To resolve collisions using aliasing filters, we need to use co-prime subsampling, i.e., subsample the signal using different co-prime subsampling rates as explained in the previous section.
1.1.4 Algorithmic Results
In this section, we will present the theoretical results of the Sparse Fourier Transform algorithms that we developed. All the algorithms follow the framework described in Section 1.1.2. However, they use different techniques from Section 1.1.3 and as a result achieve different runtime and sampling complexities as well as different guarantees. Most of the theoretical algorithms presented in this book are randomized and succeed with a large constant probability. Table 1.2 summarizes the theoretical Sparse Fourier Transform algorithms presented in this book along with their complexity results, guarantees, and techniques used.
1.2 Applications of the Sparse Fourier Transform
The second half of this book focuses on developing software and hardware systems that harness the Sparse Fourier Transform to solve practical problems. The book presents the design and implementation of six new systems that solve challenges in the areas of wireless networks, mobile systems, computer graphics, medical imaging, biochemistry, and digital circuits. All six systems are prototyped and evaluated in accordance with the standards of each application’s field.
Adapting the Sparse Fourier Transform to a particular application requires a careful design and deep knowledge of the application domain. The Sparse Fourier Transform is a framework of algorithms and techniques for analyzing sparse signals. It is not a single algorithm that can be plugged directly into an application. To apply it to a problem, one has to deeply understand the structure of the sparsity in the application of interest, and customize the framework to the observed sparsity. More generally, real applications add new constraints that are application-dependent, and can deviate from our mathematical abstraction. Below we highlight some of the common themes that arise in mapping the Sparse Fourier Transform to practical systems.
Structure of Sparsity. In most applications, the occupied frequency coefficients
