The sparse Fourier transform : theory and practice / Haitham Hassanieh.

Format:

Book

Author/Creator:

Hassanieh, Haitham, author.

Series:

ACM books ; 2374-6777 #19.

ACM books, 2374-6777 ; #19

Language:

English

Subjects (All):

Fourier transformations.

Sparse matrices.

Genre:

Electronic books.

Physical Description:

1 online resource (xvii, 260 pages) : illustrations.

Edition:

First edition.

Place of Publication:

[New York] : Association for Computing Machinery ; [San Rafael, California] : Morgan & Claypool, 2018.

System Details:

Mode of access: World Wide Web.

Summary:

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.

Contents:

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

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

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.

Notes:

Includes bibliographical references (pages [249]-260).

Title from PDF title page (viewed on March 30, 2018).

Other Format:

Print version:

ISBN:

9781947487055

OCLC:

1030021268

Access Restriction:

Restricted for use by site license.