Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
From MaRDI portal
Publication:5361835
DOI10.1145/2897518.2897650zbMath1377.94011arXiv1604.00845OpenAlexW783404226MaRDI QIDQ5361835
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1604.00845
Analysis of algorithms and problem complexity (68Q25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for discrete and fast Fourier transforms (65T50) Randomized algorithms (68W20)
Related Items (4)
Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time ⋮ Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables ⋮ A note on the high-dimensional sparse Fourier transform in the continuous setting*
This page was built for publication: Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
