9.
1.2.4 Magnetic Resonance Spectroscopy (MRS)
One of the next frontiers in MRI is Magnetic Resonance Spectroscopy (MRS). MRS enables zooming in and detecting the biochemical content of each voxel in the brain, which can be used to discover disease biomarkers that allow early detection of cancer, autism, and Alzheimer’s. MRS tests, however, take prohibitively long time, requiring the patient to stay in the MRI machine for more than 2 hr. MRS images also suffer from a lot of clutter and artifacts that can mask some disease biomarkers. These two challenges have been a major barrier against adopting these tests in clinical diagnosis. To overcome this barrier, we demonstrated that processing MRS data using the Sparse Fourier Transform enhances image quality by suppressing artifacts and reduces the time the patient has to spend in the machine by 3× (e.g., from 2 hr to 40 mins). The details of our MRS algorithm, experiments and results can be found in Chapter 10.
1.2.5 Nuclear Magnetic Resonance (NMR)
NMR is a technique that provides the detailed structural properties of chemical compounds, providing the 3D structure of complex proteins and nucleic acids. However, collecting NMR measurements is a very time consuming and costly process that can take from several days up to weeks. This prevents researchers from running high-dimensional NMR experiments which are needed for analyzing more complex protein structures. NMR uses spectral analysis to find the resonance frequencies that correspond to the coupling between different atoms. NMR spectra are sparse. Hence, using the Sparse Fourier Transform, we show how to generate the NMR spectra by subsampling the NMR measurements. We customized the Sparse Fourier Transform for multi-dimensional NMR and showed that it can reduce the time of an NMR experiment by 16×. Chapter 11 describes the Sparse Fourier Transform techniques used for processing our NMR experiments along with our recovery results.
1.2.6 The Sparse Fourier Transform Chip
Traditionally, hardware implementations of FFT have been limited in size to few thousands of points. This is because large FFTs require a huge I/O bandwidth, consume a lot of power, and occupy a large silicon area. The Sparse Fourier Transform naturally addresses these issues due to its low computational and memory cost, enabling very large Fourier transforms. We built the largest Fourier transform VLSI chip to date with nearly a million point Fourier transform while consuming 40× less power than prior FFT VLSI implementations. The hardware architecture and benchmarking of the fabricated chip can be found in Appendix G.
1.3 Book Overview
This book is divided into two parts. Part I describes the theoretical foundations of the Sparse Fourier Transform. It presents the Sparse Fourier Transform algorithms in detail and provides the analysis and proofs of the guarantees of these algorithms. Chapter 2 presents the notation and basic definitions that will be used in this part of the book. Chapters 3 and 4 focus on reducing the runtime complexity of the Sparse Fourier Transform algorithms while Chapter 5 focuses on optimizing the sample complexity. Finally, in Chapter 6, we present numerical simulations to evaluate the performance of the Sparse Fourier Transform.
Part II describes the applications and systems designed using the Sparse Fourier Transform. Chapter 7 describes the design and implementation of a wireless receiver that can capture GHz of spectrum in real time. Chapter 8 presents a GPS receiver design with lower computational overhead. Chapter 9 describes a light field photography reconstruction algorithm that achieves high quality image recovery. Chapter 10 shows how the Sparse Fourier Transform can be used to reduce the time a patient spends in an MRI machine and generate clearer images. Chapter 11 presents the application of the Sparse Fourier Transform to Nuclear Magnetic Resonance in biochemistry.
Finally, in Chapter 12, we conclude and discuss future algorithms and applications of the Sparse Fourier Transform.
1. Note that for approximately sparse signals, multiple time shifts are used to average the noise and ensure robust estimation as we show in Chapter 4.
2. In Chapter 5, we will present techniques to detect collisions. However, accurately detecting collision is not always necessary. Since x̂ is sparse, the number of collisions will be very small and errors caused by assuming a non-zero frequency is isolated when it is in a collision can be corrected in subsequent iterations of the algorithm.
3. The sinc function is defined as: sinc(x) = sin(x)/x.
4. Note that only time samples that will be used by the bucketization filters need to be computed.
5. The four dimensions of a light field correspond to the 2D pixels in each image captured by a camera in the 2D camera array.
I
PART
THEORY OF THE SPARSE FOURIER TRANSFORM
2
Preliminaries
This chapter will introduce the notation and basic definitions that we will use throughout Part I of this book.
2.1 Notation
We use ω = e−2πi/n as the n-th root of unity and
For a vector x ∊ ℂn, its support is denoted by supp(x) ⊂ [n]. We use ||x||0 to denote |supp(x)|, the number of non-zero coordinates of x. Its Fourier spectrum is denoted by x̂, with
For a vector of length n, indices should be interpreted modulo n, so x−i
