{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:41:19Z","timestamp":1740123679885,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T00:00:00Z","timestamp":1638835200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T00:00:00Z","timestamp":1638835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["380648269"],"award-info":[{"award-number":["380648269"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["4512\/1-1"],"award-info":[{"award-number":["4512\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006298","name":"S\u00e4chsische Aufbaubank","doi-asserted-by":"publisher","award":["100378180"],"award-info":[{"award-number":["100378180"]}],"id":[{"id":"10.13039\/501100006298","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009117","name":"Technische Universit\u00e4t Chemnitz","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009117","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, a sublinear time algorithm is presented for the reconstruction of functions that can be represented by just few out of a potentially large candidate set of Fourier basis functions in high spatial dimensions, a so-called high-dimensional sparse fast Fourier transform. In contrast to many other such algorithms, our method works for arbitrary candidate sets and does not make additional structural assumptions on the candidate set. Our transform significantly improves upon the other approaches available for such a general framework in terms of the scaling of the sample complexity. Our algorithm is based on sampling the function along multiple rank-1 lattices with random generators. Combined with a dimension-incremental approach, our method yields a sparse Fourier transform whose computational complexity only grows mildly in the dimension and can hence be efficiently computed even in high dimensions. Our theoretical analysis establishes that any Fourier <jats:italic>s<\/jats:italic>-sparse function can be accurately reconstructed with high probability. This guarantee is complemented by several numerical tests demonstrating the high efficiency and versatile applicability for the exactly sparse case and also for the compressible case.<\/jats:p>","DOI":"10.1007\/s11075-021-01162-1","type":"journal-article","created":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T07:03:52Z","timestamp":1638860632000},"page":"1479-1520","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions"],"prefix":"10.1007","volume":"89","author":[{"given":"Lutz","family":"K\u00e4mmerer","sequence":"first","affiliation":[]},{"given":"Felix","family":"Krahmer","sequence":"additional","affiliation":[]},{"given":"Toni","family":"Volkmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,7]]},"reference":[{"key":"1162_CR1","doi-asserted-by":"crossref","unstructured":"Al-Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Nearly optimal sparse Fourier transform. In: Proceedings of STOC, pp. 563\u2013577 (2012)","DOI":"10.1145\/2213977.2214029"},{"key":"1162_CR2","doi-asserted-by":"crossref","unstructured":"Al-Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse Fourier transform. In: Proceedings of SODA, pp. 1183\u20131194 (2012)","DOI":"10.1137\/1.9781611973099.93"},{"key":"1162_CR3","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R. W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. Int. 7, 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci. Int."},{"key":"1162_CR4","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1088\/0266-5611\/23\/3\/008","volume":"23","author":"E Cand\u00e8s","year":"2007","unstructured":"Cand\u00e8s, E., Romberg, J.: Sparsity and incoherence in compressive sampling. Inverse Probl. 23, 969\u2013985 (2007)","journal-title":"Inverse Probl."},{"key":"1162_CR5","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Tao, T., Romberg, J.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52, 489\u2013509 (2006)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"1162_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.4310\/MCGD.2021.v1.n1.a2","volume":"1","author":"B Choi","year":"2021","unstructured":"Choi, B., Christlieb, A., Wang, Y.: Multiscale High-Dimensional Sparse Fourier Algorithms for Noisy Data. Mathematics, Computation and Geometry of Data 1, 35\u201358 (2021)","journal-title":"Mathematics, Computation and Geometry of Data"},{"key":"1162_CR7","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s11075-020-00962-1","volume":"87","author":"B Choi","year":"2021","unstructured":"Choi, B., Christlieb, A., Wang, Y.: High-dimensional sparse Fourier algorithms. Numer. Algorithms 87, 161\u2013186 (2021)","journal-title":"Numer. Algorithms"},{"key":"1162_CR8","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10208-020-09462-z","volume":"21","author":"B Choi","year":"2021","unstructured":"Choi, B., Iwen, M., Krahmer, F.: Sparse Harmonic Transforms: A New Class of Sublinear-Time Algorithms for Learning Functions of Many Variables. Found. Comput. Math. 21, 275\u2013329 (2021)","journal-title":"Found. Comput. Math."},{"key":"1162_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00211-021-01200-z","volume":"148","author":"B Choi","year":"2021","unstructured":"Choi, B., Iwen, M., Volkmer, T.: Sparse Harmonic Transforms II: Best s-Term Approximation Guarantees for Bounded Orthonormal Product Bases in Sublinear-Time. Numerische Mathematik 148, 293\u2013362 (2021)","journal-title":"Numerische Mathematik"},{"key":"1162_CR10","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, 553\u2013574 (2016)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1162_CR11","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J Cooley","year":"1965","unstructured":"Cooley, J., Tukey, J.: An algorithm for the machine calculation of complex Fourier series. Math. Comp. 19, 297\u2013301 (1965)","journal-title":"Math. Comp."},{"key":"1162_CR12","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: Combinatorial algorithms for compressed sensing. In: 2006 40th Annual Conference on Information Sciences and Systems, pp. 198\u2013201 (2006)","DOI":"10.1109\/CISS.2006.286461"},{"key":"1162_CR13","doi-asserted-by":"publisher","first-page":"B675","DOI":"10.1137\/19M1278004","volume":"42","author":"A Cuyt","year":"2020","unstructured":"Cuyt, A., Hou, Y., Knaepkens, F., Lee, W.S.: Sparse multidimensional exponential analysis with an application to radar imaging. SIAM J. Sci. Comput. 42, B675\u2013B695 (2020)","journal-title":"SIAM J. Sci. Comput."},{"key":"1162_CR14","doi-asserted-by":"publisher","first-page":"4415","DOI":"10.1137\/090754947","volume":"47","author":"M D\u00f6hler","year":"2010","unstructured":"D\u00f6hler, M., Kunis, S., Potts, D.: Nonequispaced hyperbolic cross fast Fourier transform. SIAM J. Numer. Anal. 47, 4415\u20134428 (2010)","journal-title":"SIAM J. Numer. Anal."},{"key":"1162_CR15","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s11139-016-9839-4","volume":"45","author":"P Dusart","year":"2018","unstructured":"Dusart, P.: Explicit estimates of some functions over primes. Ramanujan J. 45, 227\u2013251 (2018)","journal-title":"Ramanujan J."},{"key":"1162_CR16","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Muthukrishnan, S., Strauss, M.: Improved time bounds for near-optimal sparse Fourier representations. In: Proceedings of SPIE (2005)","DOI":"10.1117\/12.615931"},{"key":"1162_CR17","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 Thirty-Fourth Annual ACM Symposium on Theory of Computing, STOC \u201902, pp 152\u2013161. Association for Computing Machinery, New York (2002)","DOI":"10.1145\/509907.509933"},{"key":"1162_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 13\u201330 (1963)","journal-title":"J. Amer. Statist. Assoc."},{"key":"1162_CR19","doi-asserted-by":"crossref","unstructured":"Indyk, P., Kapralov, M.: Sample-optimal Fourier sampling in any constant dimension. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 514\u2013523 (2014)","DOI":"10.1109\/FOCS.2014.61"},{"key":"1162_CR20","unstructured":"Iwen, M.: A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 20\u201329 (2008)"},{"key":"1162_CR21","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10208-009-9057-1","volume":"10","author":"M Iwen","year":"2010","unstructured":"Iwen, M.: Combinatorial sublinear-time Fourier algorithms. Found. Comp. Math. 10, 303\u2013338 (2010)","journal-title":"Found. Comp. Math."},{"key":"1162_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.acha.2012.03.007","volume":"34","author":"M Iwen","year":"2013","unstructured":"Iwen, M.: Improved approximation guarantees for sublinear-time Fourier algorithms. Appl. Comp. Harmonic Anal. 34, 57\u201382 (2013)","journal-title":"Appl. Comp. Harmonic Anal."},{"key":"1162_CR23","unstructured":"K\u00e4mmerer, L.: High Dimensional Fast Fourier Transform Based on Rank-1 Lattice Sampling. Dissertation Universit\u00e4tsverlag Chemnitz (2014)"},{"key":"1162_CR24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s00041-016-9520-8","volume":"24","author":"L K\u00e4mmerer","year":"2018","unstructured":"K\u00e4mmerer, L.: Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials. J. Fourier Anal. Appl. 24, 17\u201344 (2018)","journal-title":"J. Fourier Anal. Appl."},{"key":"1162_CR25","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.acha.2017.11.008","volume":"42","author":"L K\u00e4mmerer","year":"2019","unstructured":"K\u00e4mmerer, L.: Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform. Appl. Comput. Harmon. Anal. 42, 702\u2013729 (2019)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1162_CR26","doi-asserted-by":"crossref","unstructured":"K\u00e4mmerer, L., Potts, D., Volkmer, T.: High-dimensional sparse FFT based on sampling along multiple rank-1 lattices. Applied and Computational Harmonic Analysis 51, 225\u2013257 (2021)","DOI":"10.1016\/j.acha.2020.11.002"},{"key":"1162_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jat.2019.05.001","volume":"246","author":"L K\u00e4mmerer","year":"2019","unstructured":"K\u00e4mmerer, L., Volkmer, T.: Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices. J. Approx. Theory 246, 1\u201327 (2019)","journal-title":"J. Approx. Theory"},{"key":"1162_CR28","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1109\/TIP.2013.2288004","volume":"23","author":"F Krahmer","year":"2014","unstructured":"Krahmer, F., Ward, R.: Stable and robust sampling strategies for compressive imaging. IEEE Trans. Image Proc. 23, 612\u2013622 (2014)","journal-title":"IEEE Trans. Image Proc."},{"key":"1162_CR29","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, 1350003\u20131\/\u201325 (2013)","journal-title":"Adv. Adapt. Data Anal."},{"key":"1162_CR30","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, 354\u2013369 (2017)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1162_CR31","doi-asserted-by":"crossref","unstructured":"Potts, D., Steidl, G., Tasche, M.: Fast Fourier transforms for nonequispaced data: A tutorial. In: Modern Sampling Theory, pp. 247\u2013270. Springer (2001)","DOI":"10.1007\/978-1-4612-0143-4_12"},{"key":"1162_CR32","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":"1162_CR33","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, 713\u2013748 (2016)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1162_CR34","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1002\/cpa.20227","volume":"61","author":"M Rudelson","year":"2008","unstructured":"Rudelson, M., Vershynin, R.: On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure Appl. Math. 61, 1025\u20131045 (2008)","journal-title":"Comm. Pure Appl. Math."},{"key":"1162_CR35","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM \u201979, pp 216\u2013226. Springer, London (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-021-01162-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11075-021-01162-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-021-01162-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T10:26:05Z","timestamp":1647858365000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11075-021-01162-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,7]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["1162"],"URL":"https:\/\/doi.org\/10.1007\/s11075-021-01162-1","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"type":"print","value":"1017-1398"},{"type":"electronic","value":"1572-9265"}],"subject":[],"published":{"date-parts":[[2021,12,7]]},"assertion":[{"value":"27 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of interest"}}]}}