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 as the -th root of unity. For any complex number a, we use ϕ(a) ∊ [0, 2π]to denote the phase of a. For a complex number a and a real positive number b, the expression a ± b denotes a complex number a′ such that |a − a′| ≤ b.

      For a vector x ∊ ℂⁿ, its support is denoted by supp(x) ⊂ [n]. We use ||x||₀ 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 min_{j≡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 is a power of 2. We use [m] × [m] = [m]² to denote the m × m grid {(i, j) : i ∊ [m], j ∊ [m]}. For a 2D matrix , its support is denoted by .We also use ||x||₀ to denote |supp(x)|. Its 2D Fourier spectrum is denoted by x̂, with

      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 ∈ ℝⁿ with supp(F) ⊆ [−w/2, w/2] such that for all i ∊ [−∊n, ∊n], and for all i ∉ [−∊n, ∊n].

      Claim 2.1 For any ∊ and δ, there exists an standard window function.

      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 and truncating it at . The Dolph-Chebyshev window function also has the claimed property but with minimal big-Oh constant [Smith 2011] (in particular, half the constant of the truncated Gaussian). ■

      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 ∈ ℝⁿ with supp(F) ⊆ [−w/2, w/2] such that for all i ∈ [−∊′n, ∊′n] and for all i ∉ [−∊n, ∊n].

      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 flat window function.

      Note that in