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
