The work presented in this book would not have been possible without the help and support of a large group of people to whom I owe a lot of gratitude. I would also like to thank everyone who worked on the Sparse Fourier Transform project. Dina, Piotr, and Eric Price were the first people to work with me. They played an indispensable role in developing the theoretical Sparse Fourier Transform algorithms. The next person to work with me was Fadel Adib who helped me take on the hard task of kickstarting the applications. After that, Lixin Shi helped me bring to life more applications. He worked with me tirelessly for a very long time while making the work process extremely enjoyable. Finally, I would like to thank all of the remaining people who contributed to the material in this book: Elfar Adalsteinsson, Fredo Durand, Omid Abari, Ezzeldin Hamed, Abe Davis, Badih Ghazi, Ovidiu Andronesi, Vladislav Orekhov, Abhinav Agarwal, and Anantha Chandrakasan.
Haitham Hassanieh
January 2018
1
Introduction
The Fourier transform is one of the most important and widely used computational tasks. It is a foundational tool commonly used to analyze the spectral representation of signals. Its applications include audio/video processing, radar and GPS systems, wireless communications, medical imaging and spectroscopy, the processing of seismic data, and many other tasks [Bahskarna and Konstantinides 1995, Chan and Koo 2008, Heiskala and Terry 2001, Nishimura 2010, Van Nee and Coenen 1991, Yilmaz 2008]. Hence, faster algorithms for computing the Fourier transform can benefit a wide range of applications. The fastest algorithm to compute the Fourier transform today is the Fast Fourier Transform (FFT) algorithm [Cooley and Tukey 1965]. Invented in 1965 by Cooley and Tukey, the FFT computes the Fourier transform of a signal of size n in O(n log n) time. This near-linear time of the FFT made it one of the most influential algorithms in recent history [Cipra 2000]. However, the emergence of big data problems, in which the processed datasets can exceed terabytes [Schadt et al. 2010], has rendered the FFT’s runtime too slow. Furthermore, in many domains (e.g., medical imaging, computational photography), data acquisition is costly or cumbersome, and hence one may be unable to collect enough measurements to compute the FFT. These scenarios motivate the need for sublinear time algorithms that compute the Fourier transform faster than the FFT algorithm and use only a subset of the input data required by the FFT.
The key insight to enable sublinear 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
