论文标题
确定性稀疏的sublinear FFT，具有改进的数值稳定性
Deterministic Sparse Sublinear FFT with Improved Numerical Stability
论文作者
论文摘要
在本文中，我们扩展了Plonka等人的确定性sublinear FFT算法。 （2018）对于$ M $ -SPARSE VECTORS的快速重建$ {\ MathBf X} $长度$ n = 2^J $，我们假设离散傅里叶傅里叶变换的所有组件$ \ hat {\ mathbf x} = {\ Mathbf f} _ {n} _ {n} _ {n} _ { $ {\ mathbf x} $的稀疏性不需要先验，而是由算法确定的。如果稀疏$ m $大于$ 2^{j/2} $，则该算法变成了常见的FFT算法，带有运行时$ {\ Mathcal O}（n \ log n）$。对于$ m^{2} <n $，算法的运行时为$ {\ Mathcal O}（m^2 \，\ log n）$。 Plonka等人中提出的方法的修改。 （2018年）导致了迭代重建中使用的Vandermonde矩阵的状况数量的显着改善。我们的数值实验表明，我们的修改对算法的稳定性产生了巨大影响。而Plonka等人的算法。 （2018年）由于数值不稳定性而开始对$ m> 20 $不可靠，因此修改后的算法在数值上仍然是$ m = 200 $的数字稳定。
In this paper we extend the deterministic sublinear FFT algorithm in Plonka et al. (2018) for fast reconstruction of $M$-sparse vectors ${\mathbf x}$ of length $N= 2^J$, where we assume that all components of the discrete Fourier transform $\hat{\mathbf x}= {\mathbf F}_{N} {\mathbf x}$ are available. The sparsity of ${\mathbf x}$ needs not to be known a priori, but is determined by the algorithm. If the sparsity $M$ is larger than $2^{J/2}$, then the algorithm turns into a usual FFT algorithm with runtime ${\mathcal O}(N \log N)$. For $M^{2} < N$, the runtime of the algorithm is ${\mathcal O}(M^2 \, \log N)$. The proposed modifications of the approach in Plonka et al. (2018) lead to a significant improvement of the condition numbers of the Vandermonde matrices which are employed in the iterative reconstruction. Our numerical experiments show that our modification has a huge impact on the stability of the algorithm. While the algorithm in Plonka et al. (2018) starts to be unreliable for $M>20$ because of numerical instabilities, the modified algorithm is still numerically stable for $M=200$.
