Deterministic sparse FFT for M-sparse vectors

DOI10.1007/S11075-017-0370-5MaRDI QIDQ1751061zbMATH OpenOpenAlexFDO

Authors Katrin Wannenwetsch, Wen-shin Lee, Gerlind Plonka, Annie Cuyt

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)

Recommendations

• 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

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 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
• 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

Cited in

(14)

• Sparse fast DCT for vectors with one-block support
• Multiscale matrix pencils for separable reconstruction problems
• A deterministic sparse FFT for functions with structured Fourier sparsity
• A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
• High-dimensional sparse Fourier algorithms
• Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms
• Deterministic sparse sublinear FFT with improved numerical stability
• The uniform sparse FFT with application to PDEs with random coefficients
• Real sparse fast DCT for vectors with short support
• 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
• A sparse fast Fourier algorithm for real non-negative vectors
• Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables

Describes a project that uses

Uses Software

• Sparse FFT small support

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)