{"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":1772138392738,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T00:00:00Z","timestamp":1594771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T00:00:00Z","timestamp":1594771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-11- 1-0281,FA9550-12-1-0343,FA9550-12-1-0455,"],"award-info":[{"award-number":["FA9550-11- 1-0281,FA9550-12-1-0343,FA9550-12-1-0455,"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["DMS-1115709"],"award-info":[{"award-number":["DMS-1115709"]}]},{"DOI":"10.13039\/100016254","name":"MSU Foundation","doi-asserted-by":"crossref","award":["SPG-RG100059"],"award-info":[{"award-number":["SPG-RG100059"]}],"id":[{"id":"10.13039\/100016254","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Hong Kong Research Grant Council","award":["16306415,16317416,16308518"],"award-info":[{"award-number":["16306415,16317416,16308518"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s11075-020-00962-1","type":"journal-article","created":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T02:02:31Z","timestamp":1594778551000},"page":"161-186","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["High-dimensional sparse Fourier algorithms"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1659-5777","authenticated-orcid":false,"given":"Bosu","family":"Choi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Christlieb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,15]]},"reference":[{"issue":"2","key":"962_CR1","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s10444-018-9626-4","volume":"45","author":"S Bittens","year":"2019","unstructured":"Bittens, S., Zhang, R., Iwen, M.A.: A deterministic sparse FFT for functions with structured Fourier sparsity. Adv. Comput. Math. 45(2), 519\u2013561 (2019)","journal-title":"Adv. Comput. Math."},{"key":"962_CR2","doi-asserted-by":"crossref","unstructured":"Choi, B., Christlieb, A., Wang, Y.: Multiscale high-dimensional sparse Fourier algorithms for noisy data. arXiv:1907.03692 (2019)","DOI":"10.4310\/MCGD.2020.v1.n1.a2"},{"key":"962_CR3","unstructured":"Choi, B., Iwen, M., Krahmer, F.: Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables (2018)"},{"issue":"3","key":"962_CR4","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":"962_CR5","doi-asserted-by":"crossref","unstructured":"Ghazi, B., Hassanieh, H., Indyk, P., Katabi, D., Price, E., Shi, L.: Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions. In: 2013 51St Annual Allerton Conference On Communication, Control, and Computing (Allerton), pp. 1258\u20131265. IEEE (2013)","DOI":"10.1109\/Allerton.2013.6736670"},{"key":"962_CR6","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse Fourier representations via sampling. In: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 152\u2013161. ACM (2002)","DOI":"10.1145\/509907.509933"},{"key":"962_CR7","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Muthukrishnan, S., Strauss, M.: Improved Time Bounds for Near-Optimal Sparse Fourier Representations. In: Optics & Photonics 2005, pp. 59141A\u201359141A. International Society for Optics and Photonics (2005)","DOI":"10.1117\/12.615931"},{"issue":"6","key":"962_CR8","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1038\/ng.3259","volume":"47","author":"CS Greene","year":"2015","unstructured":"Greene, C.S., Krishnan, A., Wong, A.K., Ricciotti, E., Zelaya, R.A., Himmelstein, D.S., Zhang, R., Hartmann, B.M., Zaslavsky, E., Sealfon, S.C., et al.: Understanding multicellular function and disease with human tissue-specific networks. Nat. Gen. 47(6), 569\u2013576 (2015)","journal-title":"Nat. Gen."},{"key":"962_CR9","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Nearly optimal sparse Fourier transform. In: Proceedings of the forty-fourth annual ACM symposium on theory of computing, pp. 563\u2013578. ACM (2012)","DOI":"10.1145\/2213977.2214029"},{"key":"962_CR10","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, pp. 1183\u20131194. Society for Industrial and Applied Mathematics (2012)","DOI":"10.1137\/1.9781611973099.93"},{"issue":"3","key":"962_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":"962_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."},{"issue":"4","key":"962_CR13","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.jco.2015.02.004","volume":"31","author":"L K\u00e4mmerer","year":"2015","unstructured":"K\u00e4mmerer, L., Potts, D., Volkmer, T.: Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling. J. Complex. 31(4), 543\u2013576 (2015). https:\/\/doi.org\/10.1016\/j.jco.2015.02.004. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0885064X15000217","journal-title":"J. Complex."},{"key":"962_CR14","unstructured":"K\u00e4mmerer, L., Potts, D., Volkmer, T.: High-dimensional sparse fft based on sampling along multiple rank-1 lattices. arXiv:1711.05152 (2017)"},{"issue":"01","key":"962_CR15","doi-asserted-by":"publisher","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(01), 1350003 (2013)","journal-title":"Adv. Adapt. Data Anal."},{"key":"962_CR16","unstructured":"LSST: large synoptic survey telescope. http:\/\/www.lsst.org\/"},{"issue":"3","key":"962_CR17","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1007\/s00041-018-9616-4","volume":"25","author":"S Merhi","year":"2019","unstructured":"Merhi, S., Zhang, R., Iwen, M.A., Christlieb, A.: A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees. J. Fourier Anal. Appl. 25(3), 751\u2013784 (2019)","journal-title":"J. Fourier Anal. Appl."},{"issue":"4","key":"962_CR18","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. Algorithm. 71(4), 889\u2013905 (2016). https:\/\/doi.org\/10.1007\/s11075-015-0028-0","journal-title":"Numer. Algorithm."},{"issue":"1","key":"962_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. Algorithm. 78(1), 133\u2013159 (2018). https:\/\/doi.org\/10.1007\/s11075-017-0370-5","journal-title":"Numer. Algorithm."},{"issue":"1","key":"962_CR20","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s12190-012-0624-2","volume":"42","author":"G Plonka","year":"2013","unstructured":"Plonka, G., Wischerhoff, M.: How many Fourier samples are needed for real function reconstruction? J. Appl. Math. Comput. 42(1), 117\u2013137 (2013). https:\/\/doi.org\/10.1007\/s12190-012-0624-2","journal-title":"J. Appl. Math. Comput."},{"key":"962_CR21","first-page":"204","volume":"40","author":"D Potts","year":"2013","unstructured":"Potts, D., Tasche, M.: Parameter estimation for multivariate exponential sums. Electron. Trans. Numer. Anal. 40, 204\u2013224 (2013)","journal-title":"Electron. Trans. Numer. Anal."},{"key":"962_CR22","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. Front. Appl. Math. Stat. 2, 1 (2016). https:\/\/doi.org\/10.3389\/fams.2016.00001","journal-title":"Front. Appl. Math. Stat."},{"issue":"3","key":"962_CR23","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1016\/j.acha.2015.05.002","volume":"41","author":"D Potts","year":"2016","unstructured":"Potts, D., Volkmer, T.: Sparse high-dimensional FFT based on rank-1 lattice sampling. Appl. Comput. Harmon. Anal. 41(3), 713\u2013748 (2016)","journal-title":"Appl. Comput. Harmon. Anal."}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-020-00962-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11075-020-00962-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-020-00962-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T23:21:04Z","timestamp":1626304864000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11075-020-00962-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,15]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["962"],"URL":"https:\/\/doi.org\/10.1007\/s11075-020-00962-1","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"value":"1017-1398","type":"print"},{"value":"1572-9265","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,15]]},"assertion":[{"value":"28 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}