Deterministic Sparse Sublinear FFT with Improved Numerical Stability
2021-03-11 | journal article. A publication with affiliation to the University of Göttingen.
Jump to: Cite & Linked | Documents & Media | Details | Version history
Documents & Media
Details
- Authors
- Plonka, Gerlind; von Wulffen, Therese
- Abstract
- 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$.
- Issue Date
- 11-March-2021
- Journal
- Results in Mathematics
- Project
- RTG 2088: Research Training Group 2088 Discovering structure in complex data: Statistics meets Optimization and Inverse Problems
- Organization
- Institut für Numerische und Angewandte Mathematik
- Working Group
- RG Plonka-Hoch (Mathematical Signal and Image Processing)
- ISSN
- 1422-6383
- eISSN
- 1420-9012
- Language
- English
- Sponsor
- Deutsche Forschungsgemeinschaft http://dx.doi.org/10.13039/501100001659
- Notes
- This publication is with permission of the rights owner freely accessible due to an consortial licence with the publisher via the green way respectively.