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 -- 2. preliminaries -- 2.1 Notation -- 2.2 Basics -- 3. Simple and practical algorithm -- 3.1 Introduction -- 3.2 Algorithm -- 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 -- 5. Optimizing sample complexity -- 5.1 Introduction -- 5.2 Algorithm for the exactly sparse case -- 5.3 Algorithm for the general case -- 6. Numerical evaluation -- 6.1 Implementation -- 6.2 Experimental setup -- 6.3 Numerical results --

Part II. Applications of the sparse Fourier transform -- 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 -- 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 -- 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 -- 10. Fast in-vivo MRS acquisition with artifact suppression -- 10.1 Introduction -- 10.2 MRS-SFT -- 10.3 Methods -- 10.4 MRS results -- 10.5 Conclusion -- 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 -- 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 -- Analysis of the baseline algorithm -- Tightness of the variance bound -- Analysis of the QuickSync algorithm -- Appendix G. A 0.75 million point sparse Fourier transform chip -- The algorithm -- The architecture -- The chip -- References -- Author biography.