Fetching the paper…
Reading the bibliography…
We revisit the classical problem of Fourier-sparse signal reconstruction -- a variant of the \emph{Set Query} problem -- which asks to efficiently reconstruct (a subset of) a $d$-dimensional Fourier-sparse signal ($\|\hat{x}(t)\|_0 \leq k$), from minimum \emph{noisy} samples of $x(t)$ in the time domain.
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations
Herman Chernoff · 1952
Earlier work this paper cites.
An algorithm for the machine calculation of complex fourier series
James W Cooley and John W Tukey · 1965
Earlier work this paper cites.
A note on the volume of a simplex
P Stein · 1966
Earlier work this paper cites.
The New Physical Optics Notebook: Tutorials in Fourier Optics
George O Reynolds · 1989
Earlier work this paper cites.
Image compression using the discrete cosine transform
Andrew B. Watson · 1994
Earlier work this paper cites.
Signals & systems
Alan V Oppenheim, Alan S Willsky, Syed Hamid Nawab, Gloria Mata Hernández, et al · 1997
Earlier work this paper cites.
Lecture notes for ee 261 the fourier transform and its applications
Brad Osgood · 2002
Earlier work this paper cites.
Nikolskii-type inequalities for shift invariant function spaces
Peter Borwein and Tamás Erdélyi · 2006
Earlier work this paper cites.
Compressed sensing
D.L. Donoho · 2006
Earlier work this paper cites.
Mri reconstruction using discrete fourier transform: a tutorial
Abiodun M Aibinu, Momoh-Jimoh E Salami, Amir A Shafie, and Athaur R Najeeb · 2008
Earlier work this paper cites.
Two turán type inequalities
Géza Kós · 2008
Earlier work this paper cites.
Lecture notes: Fourier transform properties
Alan V. Oppenheim · 2011
Earlier work this paper cites.
Efficient sketches for the set query problem
Eric Price · 2011
Earlier work this paper cites.
Computational fourier optics: a MATLAB tutorial
David George Voelz · 2011
Earlier work this paper cites.
Twice-ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.
Nearly optimal sparse fourier transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price · 2012
Cited alongside, same era.
Nearly optimal sparse fourier transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price · 2012
Cited alongside, same era.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Cited alongside, same era.
Sample-optimal average-case sparse fourier transform in two dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, and Lixin Shi · 2013
Cited alongside, same era.
Recent developments in the sparse fourier transform: A compressed fourier transform for big data
Anna C. Gilbert, Piotr Indyk, Mark A. Iwen, and Ludwig Schmidt · 2014
Cited alongside, same era.
Fourier-sparse interpolation without a frequency gap
Xue Chen, Daniel M Kane, Eric Price, and Zhao Song · 2016
Later among the works it cites.
Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
Michael Kapralov · 2016
Later among the works it cites.
Integer optimization and lattices
Thomas Rothvoss · 2016
Later among the works it cites.
Sample efficient estimation and recovery in sparse FFT via isolation on average
Michael Kapralov · 2017
Later among the works it cites.
Active regression via linear-sample sparsification
Xue Chen and Eric Price · 2019
Later among the works it cites.
Estimating the frequency of a clustered signal
Xue Chen and Eric Price · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Sample-optimal Fourier sampling in any constant dimension
Piotr Indyk and Michael Kapralov · 2014
Cited alongside, same era.
(nearly) sample-optimal sparse fourier transform
Piotr Indyk, Michael Kapralov, and Eric Price · 2014
Cited alongside, same era.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Cited alongside, same era.
Time-frequency signal analysis and processing: a comprehensive reference
Boualem Boashash · 2015
Cited alongside, same era.
Constructing linear-sized spectral sparsification in almost-linear time
Yin Tat Lee and He Sun · 2015
Cited alongside, same era.
The threshold for super-resolution via extremal functions
Ankur Moitra · 2015
Cited alongside, same era.
Michael Kapralov, Ameya Velingker, and Amir Zandieh · 2019
Later among the works it cites.
(nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless
Vasileios Nakos, Zhao Song, and Zhengyu Wang · 2019
Later among the works it cites.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2021
Later among the works it cites.
Sparsification for sums of exponentials and its algorithmic applications
Jerry Li, Allen Liu, and Ankur Moitra · 2021
Later among the works it cites.
Learning with invariances in random features and kernel models
Song Mei, Theodor Misiakiewicz, and Andrea Montanari · 2021
Later among the works it cites.
A robust multi-dimensional sparse fourier transform in the continuous setting
Yaonan Jin, Daogao Liu, and Zhao Song · 2023
Closest in time.
Quartic samples suffice for fourier interpolation
Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang · 2023
Closest in time.