000 05593nam a2200517 i 4500
001 011453166186
003 MOCL
005 20260609132937.0
006 m eo d
007 cr cn |||m|||a
008 180330s2018 nyua fob 000 0deng d
020 _a9781947487055
_qebook
020 _z9781947487062
_qePub
020 _z9781947487048
_qpaperback
020 _z9781947487079
_qhardcover
024 7 _a10.1145/3166186
_2doi
035 _a(CaBNVSL)swl00408226
035 _a(OCoLC)1030021268
040 _aCaBNVSL
_beng
_erda
_cCaBNVSL
_dCaBNVSL
050 4 _aQC20.7.F67
_bH277 2018
082 0 4 _a515.723
_223
100 1 _aHassanieh, Haitham,
_eauthor.
245 1 4 _aThe sparse Fourier transform :
_btheory and practice /
_cHaitham Hassanieh.
250 _aFirst edition.
264 1 _a[New York] :
_bAssociation for Computing Machinery ;
_a[San Rafael, California] :
_bMorgan & Claypool,
_c2018.
300 _a1 PDF (xvii, 260 pages) :
_billustrations.
336 _atext
_2rdacontent
337 _aelectronic
_2isbdmedia
338 _aonline resource
_2rdacarrier
490 1 _aACM books,
_x2374-6777 ;
_v#19
538 _aMode of access: World Wide Web.
504 _aIncludes bibliographical references (pages [249]-260).
505 0 _a1. Introduction -- 1.1 Sparse Fourier transform algorithms -- 1.2 Applications of the sparse Fourier transform -- 1.3 Book overview --
505 8 _aPart 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 --
505 8 _aPart 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 --
505 8 _aAppendix 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.
520 3 _aThe Fourier transform is one of the most fundamental tools for computing the frequency representation of signals. It plays a central role in signal processing, communications, audio and video compression, medical imaging, genomics, astronomy, as well as many other areas. Because of its widespread use, fast algorithms for computing the Fourier transform can benefit a large number of applications. The fastest algorithm for computing the Fourier transform is the Fast Fourier Transform (FFT), which runs in near-linear time making it an indispensable tool for many applications. However, today, the runtime of the FFT algorithm is no longer fast enough especially for big data problems where each dataset can be few terabytes. Hence, faster algorithms that run in sublinear time, i.e., do not even sample all the data points, have become necessary. This book addresses the above problem by developing the Sparse Fourier Transform algorithms and building practical systems that use these algorithms to solve key problems in six different applications: wireless networks, mobile systems, computer graphics, medical imaging, biochemistry, and digital circuits.
530 _aAlso available in print.
588 _aTitle from PDF title page (viewed on March 30, 2018).
650 0 _aFourier transformations.
650 0 _aSparse matrices.
655 0 _aElectronic books.
776 0 8 _iPrint version:
_z9781947487079
_z9781947487048
830 0 _aACM books ;
_v#19.
_x2374-6777
856 4 8 _3Abstract with links to full text
_uhttp://dx.doi.org/10.1145/3166186
999 _c887
_d887