A deterministic sparse FFT algorithm for vectors with small support
A deterministic sparse FFT algorithm for vectors with small support
复制标题
DOI：
10.1007/s11075-015-0028-0
复制
发表时间：
2015-04
影响因子：
2.1
通讯作者：
G. Plonka-Hoch;Katrin Wannenwetsch
中科院分区：
文献类型：
--
作者：
G. Plonka-Hoch;Katrin Wannenwetsch
本文考虑了已知信号轴在长度<N的支撑区间外消失的特殊情况。如果支撑点长度或支撑点长度的一个好的界是先验已知的，我们从支撑点长度的离散傅里叶变换中推导出一个次线性的确定性算法。在精确傅立叶测量的情况下，我们只需要（mm）算术运算。对于噪声测量，我们提出了一种稳定（mN）算法。
In this paper we consider the special case where a signalxis known to vanish outside a support interval of lengthm<N. If the support lengthmofxor a good bound of it is a-priori known we derive a sublinear deterministic algorithm to computexfrom its discrete Fourier transform. In case of exact Fourier measurements we require only(mm) arithmetical operations. For noisy measurements, we propose a stable(mN) algorithm.