Deterministic sparse FFT for M-sparse vectors
Deterministic sparse FFT for M-sparse vectors
复制标题
DOI：
10.1007/s11075-017-0370-5
复制
发表时间：
2017-07
影响因子：
2.1
通讯作者：
G. Plonka-Hoch;Katrin Wannenwetsch;A. Cuyt;Wen-shin Lee
中科院分区：
文献类型：
--
作者：
G. Plonka-Hoch;Katrin Wannenwetsch;A. Cuyt;Wen-shin Lee
在本文中，我们推导出一个新的确定性稀疏快速傅里叶逆变换（FFT）算法的情况下，得到的向量是稀疏的。稀疏性不需要预先知道，但将在算法期间确定。若待重构向量是M-稀疏的，则该方法的复杂度至多为M2 <N，当M2 ≥N时，福尔斯又回到通常的算法。该方法基于分治法，在每次迭代步骤j中，如果M2 <2 j，可能需要求解最大为M × M的范德蒙方程组。为了保证Vandermonde系统的稳定性，我们建议采用适当选择的参数σ来确定单位圆上Vandermonde矩阵的节点。
In this paper, we derive a new deterministic sparse inverse fast Fourier transform (FFT) algorithm for the case that the resulting vector is sparse. The sparsity needs not to be known in advance but will be determined during the algorithm. If the vector to be reconstructed isM-sparse, then the complexity of the method is at mostifM2<Nand falls back to the usualalgorithm forM2≥N. The method is based on the divide-and-conquer approach and may require the solution of a Vandermonde system of size at mostM×Mat each iteration stepjifM2< 2j. To ensure the stability of the Vandermonde system, we propose to employ a suitably chosen parameterσthat determines the knots of the Vandermonde matrix on the unit circle.