Эротические рассказы

The Sparse Fourier Transform. Haitham HassaniehЧитать онлайн книгу.

The Sparse Fourier Transform - Haitham Hassanieh


Скачать книгу
B more carefully to obtain the desired running time. The cost of each iterative step is multiplied by the number of filtering steps needed to compute the location of the coefficients, which is Θ(log(n/B)).If we set B = Θ(k′), this would be Θ(log n) in most iterations, giving a Θ(k log2 n) running time. This is too slow when k is close to n. We avoid this by decreasing B more slowly and k′ more quickly. In the r-th iteration, we set B = k/ poly(r). This allows the total number of bins to remain O(k) while keeping log(n/B) small—at most O(log log k) more than log (n/k). Then, by having k′ decrease according to k′ = k/rΘ(r) rather than k/2Θ(r), we decrease the number of rounds to O(log k/ log log k). Some careful analysis shows that this counteracts the log log k loss in the log (n/B) term, achieving the desired O(k log n log(n/k)) running time.

       4.2 Algorithm for the Exactly Sparse Case

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

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

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

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

      • Image.

      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 Image time and for each i, Image can be computed in O(log(n/δ)) time. Of course, for i ∉ [(1 − α)n/(2B), n/(2B)], Image ∈ {0,1} can be computed in O(1) time. The fact that Image 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 Image 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 Image is k′-sparse, this function finds “most” of Image.

      • NOISELESSSPARSEFFT. This iterates NOISELESSSPARSEFFTINNER until it finds exactly.

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

Image

      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(). Recall that πσ,b(i) = σ(ib) mod n. Define hσ,b(i) = round(πσ,b(i)B/n) and Image. 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 iS define two types of events associated with i and S and defined over the probability space induced by σ and b:

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

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

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

      Proof Consider distinct i, jS. By Lemma 2.1,

Image

      By a union bound over jS, Pr[Ecoll(i)] ≤ 4 |S| /B.

      Claim 4.2 For any iS, the event Eoff (i) holds with probability at most α.

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

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

Image

      Let Image The running time of HASHTOBINS is Image

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

      Lemma 4.2 Consider any iS such that neither Ecoll(i) nor Eoff(i) holds. Let j = hσ,b(i). Then

Image

      and jJ.

      Proof


Скачать книгу
Яндекс.Метрика