Sample-Optimal Fourier Sampling in Any Constant Dimension

Sample-Optimal Fourier Sampling in Any Constant Dimension

We give an algorithm for ℓ[subscript 2]/ℓ[subscript 2] sparse recovery from Fourier measurements using O(k log N) samples, matching the lower bound of Do Ba-Indyk-Price-Woodruff'10 for non-adaptive algorithms up to constant factors for any k ≤ N [superscript 1-δ]. The algorithm runs in Õ(N) ti...

Full description

Bibliographic Details
Main Authors: Indyk, Piotr, Kapralov, Mikhail
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Institute of Electrical and Electronics Engineers (IEEE) 2017
Online Access:http://hdl.handle.net/1721.1/110932
https://orcid.org/0000-0002-7983-9524

Internet

http://hdl.handle.net/1721.1/110932
https://orcid.org/0000-0002-7983-9524

Similar Items