Fetching the paper…
Reading the bibliography…
The problem of approximately computing the $k$ dominant Fourier coefficients of a vector $X$ quickly, and using few samples in time domain, is known as the Sparse Fourier Transform (sparse FFT) problem.
O. Goldreich and L. Levin, “A hard-corepredicate for allone-way functions,” ACM Symp. Theory Comp. (STOC) , pp. 25–32, 1989
1989
Earlier work this paper cites.
E. Kushilevitz and Y. Mansour, “Learning decision trees using the Fourier spectrum,” ACM Symp. Theory Comp. (STOC) , 1991
1991
Earlier work this paper cites.
Y. Mansour, “Randomized interpolation and approximation of sparse polynomials,” Int. Coll. Auto., Lang., and Prog. (ICALP) , 1992
1992
Earlier work this paper cites.
T. Hagerup, K. Mehlhorn, and J. I. Munro, “Maintaining discrete probability distributions optimally,” in Int. Coll.. Auto., Lang., and Prog. (ICALP) , 1993, pp. 253–264
1993
Earlier work this paper cites.
A. Gilbert, S. Guha, P. Indyk, M. Muthukrishnan, and M. Strauss, “Near-optimal sparse Fourier representations via sampling,” ACM Symp. Theory Comp. (STOC) , 2002
2002
Earlier work this paper cites.
A. Akavia, S. Goldwasser, and S. Safra, “Proving hard-core predicates using list decoding,” IEEE Symp. Found. Comp. Sci. (FOCS) , vol. 44, pp. 146–159, 2003
2003
Earlier work this paper cites.
A. Gilbert, M. Muthukrishnan, and M. Strauss, “Improved time bounds for near-optimal space Fourier representations,” SPIE Conference, Wavelets , 2005
2005
Earlier work this paper cites.
E. Candes and T. Tao, “Near-optimal signal recovery from random projections: Universal encoding strategies,” IEEE Trans. Inf. Theory , vol. 52, no. 12, pp. 5406–5425, 2006
2006
Earlier work this paper cites.
T. M. Cover and J. A. Thomas, Elements of Information Theory . John Wiley & Sons, Inc., 2006
2006
Earlier work this paper cites.
A. Gilbert, M. J. Strauss, and J. A. Tropp, “A tutorial on fast Fourier sampling,” IEEE Sig. Proc. Mag. , vol. 25, no. 2, pp. 57–66, 2008
2008
Earlier work this paper cites.
2008
Earlier work this paper cites.
V. Cevher, P. Indyk, C. Hegde, and R. Baraniuk, “Recovery of clustered sparse signals from compressive measurements,” in Int. Conf. Samp. Theory Apps. (SAMPTA) , 2009
2009
Earlier work this paper cites.
A. Akavia, “Deterministic sparse Fourier approximation via fooling arithmetic progressions,” Conf. Learn. Theory (COLT) , pp. 381–393, 2010
2010
Earlier work this paper cites.
F. R. Bach, “Structured sparsity-inducing norms through submodular functions,” in Adv. Neur. Inf. Proc. Sys. (NIPS) , 2010, pp. 118–126
2010
Cited alongside, same era.
R. Baraniuk, V. Cevher, M. Duarte, and C. Hegde, “Model-based compressive sensing,” IEEE Trans. Inf. Theory , vol. 56, no. 4, pp. 1982–2001, April 2010
2010
Cited alongside, same era.
R. Baraniuk, V. Cevher, and M. B. Wakin, “Low-dimensional models for dimensionality reduction and signal recovery: A geometric perspective,” Proc. IEEE , vol. 98, no. 6, pp. 959–971, 2010
2010
Cited alongside, same era.
K. Do Ba, P. Indyk, E. Price, and D. P. Woodruff, “Lower bounds for sparse recovery,” ACM-SIAM Symp. Disc. Alg. (SODA) , 2010
2010
Cited alongside, same era.
M. A. Iwen, “Combinatorial sublinear-time Fourier algorithms,” Found. Comp. Math. , vol. 10, pp. 303–338, 2010
2010
S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing . Springer New York, 2013
2013
Later among the works it cites.
B. Ghazi, H. Hassanieh, P. Indyk, D. Katabi, E. Price, and L. Shi, “Sample-optimal average-case sparse fourier transform in two dimensions,” in Allerton Conf. Comm., Control, and Comp. , 2013
2013
Later among the works it cites.
S. Heider, S. Kunis, D. Potts, and M. Veit, “A sparse Prony FFT,” Samp. Theory Apps. (SAMPTA) , 2013
2013
Later among the works it cites.
P. Indyk and I. Razenshteyn, “On model-based RIP-1 matrices,” in Int. Coll. Auto., Lang., and Prog. (ICALP) , 2013
2013
Later among the works it cites.
B. Bah, L. Baldassarre, and V. Cevher, “Model-based sketching and recovery with expanders,” in ACM-SIAM Symp. Disc. Alg. (SODA) , 2014
2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
E. Price and D. P. Woodruff, “ ( 1 + ϵ ) (1+\epsilon) -approximate sparse recovery,” IEEE Symp. Found. Comp. Sci. (FOCS) , 2011
2011
Cited alongside, same era.
P. Boufounos, V. Cevher, A. C. Gilbert, Y. Li, and M. J. Strauss, “What’s the frequency, Kenneth?: Sublinear Fourier sampling off the grid,” RANDOM/APPROX , 2012
2012
Cited alongside, same era.
H. Hassanieh, F. Adib, D. Katabi, and P. Indyk, “Faster GPS via the sparse Fourier transform,” MOBICOM , 2012
2012
Cited alongside, same era.
H. Hassanieh, P. Indyk, D. Katabi, and E. Price, “Near-optimal algorithm for sparse Fourier transform,” ACM Symp. Theory Comp. (STOC) , 2012
2012
Cited alongside, same era.
H. Hassanieh, P. Indyk, D. Katabi, and E. Price, “Simple and practical algorithm for sparse Fourier transform,” ACM-SIAM Symp. Disc. Alg. (SODA) , 2012
2012
Cited alongside, same era.
H. Hassanieh, P. Indyk, D. Katabi, and E. Price, “Nearly optimal sparse Fourier transform,” in Proc. ACM Symp. Theory Comp. (STOC) . ACM, 2012, pp. 563–578
2012
Cited alongside, same era.
2012
Cited alongside, same era.
A. Gilbert, P. Indyk, M. Iwen, and L. Schmidt, “Recent developments in the sparse Fourier transform: A compressed Fourier transform for big data,” IEEE Sig. Proc. Mag. , vol. 31, no. 5, pp. 91–100, 2014
2014
Later among the works it cites.
P. Indyk and M. Kapralov, “Sample-optimal Fourier sampling in any fixed dimension,” IEEE Symp. Found. Comp. Sci. (FOCS) , 2014
2014
Later among the works it cites.
P. Indyk, M. Kapralov, and E. Price, “(Nearly) sample-optimal sparse Fourier transform,” ACM-SIAM Symp. Disc. Alg. (SODA) , 2014
2014
Later among the works it cites.
M. El Halabi and V. Cevher, “A totally unimodular view of structured sparsity,” in Int. Conf. Art. Intel. Stats. (AISTATS) , May 2015
2015
Later among the works it cites.
E. Price and Z. Song, “A robust sparse Fourier transform in the continuous setting,” IEEE Symp. Found. Comp. Sci. (FOCS) , 2015
2015
Later among the works it cites.
L. Baldassarre, N. Bhan, V. Cevher, A. Kyrillidis, and S. Satpathi, “Group-sparse model selection: Hardness and relaxations,” IEEE Trans. Inf. Theory , vol. 62, no. 11, pp. 6508–6534, November 2016
2016
Later among the works it cites.
M. Kapralov, “Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time,” ACM Symp. Theory Comp. (STOC) , 2016
2016
Later among the works it cites.