The Sparse Fourier Transform. Haitham Hassanieh
Читать онлайн книгу.
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 = xn−i. This allows us to define convolution
and the coordinate-wise product (x · y)i = xiyi, so
We use [n] to denote the set {1,…, n}. All operations on indices in are taken modulo n. Therefore we might refer to an n-dimensional vector as having coordinates {0, 1,…, n − 1} or {0, 1,…, n/2, − n/2 + 1, …, −1} interchangeably. When i ∈ ℤ is an index into an n-dimensional vector, sometimes we use |i| to denote minj≡i (mod n) |j|. Finally, we assume that n is an integer power of 2.
For the case of 2D Fourier transforms which will appear in Chapter 5, we assume that
Finally, if y is in frequency-domain, its inverse is denoted by y̌.
2.2 Basics
2.2.1 Window Functions
In digital signal processing [Oppenheim et al. 1999] one defines window functions in the following manner.
Definition 2.1 We define a (∊, δ, w) standard window function to be a symmetric vector F ∈ ℝn with supp(F) ⊆ [−w/2, w/2] such that
Claim 2.1 For any ∊ and δ, there exists an
Proof This is a well-known fact [Smith 2011]. For example, for any ∊ and δ, one can obtain a standard window by taking a Gaussian with standard deviation
The above definition shows that a standard window function acts like a filter, allowing us to focus on a subset of the Fourier coefficients. Ideally, however, we would like the pass region of our filter to be as flat as possible.
Definition 2.2 We define a (∊, ∊′, δ, ω) flat window function to be a symmetric vector F ∈ ℝn with supp(F) ⊆ [−w/2, w/2] such that
A flat window function (like the one in Figure 2.1) can be obtained from a standard window function by convolving it with a “box car” window function, i.e., an interval. Specifically, we have the following.
Claim 2.2 For any ∊, ∊′, and δ with ∊′ < ∊, there exists an
Note that in