{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T16:37:11Z","timestamp":1764002231242,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,11,21]],"date-time":"2018-11-21T00:00:00Z","timestamp":1542758400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GRK 2088"],"award-info":[{"award-number":["GRK 2088"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s11075-018-0620-1","type":"journal-article","created":{"date-parts":[[2018,11,21]],"date-time":"2018-11-21T00:41:21Z","timestamp":1542760881000},"page":"663-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Sparse fast DCT for vectors with one-block support"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5923-4210","authenticated-orcid":false,"given":"Sina","family":"Bittens","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerlind","family":"Plonka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,11,21]]},"reference":[{"issue":"3","key":"620_CR1","doi-asserted-by":"publisher","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":"620_CR2","first-page":"43","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":"620_CR3","doi-asserted-by":"crossref","unstructured":"Bittens, S., Plonka, G.: Sparse fast DCT for vectors with one-block support. \n                    http:\/\/na.math.uni-goettingen.de\/index.php?section=gruppe&subsection=software\n                    \n                   (2018)","DOI":"10.1007\/s11075-018-0620-1"},{"key":"620_CR4","doi-asserted-by":"crossref","unstructured":"Bittens, S., Plonka, G.: Sparse FFT for vectors with reflected block support. \n                    http:\/\/na.math.uni-goettingen.de\/index.php?section=gruppe&subsection=software\n                    \n                   (2018)","DOI":"10.1007\/s11075-018-0620-1"},{"key":"620_CR5","doi-asserted-by":"publisher","unstructured":"Bittens, S., Zhang, R., Iwen, M.A.: A deterministic sparse FFT for functions with structured Fourier sparsity. Adv. Comput. Math. (2018). \n                    https:\/\/doi.org\/10.1007\/s10444-018-9626-4","DOI":"10.1007\/s10444-018-9626-4"},{"issue":"3","key":"620_CR6","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":"620_CR7","unstructured":"Frigo, M., Johnson, S.G.: FFTW 3.3.6. \n                    http:\/\/www.fftw.org\/\n                    \n                   (2017)"},{"issue":"5","key":"620_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1109\/MSP.2014.2329131","volume":"31","author":"A Gilbert","year":"2014","unstructured":"Gilbert, A., Indyk, P., Iwen, M., 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":"620_CR9","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse Fourier transform. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201912, pp. 1183\u20131194 (2012)","DOI":"10.1137\/1.9781611973099.93"},{"issue":"4","key":"620_CR10","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., Kim, H.: Rapidly computing sparse Legendre expansions via sparse Fourier transforms. Numer. Algor. 74(4), 1029\u20131059 (2017)","journal-title":"Numer. Algor."},{"issue":"3","key":"620_CR11","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(3), 303\u2013338 (2010)","journal-title":"Found. Comput. Math."},{"issue":"1","key":"620_CR12","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(1), 57\u201382 (2013)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"620_CR13","doi-asserted-by":"crossref","unstructured":"Pawar, S., Ramchandran, K.: Computing a k-sparse n-length discrete Fourier transform using at most 4k samples and \n                    \n                      \n                    \n                    \n                      \n                        O\n                        (\n                        k\n                        log\n                        k\n                        )\n                      \n                    \n                    $\\mathcal {O}(k \\log k)$\n                   complexity. In: IEEE International Symposium on Information Theory, pp. 464\u2013468 (2013)","DOI":"10.1109\/ISIT.2013.6620269"},{"key":"620_CR14","doi-asserted-by":"crossref","unstructured":"Plonka, G., Potts, D., Steidl, G., Tasche, M.: Numerical Fourier Analysis. Birkh\u00e4user Basel. \n                    https:\/\/www.springer.com\/us\/book\/9783030043056\n                    \n                   (2018)","DOI":"10.1007\/978-3-030-04306-3"},{"key":"620_CR15","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.laa.2004.07.015","volume":"394","author":"G Plonka","year":"2005","unstructured":"Plonka, G., Tasche, M.: Fast and numerically stable algorithms for discrete cosine transforms. Linear Algebra Appl. 394, 309\u2013345 (2005)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"620_CR16","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":"620_CR17","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":"620_CR18","unstructured":"Plonka, G., Wannenwetsch, K.: Deterministic sparse FFT. \n                    http:\/\/na.math.uni-goettingen.de\/index.php?section=gruppe&subsection=software\n                    \n                   (2017)"},{"issue":"1","key":"620_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s11075-017-0370-5","volume":"78","author":"G Plonka","year":"2018","unstructured":"Plonka, G., Wannenwetsch, K., Cuyt, A., Lee, W.-S.: Deterministic sparse FFT for M-sparse vectors. Numer. Algorithms 78(1), 133\u2013159 (2018)","journal-title":"Numer. Algorithms"},{"issue":"3","key":"620_CR20","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1007\/s10543-015-0598-1","volume":"56","author":"D Potts","year":"2016","unstructured":"Potts, D., Tasche, M.: Reconstruction of sparse Legendre and Gegenbauer expansions. BIT Numer. Math. 56(3), 1019\u20131043 (2016)","journal-title":"BIT Numer. Math."},{"key":"620_CR21","doi-asserted-by":"crossref","unstructured":"Rao, K., Yip, P.: Discrete Cosine Transform: Algorithms, Advantages, Applications. Academic Press (1990)","DOI":"10.1016\/B978-0-08-092534-9.50007-2"},{"issue":"2","key":"620_CR22","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.: Improved sparse Fourier approximation results: faster implementations and stronger guarantees. Numer. Algorithms 63(2), 239\u2013263 (2013)","journal-title":"Numer. Algorithms"},{"key":"620_CR23","unstructured":"The MathWorks: Matlab\u2019s documentation of fft. \n                    https:\/\/www.mathworks.com\/help\/matlab\/ref\/fft.html\n                    \n                   (2017)"},{"key":"620_CR24","unstructured":"The MathWorks: Matlab\u2019s documentation of idct. \n                    https:\/\/www.mathworks.com\/help\/signal\/ref\/idct.html\n                    \n                   (2017)"},{"key":"620_CR25","unstructured":"The MathWorks: Matlab\u2019s documentation of ifft. \n                    https:\/\/www.mathworks.com\/help\/matlab\/ref\/ifft.html\n                    \n                   (2017)"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-018-0620-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11075-018-0620-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-018-0620-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,20]],"date-time":"2019-11-20T19:37:21Z","timestamp":1574278641000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11075-018-0620-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,21]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["620"],"URL":"https:\/\/doi.org\/10.1007\/s11075-018-0620-1","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"type":"print","value":"1017-1398"},{"type":"electronic","value":"1572-9265"}],"subject":[],"published":{"date-parts":[[2018,11,21]]},"assertion":[{"value":"14 March 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}