The Sparse Fourier Transform. Haitham Hassanieh

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

Читать онлайн книгу The Sparse Fourier Transform - Haitham Hassanieh страница 18

Автор:
Жанр:
Серия:
Издательство:
The Sparse Fourier Transform - Haitham Hassanieh ACM Books

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

mass from non-heavy coordinates lies in the same bin. For such a “well-hashed” coordinate i, we would like to find its location τ = πσ,b(i) = σ(ib) among the ∈n/k < n/k consecutive values that hash to the same bin. Let

      Algorithm 4.3 SFT 4.0: General Sparse Fourier Transform for k = o(n), part 2 of 2

Image Image

      so Image. In the noiseless case, we showed that the difference in phase in the bin using Pσ,0,b and using Pσ,1,b is Image plus a negligible O(δ) term. With noise this may not be true; however, we can say for any β ∈ [n] that the difference in phase between using Pσ,a,b and Pσ,α+βb, as a distribution over uniformly random α ∈ [n], is Image with (for example) E[ν2] = 1/100 (all operations on phases modulo 2π). We can only hope to get a constant number of bits from such a “measurement.” So our task is to find τ within a region Q of size n/k using O(log(n/k)) “measurements” of this form.

      One method for doing so would be to simply do measurements with random β ∈ [n]. Then each measurement lies within π/4 of Image with at least Image probability. On the other hand, for jτ and as a distribution over β, Image is roughly uniformly distributed around the circle. As a result, each measurement is probably more than π/4 away from Image. Hence, O(log(n/k)) repetitions suffice to distinguish among the n/k possibilities for τ. However, while the number of measurements is small, it is not clear how to decode in polylog rather than Ω.(n/k) time.

      To solve this, we instead do a t-ary search on the location for t = Θ(log n). At each of O(logt(n/k)) levels, we split our current candidate region Q into t consecutive subregions Q1, …, Qt, each of size w. Now, rather than choosing β ∈ [n], we choose Image. By the upper bound on β, for each q ∈ [t] the values {Image | jQq} all lie within Image of each other on the circle. On the other hand, if |jτ| > 16w, then Image will still be roughly uniformly distributed about the circle. As a result, we can check a single candidate element eq from each subregion: if eq is in the same subregion as τ, each measurement usually agrees in phase; but if eq is more than 16 subregions away, each measurement usually disagrees in phase. Hence with O(log t) measurements, we can locate τ to within O(1) consecutive subregions with failure probability 1/tΘ(1). The decoding time is O(t log t).

      This primitive LOCATEINNER lets us narrow down the candidate region for τ to a subregion that is a t′ = Ω(t) factor smaller. By repeating LOCATEINNER Image times, LOCATESIGNAL can find τ precisely. The number of measurements is then O(log t logt(n/k)) = O(log(n/k)) and the decoding time is O(t log t logt(n/k)) = O(log(n/k) log n). Furthermore, the “measurements” (which are actually calls to HASHTOBINS) are non-adaptive, so we can perform them in parallel for all O(k/∈) bins, with O(log(n/δ)) average time per measurement. This gives O(k log(n/k) · log(n/δ)) total time for LOCATESIGNAL.

      This lets us locate every heavy and “well-hashed” coordinate with 1/tΘ(1) = o(1) failure probability, so every heavy coordinate is located with arbitrarily high constant probability.

       Estimation

      By contrast, estimation is fairly simple. As in Algorithm 4.1, we can estimate Image as Image, where û is the output of HASHTOBINS. Unlike in Algorithm 4.1, we now have noise that may cause a single such estimate to be poor even if i is “well-hashed.” However, we can show that for a random permutation Pσ,a,b the estimate is “good” with constant probability. ESTIMATEVALUES takes the median of Rest = O(log Image) such samples, getting a good estimate with 1 − /64 probability. Given a candidate set L of size k/∈, with 7/8 probability at most k/8 of the coordinates are badly estimated. On the other hand, with 7/8 probability, at least 7k/8 of the heavy coordinates are both located and well estimated. This suffices to show that, with 3/4 probability, the largest k elements J of our estimate ŵ contains good estimates of 3k/4 large coordinates, so Image is close to k/4-sparse.

       4.3.2 Analysis

       Formal Definitions

      As in the noiseless case, we define πσ,b(i) = σ(ib) mod n, hσ,b(i) = round πσ,b(i)B/n), and oσ,b(i) = πσ,b(i) − hσ,b(i)n/B. We say hσ,b(i) is the “bin” that frequency i is mapped into, and oσ,b(i) is the “offset.” We define Image

      Define

Image

      In each iteration of SPARSEFFT, define ′ = , and let

Image

      Then Image and Image. We will show that each iS is found by LOCATESIGNAL with probability Image, when Image.

      For any iS define three types of events associated with i and S and defined over the probability space induced by σ and b:

      •

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