Fetching the paper…
Reading the bibliography…
We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier $k$-sparse vector $\widehat{x} \in \mathbb{C}^{n^d}$ from observing its time domain representation $x$.
Decoding of bose-chaudhuri-hocquenghem codes and prony’s method for curve fitting (corresp.)
J Wolf · 1967
Earlier work this paper cites.
A fast algorithm for particle simulations
Leslie Greengard and Vladimir Rokhlin · 1987
Earlier work this paper cites.
A deterministic algorithm for sparse multivariate polynomial interpolation
Michael Ben-Or and Prasoon Tiwari · 1988
Earlier work this paper cites.
A hard-core predicate for all one-way functions
Oded Goldreich and Leonid A Levin · 1989
Earlier work this paper cites.
Learning decision trees using the fourier spectrum
Eyal Kushilevitz and Yishay Mansour · 1993
Earlier work this paper cites.
Constant depth circuits, Fourier transform, and learnability
N. Linial, Y. Mansour, and N. Nisan · 1993
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich · 1994
Earlier work this paper cites.
Learning Boolean Functions via the Fourier Transform
Y. Mansour · 1994
Earlier work this paper cites.
Randomized interpolation and approximation of sparse polynomials
Yishay Mansour · 1995
Earlier work this paper cites.
The nonuniform discrete fourier transform and its applications in filter design. i. 1-d
Sonali Bagchi and Sanjit K Mitra · 1996
Earlier work this paper cites.
A fast Fourier transform compiler
Matteo Frigo · 1999
Earlier work this paper cites.
Fast fourier transforms for nonequispaced data: A tutorial
Daniel Potts, Gabriele Steidl, and Manfred Tasche · 2001
Earlier work this paper cites.
Near-optimal sparse Fourier representations via sampling
Anna C Gilbert, Sudipto Guha, Piotr Indyk, Shanmugavelayutham Muthukrishnan, and Martin Strauss · 2002
Earlier work this paper cites.
Proving hard-core predicates using list decoding
A Akavia, S Goldwasser, and S Safra · 2003
Earlier work this paper cites.
Nonuniform fast fourier transforms using min-max interpolation
Jeffrey A Fessler and Bradley P Sutton · 2003
Earlier work this paper cites.
Accelerating the nonuniform fast fourier transform
Leslie Greengard and June-Yub Lee · 2004
Earlier work this paper cites.
Improved time bounds for near-optimal sparse Fourier representations
Anna C Gilbert, Shan Muthukrishnan, and Martin Strauss · 2005
Earlier work this paper cites.
A new algorithm for optimal 2-constraint satisfaction and its implications
Ryan Williams · 2005
Earlier work this paper cites.
Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information
E. Candes, J. Romberg, and T. Tao · 2006
Earlier work this paper cites.
Near-optimal signal recovery from random projections: Universal encoding strategies?
Emmanuel J Candes and Terence Tao · 2006
Earlier work this paper cites.
Compressed sensing
D. Donoho · 2006
Cited alongside, same era.
Empirical Evaluation of a Sub-Linear Time Sparse DFT Algorithm
M. A. Iwen, A. Gilbert, and M. Strauss · 2007
Cited alongside, same era.
Compressed sensing MRI
Michael Lustig, David L Donoho, Juan M Santos, and John M Pauly · 2008
Cited alongside, same era.
Deterministic sparse fourier approximation via fooling arithmetic progressions
Adi Akavia · 2010
Cited alongside, same era.
Combinatorial sublinear-time Fourier algorithms
Mark A Iwen · 2010
Cited alongside, same era.
Accelerated nmr spectroscopy by using compressed sensing
Krzysztof Kazimierczuk and Vladislav YU · 2011
Cited alongside, same era.
Exploring connections between sparse fourier transform computation and decoding of product codes
Nagaraj Thenkarai Janakiraman, Santosh K. Emmadi, Krishna R. Narayanan, and Kannan Ramchandran · 2015
Later among the works it cites.
Super-resolution, extremal functions and the condition number of vandermonde matrices
Ankur Moitra · 2015
Later among the works it cites.
Fast and efficient sparse 2d discrete fourier transform using sparse-graph codes
Frank Ong, Sameer Pawar, and Kannan Ramchandran · 2015
Later among the works it cites.
A robust sparse Fourier transform in the continuous setting
Eric Price and Zhao Song · 2015
Later among the works it cites.
Fourier-sparse interpolation without a frequency gap
Xue Chen, Daniel M Kane, Eric Price, and Zhao Song · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Petros Boufounos, Volkan Cevher, Anna C Gilbert, Yi Li, and Martin J Strauss · 2012
Cited alongside, same era.
The nonuniform discrete Fourier transform and its applications in signal processing
Sonali Bagchi and Sanjit K Mitra · 2012
Cited alongside, same era.
Nearly optimal sparse Fourier transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price · 2012
Cited alongside, same era.
Simple and practical algorithm for sparse Fourier transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price · 2012
Cited alongside, same era.
Restricted isometry of Fourier matrices and list decodability of random linear codes
Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker · 2013
Cited alongside, same era.
A Mathematical Introduction to Compressive Sensing
Simon Foucart and Holger Rauhut · 2013
Cited alongside, same era.
Ishay Haviv and Oded Regev · 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.
Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform
Mahdi Cheraghchi and Piotr Indyk · 2017
Later among the works it cites.
An adaptive sublinear-time block sparse Fourier transform
Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh · 2017
Later among the works it cites.
The restricted isometry property of subsampled fourier matrices
Ishay Haviv and Oded Regev · 2017
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.
A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees
Sami Merhi, Ruochuan Zhang, Mark A Iwen, and Andrew Christlieb · 2017
Later among the works it cites.
More consequences of falsifying SETH and the orthogonal vectors conjecture
Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof · 2018
Later among the works it cites.
Efficiently Learning Fourier Sparse Set Functions
Andisheh Amrollahi, Amir Zandieh, Michael Kapralov, and Andreas Krause · 2019
Later among the works it cites.
Completeness for first-order properties on sparse structures with algorithmic applications
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams · 2019
Later among the works it cites.
Dimension-independent sparse Fourier transform
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 fast and robust paradigm for fourier compressed sensing based on coded sampling
Frank Ong, Reinhard Heckel, and Kannan Ramchandran · 2019
Later among the works it cites.
Fast generalized dfts for all finite groups
Chris Umans · 2019
Later among the works it cites.
A robust multi-dimensional sparse Fourier transform in the continuous setting
Yaonan Jin, Daogao Liu, and Zhao Song · 2020
Later among the works it cites.