Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
From MaRDI portal
Publication:4575600
DOI10.1137/1.9781611974331.ch23zbMath1412.94028arXiv1504.07648MaRDI QIDQ4575600
Publication date: 16 July 2018
Published in: ACM Transactions on Algorithms, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.07648
sketching; explicit constructions; sparse recovery; pseudorandomness; sublinear time algorithms; sparse Fourier transform
94A12: Signal theory (characterization, reconstruction, filtering, etc.)
65T50: Numerical methods for discrete and fast Fourier transforms
65Y20: Complexity and performance of numerical algorithms