{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:09:46Z","timestamp":1771697386865,"version":"3.50.1"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,1,5]],"date-time":"2010-01-05T00:00:00Z","timestamp":1262649600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2010,6]]},"DOI":"10.1007\/s10208-009-9057-1","type":"journal-article","created":{"date-parts":[[2010,1,4]],"date-time":"2010-01-04T19:52:06Z","timestamp":1262634726000},"page":"303-338","source":"Crossref","is-referenced-by-count":90,"title":["Combinatorial Sublinear-Time Fourier Algorithms"],"prefix":"10.1007","volume":"10","author":[{"given":"M. A.","family":"Iwen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"9057_CR1","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1137\/0917059","volume":"17","author":"C. Anderson","year":"1996","unstructured":"C. Anderson, M.D. Dahleh, Rapid computation of the discrete Fourier transform, SIAM J. Sci. Comput. 17, 913\u2013919 (1996).","journal-title":"SIAM J. Sci. Comput."},{"key":"9057_CR2","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1109\/TAU.1970.1162132","volume":"18","author":"L.I. Bluestein","year":"1970","unstructured":"L.I. Bluestein, A linear filtering approach to the computation of discrete Fourier transform, IEEE Trans. Audio Electroacoust. 18, 451\u2013455 (1970).","journal-title":"IEEE Trans. Audio Electroacoust."},{"key":"9057_CR3","volume-title":"Chebyshev and Fourier Spectral Methods","author":"J.P. Boyd","year":"2001","unstructured":"J.P. Boyd, Chebyshev and Fourier Spectral Methods (Dover, New York, 2001)."},{"key":"9057_CR4","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E. Candes","year":"2006","unstructured":"E. Candes, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory 52, 489\u2013509 (2006).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"8","key":"9057_CR5","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"E. Candes","year":"2006","unstructured":"E. Candes, J. Romberg, T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006).","journal-title":"Commun. Pure Appl. Math."},{"key":"9057_CR6","unstructured":"B. Chazelle, The Discrepancy Method: Randomness and Complexity (Brooks\/Cole Publishing Company, 1992)."},{"issue":"1","key":"9057_CR7","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1090\/S0894-0347-08-00610-3","volume":"22","author":"A. Cohen","year":"2008","unstructured":"A. Cohen, W. Dahmen, R. DeVore, Compressed sensing and best k-term approximation, J. Am. Math. Soc. 22(1), 211\u2013231 (2008).","journal-title":"J. Am. Math. Soc."},{"key":"9057_CR8","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J. Cooley","year":"1965","unstructured":"J. Cooley, J. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comput. 19, 297\u2013301 (1965).","journal-title":"Math. Comput."},{"key":"9057_CR9","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms (MIT Press\/McGraw\u2013Hill, Cambridge\/New York, 1990)."},{"key":"9057_CR10","unstructured":"G. Cormode, S. Muthukrishnan, Combinatorial algorithms for compressed sensing. Technical Report DIMACS TR 2005-40 (2005)."},{"key":"9057_CR11","doi-asserted-by":"crossref","unstructured":"G. Cormode, S. Muthukrishnan, Combinatorial algorithms for compressed sensing, in Conference on Information Sciences and Systems, March 2006.","DOI":"10.1109\/CISS.2006.286461"},{"key":"9057_CR12","doi-asserted-by":"crossref","unstructured":"I. Daubechies, O. Runborg, J. Zou, A sparse spectral method for homogenization multiscale problems, Multiscale Model. Simul. (2007).","DOI":"10.1137\/060676258"},{"key":"9057_CR13","doi-asserted-by":"crossref","unstructured":"R.A. DeVore, Deterministic constructions of compressed sensing matrices, J. Complex. 23 (August 2007).","DOI":"10.1016\/j.jco.2007.04.002"},{"key":"9057_CR14","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D. Donoho","year":"2006","unstructured":"D. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52, 1289\u20131306 (2006).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9057_CR15","doi-asserted-by":"crossref","unstructured":"D.L. Donoho, J. Tanner, Thresholds for the recovery of sparse solutions via \u2113 1 minimization, in 40th Annual Conference on Information Sciences and Systems (CISS), 2006.","DOI":"10.1109\/CISS.2006.286462"},{"key":"9057_CR16","volume-title":"Combinatorial Group Testing and Its Applications","author":"D.Z. Du","year":"1993","unstructured":"D.Z. Du, F.K. Hwang, Combinatorial Group Testing and Its Applications (World Scientific, Singapore, 1993)."},{"key":"9057_CR17","doi-asserted-by":"crossref","first-page":"1368","DOI":"10.1137\/0914081","volume":"14","author":"A. Dutt","year":"1993","unstructured":"A. Dutt, V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput. 14, 1368\u20131383 (1993).","journal-title":"SIAM J. Sci. Comput."},{"key":"9057_CR18","doi-asserted-by":"crossref","unstructured":"D. Eppstein, M.T. Goodrich, D.S. Hirschberg, Improved combinatorial group testing algorithms for real-world problem sizes. http:\/\/arxiv.org\/abs\/cs.DS\/0505048 , May 2005.","DOI":"10.1007\/11534273_9"},{"key":"9057_CR19","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1109\/TSP.2002.807005","volume":"51","author":"J.A. Fessler","year":"2003","unstructured":"J.A. Fessler, B.P. Sutton, Nonuniform fast Fourier transforms using min-max interpolation, IEEE Trans. Signal Proc. 51, 560\u2013574 (2003).","journal-title":"IEEE Trans. Signal Proc."},{"key":"9057_CR20","unstructured":"G.B. Folland, Fourier Analysis and Its Applications (Brooks\/Cole Publishing Company, 1992)."},{"issue":"2","key":"9057_CR21","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1109\/JPROC.2004.840301","volume":"93","author":"M. Frigo","year":"2005","unstructured":"M. Frigo, S. Johnson, The design and implementation of fftw3, Proc. IEEE 93(2), 216\u2013231 (2005).","journal-title":"Proc. IEEE"},{"key":"9057_CR22","unstructured":"A. Gilbert, M. Strauss, Group testing in statistical signal recovery. Preprint (2006)."},{"key":"9057_CR23","doi-asserted-by":"crossref","unstructured":"A. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-optimal sparse Fourier estimation via sampling, in ACM STOC, pp.\u00a0152\u2013161, 2002.","DOI":"10.1145\/509931.509933"},{"key":"9057_CR24","doi-asserted-by":"crossref","unstructured":"A. Gilbert, S. Muthukrishnan, M. Strauss, Improved time bounds for near-optimal sparse Fourier representations, in Proceedings of SPIE Wavelets XI, 2005.","DOI":"10.1117\/12.615931"},{"key":"9057_CR25","unstructured":"A.C. Gilbert, M.J. Strauss, J.A. Tropp, R. Vershynin, Algorithmic linear dimension reduction in the l 1 norm for sparse vectors. Preprint (2006)."},{"key":"9057_CR26","unstructured":"P. Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, in SODA \u201902: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 697\u2013704, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics."},{"key":"9057_CR27","unstructured":"P. Indyk, Explicit constructions for compressed sensing of sparse signals, in Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908), 2008."},{"key":"9057_CR28","unstructured":"M.A. Iwen, A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods, in Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908), 2008."},{"key":"9057_CR29","doi-asserted-by":"crossref","unstructured":"M.A. Iwen, C.V. Spencer, Improved bounds for a deterministic sublinear-time sparse Fourier algorithm, in Conference on Information Sciences and Systems (CISS), 2008.","DOI":"10.1109\/CISS.2008.4558570"},{"key":"9057_CR30","doi-asserted-by":"crossref","unstructured":"M.A. Iwen, A.C. Gilbert, M.J. Strauss, Empirical evaluation of a sub-linear time sparse DFT algorithm, Commun. Math. Sci. 5(4) (2007).","DOI":"10.4310\/CMS.2007.v5.n4.a13"},{"key":"9057_CR31","doi-asserted-by":"crossref","unstructured":"L.Y.E. Kaltofen, Improved sparse multivariate polynomial interpolation algorithms, in International Symposium on Symbolic and Algebraic Computation, 1988.","DOI":"10.1007\/3-540-51084-2_44"},{"key":"9057_CR32","unstructured":"D. Kincaid, W. Cheney, Numerical Analysis: Mathematics of Scientific Computing (China Machine Press, 2003)."},{"key":"9057_CR33","doi-asserted-by":"crossref","unstructured":"S. Kirolos, J. Laska, M. Wakin, M. Duarte, D. Baron, T. Ragheb, Y. Massoud, R. Baraniuk, Analog-to-information conversion via random demodulation, in Proc. IEEE Dallas Circuits and Systems Conference, 2006.","DOI":"10.1109\/DCAS.2006.321036"},{"issue":"6","key":"9057_CR34","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1007\/s10208-007-9005-x","volume":"8","author":"S. Kunis","year":"2008","unstructured":"S. Kunis, H. Rauhut, Random sampling of sparse trigonometric polynomials II\u2014orthogonal matching pursuit versus basis pursuit. Found. Comput. Math. 8(6), 737\u2013763 (2008).","journal-title":"Found. Comput. Math."},{"key":"9057_CR35","doi-asserted-by":"crossref","unstructured":"J. Laska, S. Kirolos, Y. Massoud, R. Baraniuk, A. Gilbert, M. Iwen, M. Strauss, Random sampling for analog-to-information conversion of wideband signals, in Proc. IEEE Dallas Circuits and Systems Conference, 2006.","DOI":"10.1109\/DCAS.2006.321048"},{"key":"9057_CR36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcp.2004.12.004","volume":"206","author":"J.-Y. Lee","year":"2005","unstructured":"J.-Y. Lee, L. Greengard, The type 3 nonuniform FFT and its applications, J. Comput. Phys. 206, 1\u20135 (2005).","journal-title":"J. Comput. Phys."},{"issue":"6","key":"9057_CR37","doi-asserted-by":"crossref","first-page":"1182","DOI":"10.1002\/mrm.21391","volume":"58","author":"M. Lustig","year":"2007","unstructured":"M. Lustig, D. Donoho, J. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging, Magn. Reson. Med. 58(6), 1182\u20131195 (2007).","journal-title":"Magn. Reson. Med."},{"key":"9057_CR38","unstructured":"R. Maleh, A.C. Gilbert, M.J. Strauss, Signal recovery from partial information via orthogonal matching pursuit, in IEEE Int. Conf. on Image Processing, 2007."},{"key":"9057_CR39","unstructured":"S. Mallet, A Wavelet Tour of Signal Processing (China Machine Press, 2003)."},{"key":"9057_CR40","doi-asserted-by":"crossref","unstructured":"Y. Mansour, Learning boolean functions via the Fourier transform, Theor. Adv. Neural Comput. Learn. 391\u2013424 (1994).","DOI":"10.1007\/978-1-4615-2696-4_11"},{"key":"9057_CR41","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1137\/S0097539792239291","volume":"24","author":"Y. Mansour","year":"1995","unstructured":"Y. Mansour, Randomized approximation and interpolation of sparse polynomials, SIAM J. Comput. 24, 2 (1995).","journal-title":"SIAM J. Comput."},{"key":"9057_CR42","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"R. Motwani, P. Raghavan, Randomized Algorithms (Cambridge University Press, Cambridge, 1995)."},{"key":"9057_CR43","doi-asserted-by":"crossref","unstructured":"S. Muthukrishnan, Data streams: algorithms and applications, Found. Trends Theor. Comput. Sci. 1 (2005).","DOI":"10.1561\/0400000002"},{"key":"9057_CR44","unstructured":"S. Muthukrishnan, Some algorithmic problems and results in compressed sensing, in Allerton Conference, 2006."},{"key":"9057_CR45","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10208-008-9031-3","volume":"9","author":"D. Needell","year":"2009","unstructured":"D. Needell, R. Vershynin, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Found. Comput. Math. 9, 317\u2013334 (2009).","journal-title":"Found. Comput. Math."},{"key":"9057_CR46","volume-title":"An Introduction to the Theory of Numbers","author":"I. Niven","year":"1991","unstructured":"I. Niven, H.S. Zuckerman, H.L. Montgomery, An Introduction to the Theory of Numbers (Wiley, New York, 1991)."},{"issue":"2","key":"9057_CR47","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1109\/TAU.1969.1162034","volume":"AU-17","author":"L. Rabiner","year":"1969","unstructured":"L. Rabiner, R. Schafer, C. Rader, The chirp z-transform algorithm, IEEE Trans. Audio Electroacoust. AU-17(2), 86\u201392 (1969).","journal-title":"IEEE Trans. Audio Electroacoust."},{"key":"9057_CR48","doi-asserted-by":"crossref","unstructured":"M. Rudelson, R. Vershynin, Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements, in 40th Annual Conference on Information Sciences and Systems (CISS), 2006.","DOI":"10.1109\/CISS.2006.286463"},{"key":"9057_CR49","unstructured":"The Prime Pages, http:\/\/primes.utm.edu\/ ."},{"issue":"12","key":"9057_CR50","doi-asserted-by":"crossref","first-page":"4655","DOI":"10.1109\/TIT.2007.909108","volume":"53","author":"J. Tropp","year":"2007","unstructured":"J. Tropp, A. Gilbert, Signal recovery from partial information via orthogonal matching pursuit, IEEE Trans. Inf. Theory 53(12), 4655\u20134666 (2007).","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-009-9057-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-009-9057-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-009-9057-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T11:05:10Z","timestamp":1559127910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-009-9057-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,5]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["9057"],"URL":"https:\/\/doi.org\/10.1007\/s10208-009-9057-1","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,5]]}}}