Deterministic sparse FFT for \(M\)-sparse vectors
type: Item
instance of: scholarly article
title: Deterministic sparse FFT for \(M\)-sparse vectors
zbMATH Open document ID: 1478.65146
author: Katrin Wannenwetsch
author: Wen-shin Lee
author: Gerlind Plonka
author: Annie Cuyt
published in: Numerical Algorithms
publication date: 2018-05-23T00:00:00Z
review text: In this interesting paper, the authors present a new deterministic sparse (inverse) fast Fourier transform (FFT), where the resulting vector \(\mathbf x \in {\mathbb C}^N\) with \(N = 2^J\) is \(M\)-sparse, i.e., \(\mathbf x\) contains only \(M\) nonzero components. This new algorithm which generalizes the sparse FFT of \textit{G. Plonka} and \textit{K. Wannenwetsch} [Numer. Algorithms 71, No. 4, 889--905 (2016; Zbl 1341.65056)] is based on a multi-scale reconstruction of \(\mathbf x\) and uses the solutions of well-conditioned Vandermonde-like systems in each iteration step. The unknown sparsity \(M\) is determined during the algorithm. The computational costs of this method is at most \({\mathcal O}(M^2\,\log N)\) if \(M^2 < N\) and falls back to \(\mathcal{O}(N\,\log N)\) if \(M^2 \geq N\). Numerical tests illustrate the performance of this method.
reviewed by: Manfred Tasche
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 94A12
zbMATH DE Number: 6871983
zbMATH Keywords: sparse fast Fourier transform
zbMATH Keywords: sparse FFT
zbMATH Keywords: deterministic algorithm
zbMATH Keywords: reconstruction of sparse vectors
zbMATH Keywords: Vandermonde systems
zbMATH Keywords: sparse signals
describes a project that uses: Sparse FFT small support
MaRDI profile type: Publication
full work available at URL: s11075-017-0370-5
OpenAlex ID: W2732514310
cites work: Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
cites work: Q5355340
cites work: On perfect conditioning of Vandermonde matrices on the unit circle
cites work: Fast QR factorization of Vandermonde matrices
cites work: Symbolic-numeric sparse interpolation of multivariate polynomials
cites work: Diversification improves interpolation
cites work: Nearly optimal sparse fourier transform
cites work: Combinatorial sublinear-time Fourier algorithms
cites work: Improved approximation guarantees for sublinear-time Fourier algorithms
cites work: Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
cites work: Hilbert's Inequality
cites work: A sparse fast Fourier algorithm for real non-negative vectors
cites work: A deterministic sparse FFT algorithm for vectors with small support
cites work: Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
DOI: 10.1007/S11075-017-0370-5
description: scientific article; zbMATH DE number 6871983