{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T16:35:31Z","timestamp":1764002131691,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,7,5]],"date-time":"2017-07-05T00:00:00Z","timestamp":1499212800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["PL 170\/16-1","RTG 2088"],"award-info":[{"award-number":["PL 170\/16-1","RTG 2088"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s11075-017-0370-5","type":"journal-article","created":{"date-parts":[[2017,7,5]],"date-time":"2017-07-05T10:14:51Z","timestamp":1499249691000},"page":"133-159","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Deterministic sparse FFT for M-sparse vectors"],"prefix":"10.1007","volume":"78","author":[{"given":"Gerlind","family":"Plonka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katrin","family":"Wannenwetsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Annie","family":"Cuyt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen-shin","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,5]]},"reference":[{"issue":"3","key":"370_CR1","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1109\/TIT.2013.2290027","volume":"60","author":"A Akavia","year":"2014","unstructured":"Akavia, A.: Deterministic sparse fourier approximation via approximating arithmetic progressions. IEEE Trans. Inform. Theory 60(3), 1733\u20131741 (2014)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"370_CR2","doi-asserted-by":"crossref","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."},{"key":"370_CR3","doi-asserted-by":"crossref","first-page":"157","DOI":"10.13001\/1081-3810.1190","volume":"16","author":"L Berman","year":"2007","unstructured":"Berman, L., Feuer, A.: On perfect conditioning of Vandermonde matrices on the unit circle. Electron. J. Linear Algebra 16, 157\u2013161 (2007)","journal-title":"Electron. J. Linear Algebra"},{"key":"370_CR4","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0024-3795(89)90652-6","volume":"122\u2013124","author":"CJ Demeure","year":"1989","unstructured":"Demeure, C.J.: Fast Q R factorization of Vandermonde matrices. Linear Algebra Appl. 122\u2013124, 165\u2013194 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"8","key":"370_CR5","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1016\/j.jsc.2008.11.003","volume":"44","author":"M Giesbrecht","year":"2009","unstructured":"Giesbrecht, M., Labahn, G., Lee, W. -S.: Symbolic-numeric sparse interpolation of multivariate polynomials. J. Symbolic Comput. 44(8), 943\u2013959 (2009)","journal-title":"J. Symbolic Comput."},{"doi-asserted-by":"crossref","unstructured":"Giesbrecht, M., Roche, D.S.: Diversification improves interpolation. In: Leykin, A. (ed.) Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation ISSAC 2011, pp 123\u2013130. ACM","key":"370_CR6","DOI":"10.1145\/1993886.1993909"},{"issue":"5","key":"370_CR7","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1109\/MSP.2014.2329131","volume":"31","author":"A Gilbert","year":"2014","unstructured":"Gilbert, A., Indyk, P., Iwen, M.A., Schmidt, L.: Recent developments in the sparse fourier transform. IEEE Signal Process. Mag. 31(5), 91\u2013100 (2014)","journal-title":"IEEE Signal Process. Mag."},{"doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse fourier transform. In: Proc. 23th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201912), pp. 1183\u20131194 (2012)","key":"370_CR8","DOI":"10.1137\/1.9781611973099.93"},{"doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Adib, F., Katabi, D., Indyk, P.: Faster GPS via the sparse fourier transform. In: Proceeding Mobicom 2012, Proceedings of the 18th Annual International Conference on Mobile Computing and networking, pp. 353\u2013364 (2012)","key":"370_CR9","DOI":"10.1145\/2348543.2348587"},{"key":"370_CR10","doi-asserted-by":"crossref","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":"370_CR11","doi-asserted-by":"crossref","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."},{"unstructured":"Janakiraman, N.T., Vem, A., Narayanan, K.R., Chamberland, J.-F.: Sub-string\/pattern matching in sub-linear time using a sparse Fourier transform approach, preprint, arXiv: 1704.07852v1","key":"370_CR12"},{"doi-asserted-by":"crossref","unstructured":"Moitra, A.: Super-resolution, extremal functions and the condition number of Vandermonde matrices. In: STOC \u201915 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 821\u2013830 (2015)","key":"370_CR13","DOI":"10.1145\/2746539.2746561"},{"key":"370_CR14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1112\/jlms\/s2-8.1.73","volume":"8","author":"HL Montgomery","year":"1974","unstructured":"Montgomery, H.L., Vaughan, R.C.: Hilbert\u2019s inequality. J. London Math. Soc. (2) 8, 73\u201382 (1974)","journal-title":"J. London Math. Soc. (2)"},{"issue":"1","key":"370_CR15","doi-asserted-by":"crossref","first-page":"1350003","DOI":"10.1142\/S1793536913500039","volume":"5","author":"D Lawlor","year":"2013","unstructured":"Lawlor, D., Wang, Y., Christlieb, A.: Adaptive sub-linear time Fourier algorithms. Adv. Adapt. Data Anal. 5(1), 1350003 (2013)","journal-title":"Adv. Adapt. Data Anal."},{"doi-asserted-by":"crossref","unstructured":"Pawar, S., Ramchandran, K.: Computing a k-sparse n-length discrete Fourier transform using at most 4k samples and O ( kk ) $\\mathcal {O}(k k)$ complexity. IEEE Int. Symp. Inf. Theory, 464\u2013468 (2013)","key":"370_CR16","DOI":"10.1109\/ISIT.2013.6620269"},{"doi-asserted-by":"crossref","unstructured":"Potts, D., Tasche, M., Volkmer, T.: Efficient spectral estimation by MUSIC and ESPRIT with application to sparse FFT. Frontiers Appl. Math. Stat. (2016)","key":"370_CR17","DOI":"10.3389\/fams.2016.00001"},{"issue":"4","key":"370_CR18","doi-asserted-by":"crossref","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":"370_CR19","doi-asserted-by":"crossref","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."},{"issue":"2","key":"370_CR20","doi-asserted-by":"crossref","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. Algor. 63(2), 239\u2013263 (2013)","journal-title":"Numer. Algor."}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11075-017-0370-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-017-0370-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-017-0370-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T11:10:45Z","timestamp":1569669045000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11075-017-0370-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,5]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["370"],"URL":"https:\/\/doi.org\/10.1007\/s11075-017-0370-5","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"type":"print","value":"1017-1398"},{"type":"electronic","value":"1572-9265"}],"subject":[],"published":{"date-parts":[[2017,7,5]]}}}