The Sparse Fourier Transform. Haitham Hassanieh

Чтение книги онлайн.

СКАЧАТЬ this section, we assume x̂_i ∈ {−L, …, L} for some precision parameter L. To simplify the bounds, we assume L ≤ nc for some constant c > 0; otherwise the log n term in the running time bound is replaced by log L. We also assume that x̂ is exactly k-sparse. We will use the filter G with parameter δ = 1/(4n2L).

      Definition 4.1 We say that is a flat window function with parameters B > 1, δ > 0, and α > 0 if and satisfies

      • = 1 for |i| ≤ (1 − α)n/(2B) and = 0 for |i| ≤ n/(2B),

      • ∈ [0,1] for all i, and

      • .

      The above notion corresponds to the (1/(2B), (1 − α)/(2B), δ, O(B/α log(n/δ))-flat window function. In Appendix D, we give efficient constructions of such window functions, where G can be computed in time and for each i, can be computed in O(log(n/δ)) time. Of course, for i ∉ [(1 − α)n/(2B), n/(2B)], ∈ {0,1} can be computed in O(1) time. The fact that takes ω(1) time to compute for i ∈ [(1 − α)n/(2B), n/(2B)] will add some complexity to our algorithm and analysis. We will need to ensure that we rarely need to compute such values. A practical implementation might find it more convenient to precompute the window functions in a preprocessing stage, rather than compute them on the fly.

      The algorithm NOISELESSSPARSEFFT (SFT 3.0) is described as Algorithm 4.1. The algorithm has three functions:

      • HASHTOBINS. This permutes the spectrum of with Pσ,a,b, then “hashes” to B bins. The guarantee will be described in Lemma 4.1.

      • NOISELESSSPARSEFFTINNER. Given time-domain access to x and a sparse vector ẑ such that is k′-sparse, this function finds “most” of .

      • NOISELESSSPARSEFFT. This iterates NOISELESSSPARSEFFTINNER until it finds x̂ exactly.

      Algorithm 4.1 SFT 3.0: Exact Sparse Fourier Transform for k = o(n)

      We analyze the algorithm “bottom-up,” starting from the lower-level procedures.

      Analysis of NOISELESSSPARSEFFTINNER and HASHTOBINS

      For any execution of NOISELESSSPARSEFFTINNER, define the support S = supp(x̂ − ẑ). Recall that πσ,b(i) = σ(i − b) mod n. Define hσ,b(i) = round(πσ,b(i)B/n) and . Note that therefore |oσ,b(i)| ≤ n/(2B). We will refer to hσ,b(i) as the “bin” that the frequency i is mapped into, and oσ,b(i) as the “offset.” For any i ∈ S define two types of events associated with i and S and defined over the probability space induced by σ and b:

      • “Collision” event E_coll(i): holds iff hσ,b(i) ∈ hσ,b(S\ {i}), and

      • “Large offset” event E_off (i): holds iff |oσ,b(i)| ≥ (1 − α)n/(2B).

      Claim 4.1 For any i ∈ S, the event E_coll(i) holds with probability at most 4|S|/B.

      Proof Consider distinct i, j ∈ S. By Lemma 2.1,

      By a union bound over j ∈ S, Pr[E_coll(i)] ≤ 4 |S| /B.

      Claim 4.2 For any i ∈ S, the event E_off (i) holds with probability at most α.

      Proof Note that oσ,b(i) ≡ πσ,b(i) ≡ σ(i − b) (mod n/B). For any odd σ and any l ∈ [n/B], we have that Pr_b[σ(i − b) ≡ l (mod n/B)]= B/n. Since only αn/B offsets oσ,b(i) cause E_off (i), the claim follows.

      Lemma 4.1 Suppose B divides n. The output û of HASHTOBINS satisfies

      Let The running time of HASHTOBINS is

      Proof The proof can be found in Appendix A.3.

      Lemma 4.2 Consider any i ∈ S such that neither E_coll(i) nor E_off(i) holds. Let j = hσ,b(i). Then

      and j ∈ J.

      Proof The proof can be found in Appendix A.4.

      For each invocation of NOISELESSSPARSEFFTINNER, let P be the set of all pairs (i, v) for which the command ŵi ← v was executed. Claims 4.1 and 4.2 and Lemma 4.2 together guarantee that for each i ∈ S the probability that P does not contain the pair (i, (x̂ − ẑ)_i) is at most 4|S|/B + α. We complement this observation with the following claim.

      Claim СКАЧАТЬ