The Sparse Fourier Transform. Haitham Hassanieh

Fourier transform algorithms is to exploit the inherit sparsity of natural signals. In many applications, most of the Fourier coefficients of the signal are small or equal to zero, i.e., the output of the Fourier transform is sparse. For such signals, one does not need to compute the entire output of the Fourier transform; it is sufficient to only compute the large frequency coefficients. Fourier sparsity is in fact very common as it appears in audio/video, medical imaging, computational learning theory, analysis of Boolean functions, similarity search in databases, spectrum sensing, datacenter monitoring, etc. [Agrawal et al. 1993, Chandrakasan et al. 1996, Kahn et al. 1988, Lin et al. 2011, Lustig et al. 2008, Mueen et al. 2010].

      This book pursues the above insight in the context of both algorithms and systems in order to answer the following two core questions.

       How can we leverage sparsity to design faster Fourier transform algorithms?

      and

       How do we build software and hardware systems that adapt our algorithms to various application domains in order to deliver practical gains?

      In this book, we will answer the above questions by presenting the Sparse Fourier Transform algorithms: a family of sublinear algorithms for computing the Fourier transform of frequency-sparse signals faster than FFT and using a small subset of the input samples. The book also describes architectures for leveraging sparsity to build practical systems that solve key problems in wireless networks, mobile systems, computer graphics, medical imaging, biochemistry, and digital circuits.

      The book is divided into two parts: theoretical algorithms and systems. The theoretical part introduces the algorithmic foundations of the Sparse Fourier Transform which encompass two main axes.

      Optimizing the Runtime Complexity. The book presents Sparse Fourier Transform algorithms with the lowest runtime complexity known to date. For exactly sparse signals, we present an algorithm that runs in O(k log n) time where k is the number of large frequency coefficients (i.e., sparsity) and n is the signal size. This algorithm is optimal if the FFT algorithm is optimal. For approximately sparse signals, which we will formally define in Section 1.1.1, we present an algorithm that runs in O(k log n log (n/k)) time which is log n factor away from optimal. Both algorithms improve over FFT for any sparsity k = o(n) and have small “Big-Oh” constants. As a result, they are often faster than FFT in practice and run quickly on very large data sets.

      Optimizing the Sampling Complexity. The book presents Sparse Fourier Transform algorithms with the optimal sampling complexity for average case inputs, i.e., these algorithms use the minimum number of input data samples that would produce a correct answer. Hence, they reduce the acquisition cost, bandwidth, and I/O overhead needed to collect, transfer, and store the data. Specifically, these algorithms require only O(k) samples for exactly sparse signals and O(k log n) samples for approximately sparse signals while keeping the same runtime complexity of the aforementioned worst case algorithms. Furthermore, the algorithms naturally extend to multi-dimensional Sparse Fourier Transforms, without incurring much overhead.

      The simplicity and practicality of the Sparse Fourier Transform algorithms enabled the design of six new systems that address major challenges in the areas of wireless networks and mobile systems, computer graphics, medical imaging, biochemistry, and digital circuits. Table 1.1 summarizes the systems developed using the Sparse Fourier Transform and the innovation in each system

      Leveraging the Sparse Fourier Transform to build practical systems, however, is not always straightforward. The Sparse Fourier Transform is a framework of algorithms and techniques for analyzing sparse signals. It inherently depends on the sparsity of the signal which changes from one application to another. Thus, incorporating domain knowledge from each application allows us to deliver much more significant gains. First, different applications exhibit different levels and structure of sparsity. For example, in wireless networks, occupied frequencies in the wireless spectrum are not randomly distributed. They are instead clustered based on transmission regulations set by the FCC. Hence, incorporating the structure of the sparsity into the algorithm and system is essential for achieving good performance gains. In addition, in some applications such as medical imaging, the sparsity of the signal is not apparent, which requires developing methods to sparsify the signal before being able to use the Sparse Fourier Transform. In other applications, sparsity appears only in part of the system and thus we have to redesign the entire system in order to propagate the gains of the Sparse Fourier Transform to other stages and improve the overall system performance. Hence, adapting the Sparse Fourier Transform into practical applications requires a deep understanding of the application domain and customizing the algorithms to become more in-sync with the system requirements which we will explore throughout this book.

      The next two sections provide an overview of the theoretical algorithms and the software and hardware systems presented in this book.

       1.1 Sparse Fourier Transform Algorithms

      The existence of Fourier transform algorithms faster than FFT is one of the central questions in 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 log^c(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⁻⁵ [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