Алгоритмы быстрого вычисления разреженного преобразования Фурье (Sparse FFT), осень 2015: Сигналы с разреженным спектром Фурье: определения и баз

  • Published on
    07-Apr-2017

  • View
    560

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>Sparse Fourier Transform(lecture 1)</p><p>Michael Kapralov1</p><p>1IBM Watson EPFL</p><p>St. Petersburg CS ClubNovember 2015</p><p>1 / 73</p></li><li><p>Given x Cn, compute the Discrete Fourier Transform (DFT) ofx :</p><p>xi =1n</p><p>j[n]</p><p>xj ij ,</p><p>where = e2i/n is the n-th root of unity.</p><p>Assume that n is a power of 2.</p><p>compression schemes(JPEG, MPEG)</p><p>signal processingdata analysis</p><p>imaging (MRI, NMR)</p><p>2 / 73</p></li><li><p>Given x Cn, compute the Discrete Fourier Transform (DFT) ofx :</p><p>xi =1n</p><p>j[n]</p><p>xj ij ,</p><p>where = e2i/n is the n-th root of unity.</p><p>Assume that n is a power of 2.</p><p>compression schemes(JPEG, MPEG)</p><p>signal processingdata analysis</p><p>imaging (MRI, NMR)</p><p>2 / 73</p></li><li><p>Given x Cn, compute the Discrete Fourier Transform (DFT) ofx :</p><p>xi =1n</p><p>j[n]</p><p>xj ij ,</p><p>where = e2i/n is the n-th root of unity.</p><p>Assume that n is a power of 2.</p><p>compression schemes(JPEG, MPEG)</p><p>signal processingdata analysis</p><p>imaging (MRI, NMR)</p><p>2 / 73</p></li><li><p>DFT has numerous applications:</p><p>3 / 73</p></li><li><p>Fast Fourier Transform (FFT)</p><p>Computes Discrete Fourier Transform (DFT) of a length nsignal in O(n logn) time</p><p>Cooley and Tukey, 1964</p><p>Gauss, 1805</p><p>Code=FFTW (Fastest Fourier Transform in the West)</p><p>4 / 73</p></li><li><p>Fast Fourier Transform (FFT)</p><p>Computes Discrete Fourier Transform (DFT) of a length nsignal in O(n logn) time</p><p>Cooley and Tukey, 1964</p><p>Gauss, 1805</p><p>Code=FFTW (Fastest Fourier Transform in the West)</p><p>4 / 73</p></li><li><p>Fast Fourier Transform (FFT)</p><p>Computes Discrete Fourier Transform (DFT) of a length nsignal in O(n logn) time</p><p>Cooley and Tukey, 1964</p><p>Gauss, 1805</p><p>Code=FFTW (Fastest Fourier Transform in the West)</p><p>5 / 73</p></li><li><p>Fast Fourier Transform (FFT)</p><p>Computes Discrete Fourier Transform (DFT) of a length nsignal in O(n logn) time</p><p>Cooley and Tukey, 1964</p><p>Gauss, 1805</p><p>Code=FFTW (Fastest Fourier Transform in the West)</p><p>6 / 73</p></li><li><p>Sparse FFT</p><p>Say that x is k -sparse if x has k nonzero entries</p><p>Say that x is approximately k -sparse if x is close to k -sparse insome norm (`2 for this lecture)</p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>7 / 73</p></li><li><p>Sparse FFT</p><p>Say that x is k -sparse if x has k nonzero entries</p><p>Say that x is approximately k -sparse if x is close to k -sparse insome norm (`2 for this lecture)</p><p>-0.0006</p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>0.0006</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noisehead</p><p>8 / 73</p></li><li><p>Sparse approximations</p><p>JPEG=</p><p>Given x , compute x , then keep top k coefficients only for k N</p><p>Used in image and video compression schemes(e.g. JPEG, MPEG)</p><p>9 / 73</p></li><li><p>Sparse approximations</p><p>JPEG=</p><p>Given x , compute x , then keep top k coefficients only for k N</p><p>Used in image and video compression schemes(e.g. JPEG, MPEG)</p><p>10 / 73</p></li><li><p>Computing approximation fast</p><p>Basic approach:</p><p> FFT computes x from x in O(n logn) time</p><p> compute top k coefficients in O(n) time.</p><p>Sparse FFT: directly computes k largest coefficients of x (approximately</p><p> formal def later)</p><p> Running time O(k log2 n) or faster</p><p> Sublinear time!</p><p>11 / 73</p></li><li><p>Computing approximation fast</p><p>Basic approach:</p><p> FFT computes x from x in O(n logn) time</p><p> compute top k coefficients in O(n) time.</p><p>Sparse FFT: directly computes k largest coefficients of x (approximately</p><p> formal def later)</p><p> Running time O(k log2 n) or faster</p><p> Sublinear time!</p><p>11 / 73</p></li><li><p>Sample complexity</p><p>Sample complexity=number of samples accessed in timedomain.</p><p>12 / 73</p></li><li><p>Sample complexity</p><p>In medical imaging (MRI, NMR), one measures Fouriercoefficients x of imaged object x (which is often sparse)</p><p>13 / 73</p></li><li><p>Sample complexity</p><p>In medical imaging (MRI, NMR), one measures Fouriercoefficients x of imaged object x (which is often sparse)</p><p>13 / 73</p></li><li><p>Sample complexity</p><p>Measure x Cn, compute the Inverse Discrete FourierTransform (IDFT) of x :</p><p>xi =</p><p>j[n]xj ij .</p><p>Given x Cn, compute the Discrete Fourier Transform (DFT) ofx :</p><p>xi =1n</p><p>j[n]</p><p>xj ij .</p><p>Sample complexity=number of samples accessed in timedomain.</p><p>Governs the measurement complexity of imaging process.</p><p>14 / 73</p></li><li><p>Sample complexity</p><p>Measure x Cn, compute the Inverse Discrete FourierTransform (IDFT) of x :</p><p>xi =</p><p>j[n]xj ij .</p><p>Given x Cn, compute the Discrete Fourier Transform (DFT) ofx :</p><p>xi =1n</p><p>j[n]</p><p>xj ij .</p><p>Sample complexity=number of samples accessed in timedomain.</p><p>Governs the measurement complexity of imaging process.</p><p>14 / 73</p></li><li><p>Sample complexity</p><p>Measure x Cn, compute the Inverse Discrete FourierTransform (IDFT) of x :</p><p>xi =</p><p>j[n]xj ij .</p><p>Given x Cn, compute the Discrete Fourier Transform (DFT)of x:</p><p>xi =1n</p><p>j[n]</p><p>xj ij .</p><p>Sample complexity=number of samples accessed in timedomain.</p><p>Governs the measurement complexity of imaging process.</p><p>15 / 73</p></li><li><p>Sample complexity</p><p>Measure x Cn, compute the Inverse Discrete FourierTransform (IDFT) of x :</p><p>xi =</p><p>j[n]xj ij .</p><p>Given x Cn, compute the Discrete Fourier Transform (DFT)of x:</p><p>xi =1n</p><p>j[n]</p><p>xj ij .</p><p>Sample complexity=number of samples accessed in timedomain.</p><p>Governs the measurement complexity of imaging process.</p><p>15 / 73</p></li><li><p>Given access to signal x in time domain, find best k -sparseapproximation to x approximately</p><p>Minimize</p><p>1. runtime</p><p>2. number of samples</p><p>16 / 73</p></li><li><p>Algorithms</p><p> Randomization Approximation Hashing Sketching . . .</p><p>Signal processing</p><p> Fourier transform Hadamard transform Filters Compressive sensing . . .</p><p>17 / 73</p></li><li><p> Lecture 1: summary of techniques fromGilbert-Guha-Indyk-Muthukrishnan-Strauss02, Akavia-Goldwasser-Safra03,</p><p>Gilbert-Muthukrishnan-Strauss05, Iwen10, Akavia10,</p><p>Hassanieh-Indyk-Katabi-Price12a, Hassanieh-Indyk-Katabi-Price12b</p><p> Lecture 2: Algorithm with O(k logn) runtime (noiselesscase) Hassanieh-Indyk-Katabi-Price12b</p><p> Lecture 3: Algorithm with O(k log2 n) runtime (noisy case)Hassanieh-Indyk-Katabi-Price12b</p><p> Lecture 4: Algorithm with O(k logn) sample complexityIndyk-Kapralov-Price14, Indyk-Kapralov14</p><p>18 / 73</p></li><li><p>Outline</p><p>1. Computing Fourier transform of 1-sparse signals fast</p><p>2. Sparsity k &gt; 1: main ideas and challenges</p><p>19 / 73</p></li><li><p>Outline</p><p>1. Computing Fourier transform of 1-sparse signals fast</p><p>2. Sparsity k &gt; 1: main ideas and challenges</p><p>20 / 73</p></li><li><p>Sparse Fourier Transform (k = 1)Warmup: x is exactly 1-sparse: xf = 0 when f 6= f for some f </p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>f </p><p>Note: signal is a pure frequency</p><p>Given: access to x</p><p>Need: find f and xf </p><p>21 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency, so xj = a f j</p><p>+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a</p><p>+noise</p><p>x1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f</p><p>+noise</p><p>Can read frequency from theangle!</p><p>f</p><p>unit circle</p><p>x0 = ax1 = a f </p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure</p><p>22 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency, so xj = a f j</p><p>+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a</p><p>+noise</p><p>x1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f</p><p>+noise</p><p>Can read frequency from theangle!</p><p>f</p><p>unit circle</p><p>x0 = ax1 = a f </p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure</p><p>22 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency, so xj = a f j</p><p>+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a</p><p>+noise</p><p>x1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f</p><p>+noise</p><p>Can read frequency from theangle!</p><p>f</p><p>unit circle</p><p>x0 = ax1 = a f </p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure</p><p>23 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency, so xj = a f j</p><p>+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a</p><p>+noise</p><p>x1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f</p><p>+noise</p><p>Can read frequency from theangle!</p><p>f</p><p>unit circle</p><p>x0 = ax1 = a f </p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure</p><p>24 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency, so xj = a f j</p><p>+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a</p><p>+noise</p><p>x1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f</p><p>+noise</p><p>Can read frequency from theangle!</p><p>f</p><p>unit circle</p><p>x0 = ax1 = a f </p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure</p><p>25 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency, so xj = a f j</p><p>+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a</p><p>+noise</p><p>x1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f</p><p>+noise</p><p>Can read frequency from theangle!</p><p>f</p><p>unit circle</p><p>x0 = ax1 = a f </p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure 26 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency+noise, so xj = a f j+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a+noisex1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f+noise</p><p>Can read frequency from theangle!</p><p>x0 = ax1 = a f </p><p>f</p><p>unit circle</p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure</p><p>27 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency+noise, so xj = a f j+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a+noisex1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f+noise</p><p>Can read frequency from theangle!</p><p>x0 = ax1 = a f </p><p>f</p><p>unit circle</p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure</p><p>28 / 73</p></li><li><p>Two-point samplingInput signal x is a pure frequency+noise, so xj = a f j+noise</p><p>Sample x0,x1</p><p>We have</p><p>x0 = a+noisex1 = a f</p><p>+noise</p><p>So</p><p>x1/x0 =f+noise</p><p>Can read frequency from theangle!</p><p>x0 = ax1 = a f </p><p>f</p><p>unit circle</p><p>Pro: constant time algorithmCon: depends heavily on the signal being pure</p><p>29 / 73</p></li><li><p>Sparse Fourier Transform (k = 1)Warmup part 2: x is 1-sparse plus noise</p><p>-0.0006</p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>0.0006</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noisehead</p><p>Note: signal is a pure frequency plus noise</p><p>Given: access to x</p><p>Need: find f and xf </p><p>Ideally, find pure frequency x that approximates x best</p><p>30 / 73</p></li><li><p>Sparse Fourier Transform (k = 1)Warmup part 2: x is 1-sparse plus noise</p><p>-0.0006</p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>0.0006</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noise</p><p>head</p><p>Note: signal is a pure frequency plus noise</p><p>Given: access to x</p><p>Need: find f and xf </p><p>Ideally, find pure frequency x that approximates x best</p><p>31 / 73</p></li><li><p>Sparse Fourier Transform (k = 1)Warmup part 2: x is 1-sparse plus noise</p><p>-0.0006</p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>0.0006</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noisehead</p><p>Note: signal is a pure frequency plus noise</p><p>Given: access to x</p><p>Need: find f and xf </p><p>Ideally, find pure frequency x that approximates x best</p><p>32 / 73</p></li><li><p>Sparse Fourier Transform (k = 1)Warmup part 2: x is 1-sparse plus noise</p><p>-0.0006</p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>0.0006</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noisehead</p><p>Note: signal is a pure frequency plus noise</p><p>Ideally, find pure frequency x that approximates x best:</p><p>min1sparse x </p><p>||x x ||2</p><p>= ||tail noise||2</p><p>33 / 73</p></li><li><p>Sparse Fourier Transform (k = 1)Warmup part 2: x is 1-sparse plus noise</p><p>-0.0006</p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>0.0006</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noise</p><p>head</p><p>Note: signal is a pure frequency plus noise</p><p>Ideally, find pure frequency x that approximates x best:</p><p>min1sparse x </p><p>||x x ||2</p><p>= ||tail noise||2</p><p>34 / 73</p></li><li><p>Sparse Fourier Transform (k = 1)Warmup part 2: x is 1-sparse plus noise</p><p>-0.0006</p><p>-0.0004</p><p>-0.0002</p><p>0</p><p>0.0002</p><p>0.0004</p><p>0.0006</p><p>-1000 -500 0 500 1000</p><p>time</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noise</p><p>head</p><p>Note: signal is a pure frequency plus noise</p><p>Ideally, find pure frequency x that approximates x best:</p><p>min1sparse x </p><p>||x x ||2 = ||tail noise||2</p><p>35 / 73</p></li><li><p>`2/`2 sparse recovery</p><p>Ideally, find pure frequency x that approximates x best</p><p>Need to allow approximation: find y such that</p><p>||x y ||2 C ||tail noise||2where C &gt; 1 is the approximation factor.</p><p>36 / 73</p></li><li><p>`2/`2 sparse recovery</p><p>Ideally, find pure frequency x that approximates x best</p><p>Need to allow approximation: find y such that</p><p>||x y ||2 3 ||tail noise||2</p><p>37 / 73</p></li><li><p>Approximation guaranteeFind y such that</p><p>||x y ||2 3 ||tail noise||2</p><p>Note: only meaningful if</p><p>||x ||2 &gt; 3 ||tail noise||2or, equivalently,</p><p>f 6=f |xf |2 |a|2</p><p>(assumethisforthelecture)</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>Assume that this holds for a small enough &gt; 0</p><p>38 / 73</p></li><li><p>Approximation guaranteeFind y such that</p><p>||x y ||2 3 ||tail noise||2</p><p>Note: only meaningful if</p><p>||x ||2 &gt; 3 ||tail noise||2or, equivalently,</p><p>f 6=f |xf |2 |a|2 (assumethisforthelecture)</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>Assume that this holds for a small enough &gt; 0</p><p>39 / 73</p></li><li><p>Approximation guaranteeFind y such that</p><p>||x y ||2 3 ||tail noise||2</p><p>Note: only meaningful if</p><p>||x ||2 &gt; 3 ||tail noise||2or, equivalently,</p><p>(assume this for the lecture)</p><p>f 6=f </p><p>|xf |2 |a|2</p><p>(assume this for the lecture)</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>40 / 73</p></li><li><p>Approximation guaranteeFind y such that</p><p>||x y ||2 3 ||tail noise||2</p><p>Note: only meaningful if</p><p>||x ||2 &gt; 3 ||tail noise||2or, equivalently,</p><p>(assume this for the lecture)</p><p>f 6=f </p><p>|xf |2 |a|2 (assume this for the lecture)</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>41 / 73</p></li><li><p>Approximation guaranteeFind y such that</p><p>||x y ||2 3 ||tail noise||2</p><p>Note: only meaningful if</p><p>||x ||2 &gt; 3 ||tail noise||2or, equivalently,</p><p>(assume this for the lecture)</p><p>f 6=f </p><p>|xf |2 |a|2 (assume this for the lecture)</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>42 / 73</p></li><li><p>Approximation guaranteeFind y such that</p><p>||x y ||2 3 ||tail noise||2</p><p>Note: only meaningful if</p><p>||x ||2 &gt; 3 ||tail noise||2or, equivalently,</p><p>(assume this for the lecture)</p><p>f 6=f </p><p>|xf |2 |a|2 (assume this for the lecture)</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noisehead</p><p>43 / 73</p></li><li><p>A robust algorithm for finding the heavy hitter</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noisehead</p><p>Assume that</p><p>f 6=f |xf |2 |a|2</p><p>Describe algorithm for the noiseless case first (= 0)</p><p>Suppose that xj = a f j .</p><p>Will find f bit by bit (binary search).</p><p>44 / 73</p></li><li><p>A robust algorithm for finding the heavy hitter</p><p>0</p><p>0.2</p><p>0.4</p><p>0.6</p><p>0.8</p><p>1</p><p>-1000 -500 0 500 1000</p><p>frequency</p><p>tail noisehead</p><p>Assume that</p><p>f 6=f |xf |2 |a|2</p><p>Describe algorithm for the noiseless case first (= 0)</p><p>Suppose that xj = a f j .</p><p>Will find f bit by bit (binary search).44 / 73</p></li><li><p>Bit 0Suppose that f = 2f +b, we want bCompute</p><p> x0 = a xn/2 = a f</p><p>(n/2)</p><p>ClaimWe have</p><p>xn/2 = x0 (1)b</p><p>(Even frequencies are n/2-periodic, odd are n/2-antiperiodic)</p><p>Proof.</p><p>xn/2 = a f(n/2) = a (1)2f+b = x0 (1)b</p><p>Will need arbitrary r s for the noisy setting</p><p>45 / 73</p></li><li><p>Bit 0Suppose that f = 2f +b, we want bCompute</p><p> x0 = a xn/2 = a f</p><p>(n/2)</p><p>ClaimWe have</p><p>xn/2 = x0 (1)b</p><p>(Even frequencies are n/2-periodic, odd are n/2-antiperiodic)</p><p>Proof.</p><p>xn/2 = a f(n/2) = a (1)2f+b = x0 (1)b</p><p>Will need arbitrary r s for the noisy setting</p><p>45 / 73</p></li><li><p>Bit 0Suppose that f = 2f +b, we want bCompute</p><p> x0+r = a fr xn/2+r = a f</p><p>(n/2+r)</p><p>ClaimFor all r [n] we have</p><p>xn/2+r = x0+r (1)b</p><p>(Even frequencies are n/2-periodic, odd are n/2-antiperiodic)</p><p>Proof.</p><p>xn/2+r = a f(n/2+r) = a fr (1)2f+b = x0+r (1)b</p><p>Will need arbitrary r s for the noisy setting</p><p>46 / 73</p></li><li><p>Bit 0Suppose that f = 2f +b, we want bCompute</p><p> xr = a fr xn/2+r = a f</p><p>(n/2+r)</p><p>ClaimFor all r [n] we have</p><p>xn/2+r = xr (1)b</p><p>(Even frequencies are n/2-periodic, odd are n/2-antiperiodic)</p><p>Proof.</p><p>xn/2+r = a f(n/2+r) = a fr (1)2f+b = xr (1)b</p><p>Will need arbitrary r s for the noisy setting</p><p>47 / 73</p></li><li><p>Bit 0Suppose that f = 2f +b, we want bCompute</p><p> xr = a fr xn/2+r = a f</p><p>(n/2+r)</p><p>ClaimFor all r [n] we have</p><p>xn/2+r = xr (1)b</p><p>(Even frequencies are n/2-periodic, odd are n/2-antiperiodic)</p><p>Proof.</p><p>xn/2+r = a f(n/2+r) = a fr (1)2f+b = xr (1)b</p><p>Will need arbitrary r s for the noisy setting</p><p>48 / 73</p></li><li><p>Bit 0 test</p><p>Set</p><p>and</p><p>b0 0 if |xn/2+r +xr | &gt; |xn/2+r xr |</p><p>Set and</p><p>b0 1 o.w.</p><p>Correctness:</p><p>If b = 0, then |xn/2+r +xr | = 2|xr | = 2|a|</p><p>If b = 0,</p>

Recommended

View more >