(Nearly) sample-optimal sparse Fourier transform

DOI10.1137/1.9781611973402.36MaRDI QIDQ5383996zbMATH OpenOpenAlexFDO

Authors Michael Kapralov, Eric Price, Piotr Indyk

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/114162

zbMATH Keywords

sparse recoverycompressive sensingFourier sampling

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Randomized algorithms (68W20) Approximation by other special function classes (41A30) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) Sampling theory in information and communication theory (94A20)

Recommendations

• Nearly optimal sparse Fourier transform
• Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
• Combinatorial sublinear-time Fourier algorithms
• scientific article; zbMATH DE number 7053345
• Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis

Cited in

(37)

• Fast Haar transforms for graph neural networks
• Tighter Fourier transform lower bounds
• Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
• Sparse fast trigonometric transforms
• Quantum learning of concentrated Boolean functions
• scientific article; zbMATH DE number 7053345 (Why is no real title available?)
• Approximation and Compression With Sparse Orthonormal Transforms
• Paraunitary matrices, entropy, algebraic condition number and Fourier computation
• A deterministic sparse FFT for functions with structured Fourier sparsity
• A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
• Combinatorial sublinear-time Fourier algorithms
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
• scientific article; zbMATH DE number 6796498 (Why is no real title available?)
• High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
• Sparse Fourier Transform via Butterfly Algorithm
• Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
• What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid
• Nearly optimal sparse Fourier transform
• Fast interpolation and multiplication of unbalanced polynomials
• An adaptive sublinear-time block sparse Fourier transform
• A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing
• What's the frequency, Kenneth?: sublinear Fourier sampling off the grid
• Deterministic sparse Fourier transform with an _ guarantee
• Sparse recovery for orthogonal polynomial transforms
• SCAN-MUSIC: an efficient super-resolution algorithm for large-scale single snapshot line spectral estimation
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• A deterministic sparse FFT algorithm for vectors with small support
• Optimized Spectrum Permutation for the Multidimensional Sparse FFT
• The sparse Fourier transform: theory and practice
• Dimension-independent sparse Fourier transform
• Performance of the multiscale sparse fast Fourier transform algorithm
• Explicit universal sampling sets in finite vector spaces
• Sparse generalized Fourier transforms
• Sparse Discrete Fractional Fourier Transform and Its Applications
• Multiscale high-dimensional sparse Fourier algorithms for noisy data

This page was built for publication: (Nearly) sample-optimal sparse Fourier transform

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