Simple and practical algorithm for sparse Fourier transform. (English) Zbl 1458.94097
Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1183-1194 (2012).
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 42A38 | Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
Software:
AAFFTReferences:
| [1] | Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993 |
| [2] | {AGS03} A. Akavia, S. Goldwasser, and S. Safra. Proving hard-core predicates using list decoding. FOCS, pages 146–, 2003. |
| [3] | {Aka10} A. Akavia. Deterministic sparse fourier approximation via fooling arithmetic progressions. COLT, pages 381-393, 2010. |
| [4] | A. Chandrakasan , V. Gutnik , T. Xanthopoulos, Data driven signal processing: an approach for energy efficient computing, Proceedings of the 1996 international symposium on Low power electronics and design, p.347-352, August 12-14, 1996, Monterey, California, USA |
| [5] | {CM06} G. Cormode and S. Muthukrishnan. Combinatorial algorithms for compressed sensing. SIROCCO, 2006. · Zbl 1222.94016 |
| [6] | E. J. Candes , J. Romberg , T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, v.52 n.2, p.489-509, February 2006 [doi>10.1109/TIT.2005.862083] · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083 |
| [7] | D. L. Donoho, Compressed sensing, IEEE Transactions on Information Theory, v.52 n.4, p.1289-1306, April 2006 [doi>10.1109/TIT.2006.871582] · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [8] | {DRZ07} I. Daubechies, O. Runborg, and J. Zou. A sparse spectral method for homogenization multiscale problems. Multiscale Model. Sim., 6(3):711-740, 2007. · Zbl 1152.65099 |
| [9] | {FJ} M. Frigo and S. G. Johnson. Fftw3.2.3. http://www.fftw.org/. |
| [10] | A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509933] · Zbl 1192.94078 |
| [11] | {GI10} A. Gilbert and P. Indyk. Sparse recovery using sparse matrices. Proceedings of IEEE, 2010. |
| [12] | {GMS05} A. Gilbert, M. Muthukrishnan, and M. Strauss. Improved time bounds for near-optimal space fourier representations. SPIE Conference, Wavelets, 2005. |
| [13] | {GST08} A. C. Gilbert, M. J. Strauss, and J. A. Tropp. A tutorial on fast fourier sampling. Signal Processing Magazine, 2008. |
| [14] | {IGS07} M. A. Iwen, A. Gilbert, and M. Strauss. Empirical evaluation of a sub-linear time sparse dft algorithm. Communications in Mathematical Sciences, 5, 2007. · Zbl 1134.65093 |
| [15] | {Iwe08} M. Iwen. AAFFT (Ann Arbor Fast Fourier Transform). http://sourceforge.net/projects/aafftannarborfa/2008. |
| [16] | M. A. Iwen, Combinatorial Sublinear-Time Fourier Algorithms, Foundations of Computational Mathematics, v.10 n.3, p.303-338, June 2010 [doi>10.1007/s10208-009-9057-1] · Zbl 1230.65145 · doi:10.1007/s10208-009-9057-1 |
| [17] | {Iwe10b} M. A. Iwen. Improved approximation guarantees for sublinear-time fourier algorithms. Arxiv preprint arXiv:1010.0014, 2010. · Zbl 1260.65115 |
| [18] | {KKL88} J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. FOCS, 1988. |
| [19] | Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.455-464, May 05-08, 1991, New Orleans, Louisiana, USA [doi>10.1145/103418.103466] · Zbl 0799.68159 |
| [20] | Nathan Linial , Yishay Mansour , Noam Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM (JACM), v.40 n.3, p.607-620, July 1993 [doi>10.1145/174130.174138] · Zbl 0781.94006 |
| [21] | Mengda Lin , A. P. Vinod , Chong Meng See, A New Flexible Filter Bank for Low Complexity Spectrum Sensing in Cognitive Radios, Journal of Signal Processing Systems, v.62 n.2, p.205-215, February 2011 [doi>10.1007/s11265-008-0329-9] · doi:10.1007/s11265-008-0329-9 |
| [22] | {Man92} Y. Mansour. Randomized interpolation and approximation of sparse polynomials. ICALP, 1992. · Zbl 1427.65013 |
| [23] | Abdullah Mueen , Suman Nath , Jie Liu, Fast approximate correlation for massive time-series data, Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, June 06-10, 2010, Indianapolis, Indiana, USA [doi>10.1145/1807167.1807188] |
| [24] | Ryan O’Donnell, Some topics in analysis of boolean functions, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374458] · Zbl 1231.94096 |
| [25] | Alan V. Oppenheim , Ronald W. Schafer , John R. Buck, Discrete-time signal processing (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999 |
| [26] | {PS10} E. Porat and M. Strauss. Sublinear time, measurement-optimal, sparse recovery for all. Manuscript, 2010. |
| [27] | {Smi11} Julius O. Smith. Spectral Audio Signal Processing, October 2008 Draft. http://ccrma.stanford.edu/ jos/sasp/, accessed 2011-07- |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
