The Sparse Fourier Transform. Haitham Hassanieh

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:⁴

      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 → σ⁻¹f + β 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 are not randomly distributed; they follow a specific structure. For example, as mentioned earlier, in wireless communication, the occupied frequencies in the wireless spectrum are clustered. In computational photography, the occupied frequencies are more likely to be present in part of the Fourier spectrum. On the other hand, in an application like GPS, the occupied coefficient can be anywhere. Understanding the structure of sparsity in each application allows us to design a system that leverages it to achieve the best performance gains.

      Level of Sparsity. A main difference between theory and practice is that the Sparse Fourier Transform algorithms operate in the discrete domain. In real and natural signals, however, the frequency coefficients do not necessarily lie on discrete grid points. Simply rounding off the locations of the coefficients to the nearest grid points can create bad artifacts which significantly reduce the sparsity of the signal and damage the quality of the results. This problem occurs in application like medical imaging and light-field photography. Hence, we have to design systems that can sparsify the signals and recover their original sparsity in the continuous domain in order to address the mismatch between the theoretical Sparse Fourier Transform framework and the scenarios in which it is applied.

Table 1.2 Theoretical Sparse Fourier Transform algorithms

      a. The sampling complexity of algorithms SFT 1.0–4.1 is the same as their runtime complexity.

      System Requirements. Different applications have different goals. For example, in medical imaging, the acquisition cost is high since it requires the patient to spend more time in the MRI machine while processing the captured data afterward is not a problem. Hence, the goal would be to minimize the number of input samples that need to be collected even if it requires additional processing time. On the other hand, in applications like GPS, collecting the samples is very cheap. However, processing them consumes a lot of power. Hence, the goal would be to minimize computational load even if all the input samples are used. Finally, in applications like spectrum acquisition and NMR spectroscopy, the goal would be to minimize both the runtime and the sampling. Hence, understanding the system is essential for adapting the Sparse Fourier Transform techniques to satisfy the requirements of each application.

      System Architecture. In some applications, the applicability of the Sparse Fourier Transform to a system architecture might not even be apparent. For example, the Fourier transform of the GPS signal is not sparse and hence applying the Sparse Fourier Transform directly to GPS is not feasible. However, we observed that the GPS receiver correlates its signal with a special code transmitted by the satellite, and the output of the correlation is sparse because it spikes only when the code and the signal are aligned. Hence, we have to map this indirect form of sparsity to the Sparse Fourier Transform framework. We also need to ensure that the gains of the Sparse Fourier Transform are not bottlenecked by other components in the system. Thus, careful system design is essential for propagating these gains along the system pipeline and improving the overall system performance.

      Signal to Noise Ratio. In practice, the gains of the Sparse Fourier Transform are constraint by the noise level in the system. It is essential to perform sampling and processing that would be sufficient to bring the signal above the noise floor of the system. For example, although the sparsity that appears in a GPS system is extremely high (≈0.025%), GPS signals are -30 dB to -20 dB below the noise floor which requires additional computation that upper bounds the performance gains. Thus, understanding the noise level and structure is essential in designing any system that uses the Sparse Fourier Transform.

      The following subsections summarize the systems presented in this book and how they benefit from the Sparse Fourier Transform.