The Sparse Fourier Transform

Haitham Hassanieh

Description

The 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.

This is a revised version of the thesis that won the 2016 ACM Doctoral Dissertation Award.

Table of 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 Using Continuous Fourier Sparsity / 10. Fast In-Vivo MRS Acquisition with Artifact Suppression / 11. Fast Multi-Dimensional NMR Acquisition and Processing / 12. Conclusion

Sujets

• Sciences formelles
• Informatique théorique
• Algorithmes
• Algorithms
• Programming
• Computers
• Informatique

Informations

• Publié par: Association for Computing Machinery and Morgan & Claypool Publishers
• Date de parution: 27 février 2018
• Nombre de lectures: 0
• EAN13: 9781947487062
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

The Sparse Fourier Transform
ACM Books
Editor in Chief
M. Tamer zsu, University of Waterloo
ACM Books is a new series of high-quality books for the computer science community, published by ACM in collaboration with Morgan Claypool Publishers. ACM Books publications are widely distributed in both print and digital formats through booksellers and to libraries (and library consortia) and individual ACM members via the ACM Digital Library platform.
The Sparse Fourier Transform: Theory and Practice
Haitham Hassanieh, University of Illinois at Urbana-Champaign
2018
The Continuing Arms Race: Code-Reuse Attacks and Defenses
Editors: Per Larsen, Immunant, Inc .
Ahmad-Reza Sadeghi, Technische Universit t Darmstadt
2018
Frontiers of Multimedia Research
Editor: Shih-Fu Chang, Columbia University
2018
Shared-Memory Parallelism Can Be Simple, Fast, and Scalable
Julian Shun, University of California, Berkeley
2017
Computational Prediction of Protein Complexes from Protein Interaction Networks
Sriganesh Srihari, The University of Queensland Institute for Molecular Bioscience
Chern Han Yong, Duke-National University of Singapore Medical School
Limsoon Wong, National University of Singapore
2017
The Handbook of Multimodal-Multisensor Interfaces, Volume 1: Foundations, User Modeling, and Common Modality Combinations
Editors: Sharon Oviatt, Incaa Designs
Bj rn Schuller, University of Passau and Imperial College London
Philip R. Cohen, Voicebox Technologies
Daniel Sonntag, German Research Center for Artificial Intelligence (DFKI)
Gerasimos Potamianos, University of Thessaly
Antonio Kr ger, German Research Center for Artificial Intelligence (DFKI)
2017
Communities of Computing: Computer Science and Society in the ACM
Thomas J. Misa, Editor, University of Minnesota
2017
Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining
ChengXiang Zhai, University of Illinois at Urbana-Champaign
Sean Massung, University of Illinois at Urbana-Champaign
2016
An Architecture for Fast and General Data Processing on Large Clusters
Matei Zaharia, Stanford University
2016
Reactive Internet Programming: State Chart XML in Action
Franck Barbier, University of Pau, France
2016
Verified Functional Programming in Agda
Aaron Stump, The University of Iowa
2016
The VR Book: Human-Centered Design for Virtual Reality
Jason Jerald, NextGen Interactions
2016
Ada s Legacy: Cultures of Computing from the Victorian to the Digital Age
Robin Hammerman, Stevens Institute of Technology
Andrew L. Russell, Stevens Institute of Technology
2016
Edmund Berkeley and the Social Responsibility of Computer Professionals
Bernadette Longo, New Jersey Institute of Technology
2015
Candidate Multilinear Maps
Sanjam Garg, University of California, Berkeley
2015
Smarter Than Their Machines: Oral Histories of Pioneers in Interactive Computing
John Cullinane, Northeastern University; Mossavar-Rahmani Center for Business and Government, John F. Kennedy School of Government, Harvard University
2015
A Framework for Scientific Discovery through Video Games
Seth Cooper, University of Washington
2014
Trust Extension as a Mechanism for Secure Code Execution on Commodity Computers
Bryan Jeffrey Parno, Microsoft Research
2014
Embracing Interference in Wireless Systems
Shyamnath Gollakota, University of Washington
2014
The Sparse Fourier Transform
Theory and Practice
Haitham Hassanieh
University of Illinois at Urbana-Champaign
ACM Books #19
Copyright 2018 by the Association for Computing Machinery and Morgan Claypool Publishers
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means-electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews-without the prior permission of the publisher.
Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which Morgan Claypool is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.
The Sparse Fourier Transform
Haitham Hassanieh
books.acm.org
www.morganclaypoolpublishers.com
ISBN: 978-1-94748-707-9 hardcover
ISBN: 978-1-94748-704-8 paperback
ISBN: 978-1-94748-705-5 eBook
ISBN: 978-1-94748-706-2 ePub
Series ISSN: 2374-6769 print 2374-6777 electronic
DOIs:
10.1145/3166186 Book
10.1145/3166186.3166187 Preface
10.1145/3166186.3166188 Chapter 1
10.1145/3166186.3166189 Chapter 2
10.1145/3166186.3166190 Chapter 3
10.1145/3166186.3166191 Chapter 4
10.1145/3166186.3166192 Chapter 5
10.1145/3166186.3166193 Chapter 6
10.1145/3166186.3166194 Chapter 7
10.1145/3166186.3166195 Chapter 8
10.1145/3166186.3166196 Chapter 9
10.1145/3166186.3166197 Chapter 10
10.1145/3166186.3166198 Chapter 11
10.1145/3166186.3166199 Chapter 12
10.1145/3166186.3166200 Appendices
10.1145/3166186.3166201 References
A publication in the ACM Books series, #19
Editor in Chief: M. Tamer zsu, University of Waterloo
First Edition
10 9 8 7 6 5 4 3 2 1
To Maha and Nadima Hassanieh
Contents
Preface
Chapter 1
Introduction
1.1 Sparse Fourier Transform Algorithms
1.2 Applications of the Sparse Fourier Transform
1.3 Book Overview
PART I
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 II
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 In-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
Preface
The 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.
Part I of the book focuses on the theory front. It introduces the Sparse Fourier Transform algorithms: a family of sublinear time algorithms for computing the Fourier transform faster than FFT. The Sparse Fourier Transform is based on the insight that many real-world signals are sparse, i.e., most of the frequencies have negligible contribution to the overall signal. Exploiting this sparsity, the book introduces several new algorithms which encompass two main axes.
Runtime Complexity. Nearly optimal Sparse Fourier Transform algorithms are presented that are faster than FFT and have the lowest runtime complexity known to date.
Sampling Complexity. Sparse Fourier Transform algorithms with optimal sampling complexity are presented in the average case and the same nearly optimal runtime complexity. These algorithms use the minimum numbe