Chapter 1 Introduction 1.1 Sparse Fourier Transform Algorithms 1.2 Applications of the Sparse Fourier Transform 1.3 Book Overview PART �� 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 �� 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 Light Field Reconstruction Using Continuous Fourier Sparsity 9.1 Introduction 9.2 Related Work 9.3 Sparsity in the Discrete vs. Continuous Fourier Domain 9.4 Light Field Notation 9.5 Light Field Reconstruction Algorithm 9.6 Experiments 9.7 Results 9.8 Discussion 9.9 Conclusion Chapter 10 Fast ln-Vivo MRS Acquisition with Artifact Suppression 10.1 Introduction 10.2 MRS-SFT 10.3 Methods 10,4 MRS Results 10.5 Conclusion Chapter 11 Fast Multi-Dimensional NMR Acquisition and Processing 11.1 Introduction 11.2 Multi-Dimensional Sparse Fourier Transform 11.3 Materials and Methods 11.4 Results 11.5 Discussion 11.6 Conclusion Chapter 12 Conclusion 12.1 Future Directions Appendix A Proofs Appendix B The Optimality of the Exactly k-Sparse Algorithm 4.1 Appendix C Lower Bound of the Sparse Fourier Transform in the General Case Appendix D Efficient Constructions of Window Functions Appendix E Sample Lower Bound for the Bernoulli Distribution Appendix F Analysis of the QuickSync System F.1 Analysis of the Baseline Algorithm F.2 Tightness of the Variance Bound F.3 Analysis of the QuickSync Algorithm Appendix G A 0.75 Million Point Sparse Fourier Transform Chip G.1 The Algorithm G.2 The Architecture G.3 The Chip References Author Biography