reviews—without the prior permission of the publisher.
Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which Morgan & Claypool is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.
The Sparse Fourier Transform
Haitham Hassanieh
www.morganclaypoolpublishers.com
ISBN: 978-1-94748-707-9 hardcover
ISBN: 978-1-94748-704-8 paperback
ISBN: 978-1-94748-705-5 eBook
ISBN: 978-1-94748-706-2 ePub
Series ISSN: 2374-6769 print 2374-6777 electronic
DOIs:
10.1145/3166186 Book
10.1145/3166186.3166187 Preface
10.1145/3166186.3166188 Chapter 1
10.1145/3166186.3166189 Chapter 2
10.1145/3166186.3166190 Chapter 3
10.1145/3166186.3166191 Chapter 4
10.1145/3166186.3166192 Chapter 5
10.1145/3166186.3166193 Chapter 6
10.1145/3166186.3166194 Chapter 7
10.1145/3166186.3166195 Chapter 8
10.1145/3166186.3166196 Chapter 9
10.1145/3166186.3166197 Chapter 10
10.1145/3166186.3166198 Chapter 11
10.1145/3166186.3166199 Chapter 12
10.1145/3166186.3166200 Appendices
10.1145/3166186.3166201 References
A publication in the ACM Books series, #19
Editor in Chief: M. Tamer Özsu, University of Waterloo
First Edition
10 9 8 7 6 5 4 3 2 1
To Maha and Nadima Hassanieh
Contents
| Preface | |
| Chapter 1 | Introduction |
| 1.1 Sparse Fourier Transform Algorithms | |
| 1.2 Applications of the Sparse Fourier Transform | |
| 1.3 Book Overview | |
| PART I | THEORY OF THE SPARSE FOURIER TRANSFORM |
| Chapter 2 | Preliminaries |
| 2.1 Notation | |
| 2.2 Basics | |
| Chapter 3 | Simple and Practical Algorithm |
| 3.1 Introduction | |
| 3.2 Algorithm | |
| Chapter 4 | Optimizing Runtime Complexity |
| 4.1 Introduction | |
| 4.2 Algorithm for the Exactly Sparse Case | |
| 4.3 Algorithm for the General Case | |
| 4.4 Extension to Two Dimensions | |
| Chapter 5 | Optimizing Sample Complexity |
| 5.1 Introduction | |
| 5.2 Algorithm for the Exactly Sparse Case | |
| 5.3 Algorithm for the General Case | |
| Chapter 6 | Numerical Evaluation |
| 6.1 Implementation | |
| 6.2 Experimental Setup | |
| 6.3 Numerical Results | |
| PART II | APPLICATIONS OF THE SPARSE FOURIER TRANSFORM |
| Chapter 7 | GHz-Wide Spectrum Sensing and Decoding |
| 7.1 Introduction | |
| 7.2 Related Work | |
| 7.3 BigBand | |
| 7.4 Channel Estimation and Calibration | |
| 7.5 Differential Sensing of Non-Sparse Spectrum | |
| 7.6 A USRP-Based Implementation | |
| 7.7 BigBand’s Spectrum Sensing Results | |
| 7.8 BigBand’s Decoding Results | |
| 7.9 D-BigBand’s Sensing Results | |
| 7.10 Conclusion | |
| Chapter 8 | Faster GPS Synchronization |
| 8.1 Introduction | |
| 8.2 GPS Primer | |
| 8.3 QuickSync | |
| 8.4 Theoretical Guarantees | |
| 8.5 Doppler Shift and Frequency Offset | |
| 8.6 Testing Environment | |
| 8.7 Results | |
| 8.8 Related Work | |
| 8.9 Conclusion | |
| Chapter 9 |
|
