论文标题
改进的傅立叶 - 帕克斯信号的重建
Improved Reconstruction for Fourier-Sparse Signals
论文作者
论文摘要
我们重新讨论了傅立叶式信号重建的经典问题 - \ emph {设置查询}问题的变体 - 该问题要求有效地重建（一个子集）a $ d $二维傅立叶傅立叶sparse Signal（$ \ | \ | \ | \ hat {x}（x}（x}（x}（x}（x}（x）\ | _0 \ | _0 \ | _ noim） $ x（t）$在时域中。我们通过开发稀疏的傅立叶变换理论（SFT）来为位于\ emph {lattice}上的频率提供一个统一的框架，该频率可以看作是在离散域和连续域之间的``半连续''版本的``半连续''版本。使用此框架，我们获得以下结果： $ \ bullet $ **无维傅里叶稀疏恢复**我们提出了一个以$ o（k^{ω+1}）$重建时间为单位的示例 - 最佳傅立叶Set-Query算法，\ emph {Indeppented}信号的长度（$ n $）（$ n $）和$ \ ell_ \ ell_ fty $ -norm。 This complements the state-of-art algorithm of [Kapralov, STOC 2017], whose reconstruction time is $\tilde{O}(k \log^2 n \log R^*)$, where $R^* \approx \|\hat{x}\|_\infty$ is a signal-dependent parameter, and the algorithm is limited to low dimensions.相比之下，我们的算法适用于任意$ d $尺寸，从而减轻$ \ exp（d）$ blowup的解码时间仅在$ d $中线性。我们算法中的关键组成部分是傅立叶基础的快速光谱稀疏。 $ \ bullet $ **高准确度傅立叶插值**在一个维度中，我们设计了一个poly time $（3+ \ sqrt {2} +ε）$ - 连续傅立叶插值的近似算法。这绕过了所有以前所有算法的障碍[Price and Song，Focs，2015年，Chen，Kane，Price和Song，Focs 2016]，该算法仅在此基本问题上实现$ C> 100美元的近似值。我们的主要贡献是基于\ emph {noise取消}的分层频率分解的新分析工具。
We revisit the classical problem of Fourier-sparse signal reconstruction -- a variant of the \emph{Set Query} problem -- which asks to efficiently reconstruct (a subset of) a $d$-dimensional Fourier-sparse signal ($\|\hat{x}(t)\|_0 \leq k$), from minimum \emph{noisy} samples of $x(t)$ in the time domain. We present a unified framework for this problem by developing a theory of sparse Fourier transforms (SFT) for frequencies lying on a \emph{lattice}, which can be viewed as a ``semi-continuous'' version of SFT in between discrete and continuous domains. Using this framework, we obtain the following results: $\bullet$ **Dimension-free Fourier sparse recovery** We present a sample-optimal discrete Fourier Set-Query algorithm with $O(k^{ω+1})$ reconstruction time in one dimension, \emph{independent} of the signal's length ($n$) and $\ell_\infty$-norm. This complements the state-of-art algorithm of [Kapralov, STOC 2017], whose reconstruction time is $\tilde{O}(k \log^2 n \log R^*)$, where $R^* \approx \|\hat{x}\|_\infty$ is a signal-dependent parameter, and the algorithm is limited to low dimensions. By contrast, our algorithm works for arbitrary $d$ dimensions, mitigating the $\exp(d)$ blowup in decoding time to merely linear in $d$. A key component in our algorithm is fast spectral sparsification of the Fourier basis. $\bullet$ **High-accuracy Fourier interpolation** In one dimension, we design a poly-time $(3+ \sqrt{2} +ε)$-approximation algorithm for continuous Fourier interpolation. This bypasses a barrier of all previous algorithms [Price and Song, FOCS 2015, Chen, Kane, Price and Song, FOCS 2016], which only achieve $c>100$ approximation for this basic problem. Our main contribution is a new analytic tool for hierarchical frequency decomposition based on \emph{noise cancellation}.
