Deterministic sparse FFT for M-sparse vectors
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.
- Deterministic sparse sublinear FFT with improved numerical stability
- A deterministic sparse FFT algorithm for vectors with small support
- Real sparse fast DCT for vectors with short support
- A sparse fast Fourier algorithm for real non-negative vectors
- A deterministic sparse FFT for functions with structured Fourier sparsity
- A deterministic sparse FFT algorithm for vectors with small support
- A sparse fast Fourier algorithm for real non-negative vectors
- Combinatorial sublinear-time Fourier algorithms
- Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
- Diversification improves interpolation
- Fast QR factorization of Vandermonde matrices
- Hilbert's Inequality
- scientific article; zbMATH DE number 6770709 (Why is no real title available?)
- Improved approximation guarantees for sublinear-time Fourier algorithms
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- Nearly optimal sparse Fourier transform
- On perfect conditioning of Vandermonde matrices on the unit circle
- Super-resolution, extremal functions and the condition number of Vandermonde matrices
- Symbolic-numeric sparse interpolation of multivariate polynomials
- A deterministic sparse FFT for functions with structured Fourier sparsity
- High-dimensional sparse Fourier algorithms
- Deterministic sparse sublinear FFT with improved numerical stability
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
- The uniform sparse FFT with application to PDEs with random coefficients
- A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
- Sparse fast DCT for vectors with one-block support
- Real sparse fast DCT for vectors with short support
- A sparse fast Fourier algorithm for real non-negative vectors
- A deterministic sparse FFT algorithm for vectors with small support
- Optimized Spectrum Permutation for the Multidimensional Sparse FFT
- Performance of the multiscale sparse fast Fourier transform algorithm
- Multiscale matrix pencils for separable reconstruction problems
- Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms
- Fast interpolation and multiplication of unbalanced polynomials
This page was built for publication: Deterministic sparse FFT for \(M\)-sparse vectors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751061)
