LEADER 03409nam 22004933 450 001 9910838231703321 005 20230814222100.0 010 $a1-947487-04-3 035 $a(CKB)4100000003844519 035 $a(MiAaPQ)EBC6954876 035 $a(Au-PeEL)EBL6954876 035 $a(MiAaPQ)EBC31086553 035 $a(Au-PeEL)EBL31086553 035 $a(EXLCZ)994100000003844519 100 $a20220421d2018 uy 0 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 14$aThe Sparse Fourier Transform $eTheory and Practice 205 $a1st ed. 210 1$aSan Rafael :$cMorgan & Claypool Publishers,$d2018. 210 4$dİ2018. 215 $a1 online resource 225 0 $aACM books ;$v19 311 $a1-947487-06-X 311 $a1-947487-05-1 327 $aIntro -- Contents -- Preface -- 1. Introduction -- PART I. THEORY OF THE SPARSE FOURIER TRANSFORM -- 2. Preliminaries -- 3. Simple and Practical Algorithm -- 4. Optimizing Runtime Complexity -- 5. Optimizing Sample Complexity -- 6. Numerical Evaluation -- PART II. APPLICATIONS OF THE SPARSE FOURIER TRANSFORM -- 7. GHz-Wide Spectrum Sensing and Decoding -- 8. Faster GPS Synchronization -- 9. Light Field Reconstruction -- 10. Fast In-Vivo MRS Acquisition with Artifact Suppression -- 11. Fast Mu1ti-Dimensional NMR Acquisition and Processing -- 12. Conclusion -- A. Proofs -- B. The Optimality of the Exactly k-Sparse Algorithm 4.1 -- C. Lower Bound of the Sparse Fourier Transform in the General Case -- D. Efficient Constructions of Window Functions -- E. Sample Lower Bound for the Bernoulli Distribution -- F. Analysis of the QuickSync System -- G. A 0.75 Million Point Sparse Fourier Transform Chip -- References -- Author Biography. 330 $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. 410 0$aACM Bks. 606 $aFourier transformations 606 $aSparse matrices 615 0$aFourier transformations. 615 0$aSparse matrices. 676 $a515/.723 700 $aHassanieh$b Haitham$01731442 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910838231703321 996 $aThe Sparse Fourier Transform$94144100 997 $aUNINA