Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

DOI10.1137/1.9781611974331.ch23zbMath1412.94028arXiv1504.07648OpenAlexW2950308398MaRDI QIDQ4575600

Mahdi Cheraghchi, Piotr Indyk

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

zbMATH Keywords

sketchingexplicit constructionssparse recoverypseudorandomnesssublinear time algorithmssparse Fourier transform

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20)

Related Items (2)

Simple Codes and Sparse Recovery with Fast Decoding ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity

This page was built for publication: Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform