(Nearly) Sample-Optimal Sparse Fourier Transform

DOI10.1137/1.9781611973402.36zbMath1455.94085OpenAlexW4242004838MaRDI QIDQ5383996

Eric Price, Michael Kapralov, 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

compressive sensingsparse recoveryFourier sampling

Mathematics Subject Classification ID

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

Related Items (9)

A deterministic sparse FFT algorithm for vectors with small support ⋮ Tighter Fourier Transform Lower Bounds ⋮ High-dimensional sparse FFT based on sampling along multiple rank-1 lattices ⋮ Performance of the multiscale sparse fast Fourier transform algorithm ⋮ Fast Haar transforms for graph neural networks ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Paraunitary matrices, entropy, algebraic condition number and Fourier computation ⋮ Quantum learning of concentrated Boolean functions

This page was built for publication: (Nearly) Sample-Optimal Sparse Fourier Transform