The sparse Fourier transform : theory and practice /

Bibliographic Details
Main Author:	Hassanieh, Haitham (Author)
Format:	eBook
Language:	English
Published:	[New York] : [San Rafael, California] : Association for Computing Machinery ; Morgan & Claypool, 2018.
Edition:	First edition.
Series:	ACM books ; #19.
Subjects:	Fourier transformations. Sparse matrices. Electronic data.
Online Access:	Connect to the full text of this electronic book

Table of Contents:

1. Introduction
1.1 Sparse Fourier transform algorithms
1.2 Applications of the sparse Fourier transform
1.3 Book overview
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.
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