內容大鋼
傅里葉變換是計算信號頻域表示的最基本工具之一。它在信號處理、通信、音視頻壓縮、醫學成像、基因組學、天文學等許多領域中都發揮著核心作用。上世紀60年代數學家們開發了傅里葉變換的快速演算法，快速傅里葉變換（FFT）能在接近線性的時間內運行，已成為很多領域不可或缺的工具。然而，時至今日，FFT演算法的運行速度已經趕不上很多大數據問題的計算需求量。因此，在次線性時間內運行更快的演算法變得必要。稀疏傅里葉變換演算法並不採樣所有數據點，在很多問題上可以比傳統FFT快上10到100倍，帶來了革命性的進步！本書的研究內容曾獲得2016年美國電腦協會（ACM）的年度最佳博士論文獎。
作者介紹
(美)海塞姆·哈桑|責編:陳亮//劉慧
海塞姆·哈桑(Haitham Hassanieh)目前是美國伊利諾伊大學電子與電腦工程系和電腦科學系兩系合聘教授。他于201 6年在美國麻省理工學院獲得博士學位，並獲得麻省理工學院電腦科學最佳博士學位論文獎和美國電腦協會(ACM)的年度最佳博士論文獎。他的研究工作被《麻省理工技術評論》評為年度全球十大突破技術(TR10)之一，他還獲得過2011年SIGCOMM最佳論文獎和201 7年MobiSys最佳論文獎。
目錄
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
[