Indyk, Piotr; Kapralov, Michael; Price, Eric (Nearly) sample-optimal sparse Fourier transform. (English) Zbl 1455.94085 Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 480-499 (2014). Cited in 9 Documents MSC: 94A20 Sampling theory in information and communication theory 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 42B10 Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type 41A30 Approximation by other special function classes 68W20 Randomized algorithms Keywords:compressive sensing; Fourier sampling; sparse recovery Citations:Zbl 1286.94046 PDFBibTeX XMLCite \textit{P. Indyk} et al., in: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5--7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 480--499 (2014; Zbl 1455.94085) Full Text: DOI Link