Fast and Efficient Sparse 2D Discrete Fourier Transform using Sparse-Graph Codes

I. J. Good, “The interaction algorithm and practical Fourier analysis,” Journal of the Royal Statistical Society. Series B (Methodological) , 1958. [Online]. Available: \url

1958

Earlier work this paper cites.

L. H. Thomas, Using a computer to solve problems in physics . Applications of Digital Computers, 1963. [Online]. Available: \url

1963

Earlier work this paper cites.

A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss, “Near-optimal sparse fourier representations via sampling,” in the thiry-fourth annual ACM symposium . New York, New York, USA: ACM, May 2002, pp. 152–161. [Online]. Available: \url

2002

Earlier work this paper cites.

A. C. Gilbert, S. Muthukrishnan, and M. Strauss, “Improved Time Bounds for Near-Optimal Sparse Fourier Representations,” Optics & Photonics 2005 , vol. 5914, pp. 1–15, Jul. 2005. [Online]. Available: \url

2005

Earlier work this paper cites.

D. L. Donoho, “Compressed sensing,” Information Theory, IEEE Transactions on , vol. 52, no. 4, pp. 1289–1306, Apr. 2006. [Online]. Available: \url

2006

Earlier work this paper cites.

E. J. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,” Information Theory, IEEE Transactions on , vol. 52, no. 2, pp. 489–509, 2006. [Online]. Available: \url

2006

Earlier work this paper cites.

M. Lustig, D. Donoho, and J. M. Pauly, “Sparse MRI: The application of compressed sensing for rapid MR imaging,” Magnetic Resonance in Medicine , vol. 58, no. 6, pp. 1182–1195, 2007. [Online]. Available: \url

2007

Cited alongside, same era.

A. C. Gilbert, M. J. Strauss, and J. A. Tropp, “A Tutorial on Fast Fourier Sampling,” IEEE Signal Processing Magazine , vol. 25, no. 2, pp. 57–66, Mar. 2008. [Online]. Available: \url

2008

Cited alongside, same era.

R. E. Blahut, Fast Algorithms for Signal Processing . Cambridge University Press, Jun. 2010. [Online]. Available: \url

2010

Cited alongside, same era.

H. Hassanieh, P. Indyk, D. Katabi, and E. Price, “Nearly optimal sparse fourier transform,” in the 44th symposium . New York, New York, USA: ACM, May 2012, pp. 563–578. [Online]. Available: \url

2012

Cited alongside, same era.

B. Ghazi, H. Hassanieh, P. Indyk, D. Katabi, E. Price, and L. Shi, “Sample-optimal average-case sparse Fourier Transform in two dimensions,” in 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton) . IEEE, 2013, pp. 1258–1265. [Online]. Available: \url

2013

Later among the works it cites.

A. C. Gilbert, P. Indyk, M. Iwen, and L. Schmidt, “Recent Developments in the Sparse Fourier Transform: A compressed Fourier transform for big data,” IEEE Signal Processing Magazine , vol. 31, no. 5, pp. 91–100, Sep. 2014. [Online]. Available: \url

2014

Later among the works it cites.

P. Indyk, M. Kapralov, and E. Price, “(Nearly) sample-optimal sparse Fourier transform,” in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM, 2014, pp. 480–499. [Online]. Available: \url

2014

Later among the works it cites.

P. Indyk and M. Kapralov, “Sample-Optimal Fourier Sampling in Any Constant Dimension,” 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) , pp. 514–523, 2014. [Online]. Available: \url