Improved time bounds for near-optimal sparse Fourier representations 论文
摘要
•We study the problem of finding a Fourier representation <b>R </b>of <i>m</i> terms for a given discrete signal <b>A</b> of length<i> N</i>. The Fast Fourier Transform (FFT) can find the optimal <i>N</i>-term representation in time <i>O</i>(<i>N </i>log <i>N</i>) time, but our goal is to get <i>sublinear</i> time algorithms when <i>m</i> << <i>N</i>. Suppose ||<b>A</b>||<sub>2</sub> ≤<i>M</i>||<b>A</b>-<b>R</b><sub>opt</sub>||<sub>2</sub>, where <b>R</b><sub>opt</sub> is the optimal output. The previously best known algorithms output <b>R</b> such that ||<b>A</b>-<b>R</b>||<sup>2</sup><sub>2</sub>≤(1+ε))||<b>A</b>-<b>R</b><sub>opt</sub>||<sup>2</sup><sub>2</sub> with probability at least 1-δ in time* poly(<i>m</i>,log(1/δ),log <i>N</i>,log <i>M</i>,1/ε). Although this is sublinear in the input size, the dominating expression is the polynomial factor in <i>m</i> which, for published algorithms, is greater than or equal to the bottleneck at <i>m</i><sup>2</sup> that we identify below. Our experience with these algorithms shows that this is serious limitation in theory and in practice. Our algorithm beats this <i>m</i><sup>2</sup> bottleneck. Our main result is a significantly improved algorithm for this problem and the <i>d</i>-dimensional analog. Our algorithm outputs an <b>R</b> with the same approximation guarantees but it runs in time <i>m</i>•poly(log(1/δ),log <i>N</i>,log <i>M</i>,1/ε). A version of the algorithm holds for all <i>N</i>, though the details differ slightly according to the factorization of <i>N</i>. For the <i>d</i>-dimensional problem of size <i>N</i><sub>1</sub> × <i>N</i><sub>2</sub> × •• × <i>N</i><sub>d</sub>, the linear-in-<i>m</i> algorithm extends efficiently to higher dimensions for certain factorizations of the <i>N<sub>i</sub></i>'s; we give a quadratic-in-<i>m</i> algorithm that works for any values of <i>N<sub>i</sub></i>'s. This article replaces several earlier, unpublished drafts.