The Sparse Fourier Transform. Haitham Hassanieh

      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 our applications we have δ < 1/n^O((1) and ∊ = 2∊′. Thus the window lengths w of the flat window function and the standard window function are the same up to a constant factor.

      Figure 2.1 An example flat window function for n = 256. This is the sum of 31 adjacent (1/22, 10⁻⁸, 133) Dolph-Chebyshev window functions, giving a (0.11, 0.06, 2 × 10⁻⁹, 133) flat window function (although our proof only guarantees a tolerance δ = 29 × 10⁻⁸, the actual tolerance is better). The top row shows G and in a linear scale, and the bottom row shows the same with a log scale.

      Proof Let f = (∊ − ∊′)/2, and let F be an standard window function with minimal . We can assume ∊, ∊′ > 1/(2n) (because [−∊n, ∊n] = {0} otherwise), so . Let be the sum of 1 + 2(∊′ + f)n adjacent copies of , normalized to . That is, we define

      so by the shift theorem, in the time domain

      Since for |i| ≤ fn, the normalization factor is at least 1. For each i ∈ [−∊′n, ∊′n], the sum on top contains all the terms from the sum on bottom. The other 2∊′n terms in the top sum have magnitude at most δ/((∊′ + ∊)n) = δ/(2(∊′ + f)n), so . For |i| > ∊n, however, . Thus F′ is an (∊, ∊′, δ, w) flat window function, with the correct w. ■

2.2.2 Permutation of Spectra

      Following Gilbert et al. [2005a], we can permute the Fourier spectrum as follows by permuting the time domain:

      Definition 2.3 Suppose σ⁻¹ exists mod n.

Скачать книгу