Deterministic sparse FFT for \(M\)-sparse vectors

DOI10.1007/s11075-017-0370-5zbMath1478.65146OpenAlexW2732514310MaRDI QIDQ1751061

Wen-Shin Lee, Katrin Wannenwetsch, Annie A. M. Cuyt, Gerlind Plonka-Hoch

Publication date: 23 May 2018

Published in: Numerical Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11075-017-0370-5

zbMATH Keywords

deterministic algorithmsparse signalssparse fast Fourier transformVandermonde systemsreconstruction of sparse vectorssparse FFT

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items

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, A deterministic sparse FFT for functions with structured Fourier sparsity, High-dimensional sparse Fourier algorithms, Sparse fast DCT for vectors with one-block support, 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, Real sparse fast DCT for vectors with short support

Uses Software

• Sparse FFT small support

Cites Work

• Unnamed Item
• A deterministic sparse FFT algorithm for vectors with small support
• Combinatorial sublinear-time Fourier algorithms
• Fast QR factorization of Vandermonde matrices
• Improved approximation guarantees for sublinear-time Fourier algorithms
• A sparse fast Fourier algorithm for real non-negative vectors
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• On perfect conditioning of Vandermonde matrices on the unit circle
• Hilbert's Inequality
• Diversification improves interpolation
• Nearly optimal sparse fourier transform
• Symbolic-numeric sparse interpolation of multivariate polynomials