Deterministic sparse sublinear FFT with improved numerical stability

DOI10.1007/S00025-020-01330-0MaRDI QIDQ2038594zbMATH OpenOpenAlexFDO

Authors Therese von Wulffen, Gerlind Plonka

Publication date 7 July 2021

Published in Results in Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2004.11097

zbMATH Keywords

discrete Fourier transformVandermonde matricessublinear algorithmsparse FFT

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: In this paper we extend the deterministic sublinear FFT algorithm in Plonka et al. (2018) for fast reconstruction of $M$-sparse vectors $mathbfx$ of length $N=2^J$, where we assume that all components of the discrete Fourier transform $hatmathbfx={mathbfF}_{N}mathbfx$ are available. The sparsity of $mathbfx$ 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 $mathcalO(NlogN)$. For $M^2<N$, the runtime of the algorithm is $mathcalO(M^2,logN)$. 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$.

Recommendations

• Deterministic sparse FFT for M-sparse vectors
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• A deterministic sparse FFT algorithm for vectors with small support
• A deterministic sparse FFT for functions with structured Fourier sparsity
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees

Cites work

• scientific article; zbMATH DE number 6770709 (Why is no real title available?)
• A deterministic sparse FFT algorithm for vectors with small support
• A multiscale sub-linear time Fourier algorithm for noisy data
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
• A sparse fast Fourier algorithm for real non-negative vectors
• Approximate formulas for some functions of prime numbers
• Combinatorial sublinear-time Fourier algorithms
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• Deterministic sparse FFT for M-sparse vectors
• Fast QR factorization of Vandermonde matrices
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Numerical Fourier analysis
• On perfect conditioning of Vandermonde matrices on the unit circle
• Real sparse fast DCT for vectors with short support
• Sparse fast DCT for vectors with one-block support
• Super-resolution, extremal functions and the condition number of Vandermonde matrices

Cited in

(5)

• Deterministic sparse FFT for M-sparse vectors
• Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• scientific article; zbMATH DE number 1555403 (Why is no real title available?)
• A deterministic sparse FFT algorithm for vectors with small support

Describes a project that uses

Uses Software

• DCT_shortsupp_oneblock
• Sparse FFT small support

This page was built for publication: Deterministic sparse sublinear FFT with improved numerical stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2038594)