A sparse fast Fourier algorithm for real non-negative vectors
A sparse fast Fourier algorithm for real non-negative vectors
复制标题
实数非负向量的稀疏快速傅立叶算法
DOI：
10.1016/j.cam.2017.03.019
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Katrin Wannenwetsch
中科院分区：
文献类型：
--
作者：
Gerlind Plonka;Katrin Wannenwetsch
本文提出了一种新的快速傅立叶变换来从其离散傅里叶变换x∈=F N x̂CN中恢复实数非负信号x∈R+N。如果信号x看起来有一个短的支持度，即在长度为m<；N的支持区间外消失，则该算法的算术复杂度仅为O(m log m log(N/m))，并且需要O(m log(N/m))个傅立叶样本。与其他方法不同的是，不需要关于向量x的稀疏性或支持范围的先验知识。该算法自动识别并利用向量可能的短支持，并且如果x具有(几乎)完全支持，则退回到通常的基2 FFT算法。数值算例表明了该算法的数值稳定性。
In this paper we propose a new fast Fourier transform to recover a real non-negative signal x∈ R+ N from its discrete Fourier transform x ̂= F N x∈ C N. If the signal x appears to have a short support, ie, vanishes outside a support interval of length m< N, then the algorithm has an arithmetical complexity of only O (m log m log (N/m)) and requires O (m log (N/m)) Fourier samples for this computation. In contrast to other approaches there is no a priori knowledge needed about sparsity or support bounds for the vector x. The algorithm automatically recognizes and exploits a possible short support of the vector and falls back to a usual radix-2 FFT algorithm if x has (almost) full support. The numerical stability of the proposed algorithm is shown by numerical examples.
通过近似算术级数进行确定性稀疏傅立叶逼近
影响因子：
2.5
作者：
Adi Akavia
通讯作者：
Adi Akavia
关于快速傅立叶变换线性复杂度下界的注记
DOI：
--
发表时间：
1973
期刊：
JACM
影响因子：
--
作者：
Jacques Morgenstern
通讯作者：
Jacques Morgenstern