{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:39:52Z","timestamp":1772138392753,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T00:00:00Z","timestamp":1533772800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T00:00:00Z","timestamp":1533772800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["GRK 2088"],"award-info":[{"award-number":["GRK 2088"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1416752"],"award-info":[{"award-number":["DMS-1416752"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Adv Comput Math"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s10444-018-9626-4","type":"journal-article","created":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T05:05:50Z","timestamp":1533791150000},"page":"519-561","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["A deterministic sparse FFT for functions with structured Fourier sparsity"],"prefix":"10.1007","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5923-4210","authenticated-orcid":false,"given":"Sina","family":"Bittens","sequence":"first","affiliation":[]},{"given":"Ruochuan","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Mark A.","family":"Iwen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"9626_CR1","unstructured":"Akavia, A.: Deterministic sparse Fourier approximation via fooling arithmetic progressions. In: Proceedings of 23rd COLT, pp 381\u2013393 (2010)"},{"key":"9626_CR2","first-page":"146","volume":"44","author":"A Akavia","year":"2003","unstructured":"Akavia, A., Goldwasser, S., Safra, S.: Proving hard-core predicates using list decoding. FOCS 44, 146\u2013159 (2003)","journal-title":"FOCS"},{"issue":"1","key":"9626_CR3","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1137\/110835864","volume":"33","author":"J Bailey","year":"2012","unstructured":"Bailey, J., Iwen, M.A., Spencer, C.V.: On the design of deterministic matrices for fast recovery of Fourier compressible functions. SIAM J. Matrix Anal. Appl. 33 (1), 263\u2013289 (2012)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9626_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1186\/s13104-016-2361-3","volume":"10","author":"S Bittens","year":"2017","unstructured":"Bittens, S.: Sparse FFT for functions with short frequency support. Dolomites Res Notes Approx. 10, 43\u201355 (2017)","journal-title":"Dolomites Res Notes Approx."},{"issue":"4","key":"9626_CR5","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1109\/TAU.1970.1162132","volume":"18","author":"LI Bluestein","year":"1970","unstructured":"Bluestein, L.I.: A linear filtering approach to the computation of discrete Fourier transform. IEEE Trans. Audio Electroacoust. 18(4), 451\u2013455 (1970)","journal-title":"IEEE Trans. Audio Electroacoust."},{"key":"9626_CR6","doi-asserted-by":"crossref","unstructured":"Boufounos, P., Cevher, V., Gilbert, A.C., Li, Y., Strauss, M.J.: What\u2019s the frequency, Kenneth?: Sublinear Fourier sampling off the grid RANDOM\/APPROX (2012)","DOI":"10.1007\/978-3-642-32512-0_6"},{"issue":"1","key":"9626_CR7","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1215\/00127094-1384809","volume":"159","author":"J Bourgain","year":"2011","unstructured":"Bourgain, J., Dilworth, S., Ford, K., Konyagin, S., Kutzarova, D., et al.: Explicit constructions of RIP matrices and related problems. Duke Math. J. 159(1), 145\u2013185 (2011)","journal-title":"Duke Math. J."},{"key":"9626_CR8","doi-asserted-by":"crossref","unstructured":"Cevher, V., Kapralov, M., Scarlett, J., Zandieh, A.: An adaptive sublinear-time block sparse Fourier transform. arXiv: 1702.01286 (2017)","DOI":"10.1145\/3055399.3055462"},{"key":"9626_CR9","doi-asserted-by":"crossref","unstructured":"Cheraghchi, M., Indyk, P.: Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 298\u2013317 (2016)","DOI":"10.1137\/1.9781611974331.ch23"},{"key":"9626_CR10","unstructured":"Choi, B., Christlieb, A., Wang, Y.: Multi-dimensional sublinear sparse Fourier algorithm. arXiv: 160607407 (2016)"},{"issue":"3","key":"9626_CR11","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/j.acha.2015.04.002","volume":"40","author":"A Christlieb","year":"2016","unstructured":"Christlieb, A., Lawlor, D., Wang, Y.: A multiscale sub-linear time Fourier algorithm for noisy data. Appl. Comput. Harmon. Anal. 40(3), 553\u2013574 (2016)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9626_CR12","doi-asserted-by":"crossref","unstructured":"Feng, P., Bresler, Y.: Spectrum-blind minimum-rate sampling and reconstruction of multiband signals. In: 1996 IEEE International Conference on Acoustics, Speech, and Signal Processing Conference Proceedings, vol. 3, pp 1688\u20131691 (1996)","DOI":"10.1109\/ICASSP.1996.544131"},{"key":"9626_CR13","doi-asserted-by":"crossref","unstructured":"Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Birkh\u00e4user Basel (2013)","DOI":"10.1007\/978-0-8176-4948-7"},{"key":"9626_CR14","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, M., Strauss, M.J.: Near-optimal sparse Fourier representations via sampling. STOC (2002)","DOI":"10.1145\/509907.509933"},{"issue":"5","key":"9626_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1109\/MSP.2014.2329131","volume":"31","author":"AC Gilbert","year":"2014","unstructured":"Gilbert, A.C., Indyk, P., Iwen, M.A., Schmidt, L.: Recent developments in the sparse Fourier transform: a compressed Fourier transform for big data. IEEE Signal Process. Mag. 31(5), 91\u2013100 (2014)","journal-title":"IEEE Signal Process. Mag."},{"key":"9626_CR16","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Muthukrishnan, M., Strauss, M.J.: Improved time bounds for near-optimal space Fourier representations. SPIE Conference, Wavelets (2005)","DOI":"10.1117\/12.615931"},{"key":"9626_CR17","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Adib, F., Katabi, D., Indyk, P.: Faster GPS via the sparse Fourier transform MOBICOM (2012)","DOI":"10.1145\/2348543.2348587"},{"key":"9626_CR18","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Near-optimal algorithm for sparse Fourier transform STOC (2012)","DOI":"10.1137\/1.9781611973099.93"},{"key":"9626_CR19","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: sFFT: sparse fast Fourier transform. http:\/\/groups.csail.mit.edu\/netmit\/sFFT\/ (2012)","DOI":"10.1145\/2213977.2214029"},{"key":"9626_CR20","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse Fourier transform SODA (2012)","DOI":"10.1137\/1.9781611973099.93"},{"key":"9626_CR21","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Shi, L., Abari, O., Hamed, E., Katabi, D.: GHz-wide sensing and decoding using the sparse Fourier transform INFOCOM (2014)","DOI":"10.1109\/INFOCOM.2014.6848169"},{"key":"9626_CR22","unstructured":"Heider, S., Kunis, S., Potts, D.: Veit, M.: A sparse prony FFT. In: Proceedings of the 10th International Conference on Sampling Theory and Applications (SAMPTA), pp. 572\u2013575 (2013)"},{"issue":"4","key":"9626_CR23","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1007\/s11075-016-0184-x","volume":"74","author":"X Hu","year":"2017","unstructured":"Hu, X., Iwen, M.A., Kim, H.: Rapidly computing sparse Legendre expansions via sparse Fourier transforms. Numer. Algorithms 74(4), 1029\u20131059 (2017)","journal-title":"Numer. Algorithms"},{"key":"9626_CR24","doi-asserted-by":"crossref","unstructured":"Indyk, P., Kapralov, M., Price, E.: (Nearly) sample-optimal sparse Fourier transform SODA (2014)","DOI":"10.1137\/1.9781611973402.36"},{"key":"9626_CR25","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10208-009-9057-1","volume":"10","author":"MA Iwen","year":"2010","unstructured":"Iwen, M.A.: Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math. 10, 303\u2013338 (2010)","journal-title":"Found. Comput. Math."},{"key":"9626_CR26","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.acha.2012.03.007","volume":"34","author":"MA Iwen","year":"2013","unstructured":"Iwen, M.A.: Improved approximation guarantees for sublinear-time Fourier algorithms. Appl. Comput. Harmon. Anal. 34, 57\u201382 (2013)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9626_CR27","unstructured":"Iwen, M.A.: MSU\u2019s Sparse Fourier Repository. http:\/\/sourceforge.net\/projects\/aafftannarborfa\/ (2013)"},{"issue":"4","key":"9626_CR28","doi-asserted-by":"publisher","first-page":"981","DOI":"10.4310\/CMS.2007.v5.n4.a13","volume":"5","author":"MA Iwen","year":"2007","unstructured":"Iwen, M.A., Gilbert, A.C., Strauss, M.J.: Empirical evaluation of a sub-linear time sparse DFT Algorithm. Commun. Math. Sci. 5(4), 981\u2013998 (2007)","journal-title":"Commun. Math. Sci."},{"key":"9626_CR29","doi-asserted-by":"crossref","unstructured":"Iwen, M.A., Spencer, C.V.: Improved bounds for a deterministic sublinear-time sparse Fourier algorithm conference on information systems (CISS) (2008)","DOI":"10.1109\/CISS.2008.4558570"},{"key":"9626_CR30","volume-title":"Algebra, revised 3rd edn. Graduate Texts in Mathematics","author":"S Lang","year":"2005","unstructured":"Lang, S.: Algebra, revised 3rd edn. Graduate Texts in Mathematics. Springer, New York (2005)"},{"key":"9626_CR31","doi-asserted-by":"crossref","unstructured":"Laska, J., Kirolos, S., Massoud, Y., Baraniuk, R., Gilbert, A.C., Iwen, M.A., Strauss, M.J.: Random sampling for analog-to-information conversion of wideband signals. In: 2006 IEEE Dallas\/CAS Workshop On Design, Applications, Integration and Software, pp. 119\u2013122 (2006)","DOI":"10.1109\/DCAS.2006.321048"},{"issue":"01","key":"9626_CR32","doi-asserted-by":"publisher","first-page":"1350,003","DOI":"10.1142\/S1793536913500039","volume":"5","author":"D Lawlor","year":"2013","unstructured":"Lawlor, D., Wang, Y., Christlieb, A.: Adaptive sub-linear time fourier algorithms. Advances in Adaptive Data Analysis 5(01), 1350,003 (2013)","journal-title":"Advances in Adaptive Data Analysis"},{"key":"9626_CR33","doi-asserted-by":"crossref","unstructured":"Mansour, Y.: Randomized interpolation and approximation of sparse polynomials ICALP (1992)","DOI":"10.1007\/3-540-55719-9_79"},{"key":"9626_CR34","doi-asserted-by":"publisher","unstructured":"Merhi, S., Zhang, R., Iwen, M.A., Christlieb, A.: A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees. Fourier Anal. Appl. https:\/\/doi.org\/10.1007\/s00041-018-9616-4 (2018)","DOI":"10.1007\/s00041-018-9616-4"},{"issue":"3","key":"9626_CR35","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1109\/TSP.2009.2012791","volume":"57","author":"M Mishali","year":"2009","unstructured":"Mishali, M., Eldar, Y.C.: Blind multiband signal reconstruction: compressed sensing for analog signals. IEEE Trans. Signal Process. 57(3), 993\u20131009 (2009)","journal-title":"IEEE Trans. Signal Process."},{"issue":"2","key":"9626_CR36","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1109\/JSTSP.2010.2042414","volume":"4","author":"M Mishali","year":"2010","unstructured":"Mishali, M., Eldar, Y.C.: From Theory to Practice: Sub-Nyquist sampling of sparse wideband analog signals. IEEE J. Sel. Top. Sign. Process. 4(2), 375\u2013391 (2010)","journal-title":"IEEE J. Sel. Top. Sign. Process."},{"issue":"1","key":"9626_CR37","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1049\/iet-cds.2010.0147","volume":"5","author":"M Mishali","year":"2011","unstructured":"Mishali, M., Eldar, Y.C., Dounaevsky, O., Shoshan, E.: Xampling: analog to digital at sub-Nyquist rates. IET Circuits Devices Syst. 5(1), 8\u201320 (2011)","journal-title":"IET Circuits Devices Syst."},{"key":"9626_CR38","doi-asserted-by":"crossref","unstructured":"Mishali, M., Eldar, Y.C., Tropp, J.A.: Efficient sampling of sparse wideband analog signals. In: 2008 IEEE 25th Convention of Electrical and Electronics Engineers in Israel, pp. 290\u2013294 (2008)","DOI":"10.1109\/EEEI.2008.4736707"},{"key":"9626_CR39","volume-title":"Multiplicative Number Theory I: Classical Theory. Cambridge Studies in Advanced Mathematics","author":"H Montgomery","year":"2007","unstructured":"Montgomery, H., Vaughan, R.: Multiplicative Number Theory I: Classical Theory. Cambridge Studies in Advanced Mathematics. Cambridge university press, Cambridge (2007)"},{"issue":"2","key":"9626_CR40","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.acha.2016.06.001","volume":"43","author":"L Morotti","year":"2017","unstructured":"Morotti, L.: Explicit universal sampling sets in finite vector spaces. Appl. Comput. Harmon. Anal. 43(2), 354\u2013369 (2017)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"2","key":"9626_CR41","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1002\/gamm.201410011","volume":"37","author":"G Plonka","year":"2014","unstructured":"Plonka, G., Tasche, M.: Prony methods for recovery of structured functions. GAMM-Mitt. 37(2), 239\u2013258 (2014)","journal-title":"GAMM-Mitt."},{"issue":"4","key":"9626_CR42","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1007\/s11075-015-0028-0","volume":"71","author":"G Plonka","year":"2016","unstructured":"Plonka, G., Wannenwetsch, K.: A deterministic sparse FFT algorithm for vectors with small support. Numer. Algorithms 71(4), 889\u2013905 (2016)","journal-title":"Numer. Algorithms"},{"key":"9626_CR43","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1016\/j.cam.2017.03.019","volume":"321","author":"G Plonka","year":"2017","unstructured":"Plonka, G., Wannenwetsch, K.: A sparse fast Fourier algorithm for real non-negative vectors. J. Comput. Appl. Math. 321, 532\u2013539 (2017)","journal-title":"J. Comput. Appl. Math."},{"key":"9626_CR44","doi-asserted-by":"publisher","unstructured":"Plonka, G., Wannenwetsch, K., Cuyt, A., Lee, W.S.: Deterministic sparse FFT for M-sparse vectors https:\/\/doi.org\/10.1007\/s11075-017-0370-5 (2017)","DOI":"10.1007\/s11075-017-0370-5"},{"key":"9626_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3389\/fams.2016.00001","volume":"2","author":"D Potts","year":"2016","unstructured":"Potts, D., Tasche, M., Volkmer, T.: Efficient spectral estimation by MUSIC and ESPRIT with application to sparse FFT. Frontiers in Applied Mathematics and Statistics 2, 1 (2016)","journal-title":"Frontiers in Applied Mathematics and Statistics"},{"key":"9626_CR46","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1109\/TAU.1969.1162034","volume":"17","author":"LR Rabiner","year":"1969","unstructured":"Rabiner, L.R., Schafer, R.W., Rader, C.M.: The chirp-z transform algorithm. IEEE Trans. Audio Electroacoust. 17, 86\u201392 (1969)","journal-title":"IEEE Trans. Audio Electroacoust."},{"issue":"2","key":"9626_CR47","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s11075-012-9621-7","volume":"63","author":"B Segal","year":"2013","unstructured":"Segal, B., Iwen, M.A.: Improved sparse Fourier approximation results: faster implementations and stronger guarantees. Numer. Algorithms 63(2), 239\u2013263 (2013)","journal-title":"Numer. Algorithms"},{"key":"9626_CR48","doi-asserted-by":"publisher","unstructured":"Yenduri, P., Gilbert, A.C.: Compressive, collaborative spectrum sensing for wideband cognitive radios. https:\/\/doi.org\/10.1109\/ISWCS.2012.6328424 (2012)","DOI":"10.1109\/ISWCS.2012.6328424"},{"issue":"3","key":"9626_CR49","first-page":"502","volume":"2","author":"PK Yenduri","year":"2012","unstructured":"Yenduri, P.K., Rocca, A.Z., Rao, A.S., Naraghi, S., Flynn, M.P., Gilbert, A.C.: A low-power compressive sampling time-based analog-to-digital converter. IEEE J. Em. Sel. Top. C. 2(3), 502\u2013515 (2012)","journal-title":"IEEE J. Em. Sel. Top. C."}],"container-title":["Advances in Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10444-018-9626-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10444-018-9626-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10444-018-9626-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T07:59:32Z","timestamp":1751788772000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10444-018-9626-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,9]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9626"],"URL":"https:\/\/doi.org\/10.1007\/s10444-018-9626-4","relation":{},"ISSN":["1019-7168","1572-9044"],"issn-type":[{"value":"1019-7168","type":"print"},{"value":"1572-9044","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,9]]},"assertion":[{"value":"21 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}