{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T09:15:37Z","timestamp":1781601337323,"version":"3.54.5"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T00:00:00Z","timestamp":1687564800000},"content-version":"vor","delay-in-days":23,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"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. Math."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We use hyperbolic wavelet regression for the fast reconstruction of high-dimensional functions having only low dimensional variable interactions. Compactly supported periodic Chui\u2013Wang wavelets are used for the tensorized hyperbolic wavelet basis. In a first step we give a self-contained characterization of tensor product Sobolev\u2013Besov spaces on the<jats:italic>d<\/jats:italic>-torus with arbitrary smoothness in terms of the decay of such wavelet coefficients. In the second part we perform and analyze scattered-data approximation using a hyperbolic cross type truncation of the basis expansion for the associated least squares method. The corresponding system matrix is sparse due to the compact support of the wavelets, which leads to a significant acceleration of the matrix vector multiplication. In case of i.i.d. samples we can even bound the approximation error with high probability by loosing only<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\log $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mo>log<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-terms that do not depend on<jats:italic>d<\/jats:italic>compared to the best approximation. In addition, if the function has low effective dimension (i.e. only interactions of few variables), we qualitatively determine the variable interactions and omit ANOVA terms with low variance in a second step in order to increase the accuracy. This allows us to suggest an adapted model for the approximation. Numerical results show the efficiency of the proposed method.<\/jats:p>","DOI":"10.1007\/s00211-023-01358-8","type":"journal-article","created":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T11:46:34Z","timestamp":1687607194000},"page":"155-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Fast hyperbolic wavelet regression meets ANOVA"],"prefix":"10.1007","volume":"154","author":[{"given":"Laura","family":"Lippert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Potts","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tino","family":"Ullrich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,6,24]]},"reference":[{"key":"1358_CR1","volume-title":"Iterative Solution Methods","author":"O Axelsson","year":"1996","unstructured":"Axelsson, O.: Iterative Solution Methods. Cambridge University Press, Cambridge (1996)"},{"key":"1358_CR2","doi-asserted-by":"crossref","unstructured":"Bartel, F.: Stability and error guarantees for least squares approximation with noisy samples. SMAI J. Comput. Math. (2022) (accepted)","DOI":"10.5802\/smai-jcm.96"},{"key":"1358_CR3","doi-asserted-by":"crossref","unstructured":"Bohn, B.: Error analysis of regularized and unregularized least-squares regression on discretized function spaces. Dissertation, Institut f\u00fcr Numerische Simulation, Universit\u00e4t Bonn (2017)","DOI":"10.1137\/15M1013973"},{"key":"1358_CR4","volume-title":"Sparse Grids and Applications\u2014Miami 2016 Lecture Notes in Computational Science and Engineering","author":"B Bohn","year":"2018","unstructured":"Bohn, B.: On the convergence rate of sparse grid least squares regression. In: Garcke, J., Pfl\u00fcger, D., Webster, C., Zhang, G. (eds.) Sparse Grids and Applications\u2014Miami 2016 Lecture Notes in Computational Science and Engineering, vol. 123. Springer, Cham (2018)"},{"issue":"4","key":"1358_CR5","doi-asserted-by":"publisher","first-page":"1843","DOI":"10.1137\/15M1013973","volume":"55","author":"B Bohn","year":"2017","unstructured":"Bohn, B., Griebel, M.: Error estimates for multivariate regression on discretized function spaces. SIAM J. Numer. Anal. 55(4), 1843\u20131866 (2017)","journal-title":"SIAM J. Numer. Anal."},{"key":"1358_CR6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1017\/S0962492904000182","volume":"13","author":"H-J Bungartz","year":"2004","unstructured":"Bungartz, H.-J., Griebel, M.: Sparse grids. Acta Numer. 13, 147\u2013269 (2004)","journal-title":"Acta Numer."},{"issue":"1","key":"1358_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.21314\/JCF.1997.005","volume":"1","author":"R Caflisch","year":"1997","unstructured":"Caflisch, R., Morokoff, W., Owen, A.: Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension. J. Comput. Finance 1(1), 27\u201346 (1997)","journal-title":"J. Comput. Finance"},{"issue":"3","key":"1358_CR8","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1051\/m2an\/2014050","volume":"49","author":"A Chkifa","year":"2015","unstructured":"Chkifa, A., Cohen, A., Migliorati, G., Nobile, F., Tempone, R.: Discrete least squares polynomial approximation with random evaluations\u2014application to parametric and stochastic elliptic PDEs. ESAIM: M2AN 49(3), 815\u2013837 (2015)","journal-title":"ESAIM: M2AN"},{"key":"1358_CR9","volume-title":"An Introduction to Wavelets","author":"CK Chui","year":"1992","unstructured":"Chui, C.K.: An Introduction to Wavelets. Academic Press, Boston (1992)"},{"key":"1358_CR10","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s10208-013-9142-3","volume":"13","author":"A Cohen","year":"2013","unstructured":"Cohen, A., Davenport, M.A., Dany, L.: On the stability and accuracy of least-squares approximations. Found. Comput. Math. 13, 819\u2013834 (2013)","journal-title":"Found. Comput. Math."},{"key":"1358_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101602","volume":"68","author":"A Cohen","year":"2022","unstructured":"Cohen, A., Dolbeault, M.: Optimal pointwise sampling for $$L^2$$ approximation. J. Complex. 68, 101602 (2022)","journal-title":"J. Complex."},{"key":"1358_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.5802\/smai-jcm.24","volume":"3","author":"A Cohen","year":"2017","unstructured":"Cohen, A., Migliorati, G.: Optimal weighted least-squares methods. SMAI J. Comput. Math. 3, 181\u2013203 (2017)","journal-title":"SMAI J. Comput. Math."},{"key":"1358_CR13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970104","volume-title":"Ten Lectures on Wavelets","author":"I Daubechies","year":"1992","unstructured":"Daubechies, I.: Ten Lectures on Wavelets. SIAM, Philadelphia, PA, USA (1992)"},{"key":"1358_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s003659900060","volume":"14","author":"R DeVore","year":"1998","unstructured":"DeVore, R., Konyagin, S., Temlyakov, V.: Hyperbolic wavelet approximation. Constr. Approx. 14, 1\u201326 (1998)","journal-title":"Constr. Approx."},{"issue":"1","key":"1358_CR15","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00365-010-9105-8","volume":"33","author":"R DeVore","year":"2010","unstructured":"DeVore, R., Petrova, G., Wojtaszczyk, P.: Approximation of functions of few variables in high dimensions. Constr. Approx. 33(1), 125\u2013143 (2010)","journal-title":"Constr. Approx."},{"key":"1358_CR16","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1007\/s10208-013-9149-9","volume":"13","author":"D Dung","year":"2013","unstructured":"Dung, D., Ullrich, T.: N-widths and $$\\epsilon $$-dimensions for high-dimensional approximations. Found. Comput. Math. 13, 965\u20131003 (2013)","journal-title":"Found. Comput. Math."},{"key":"1358_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.jmva.2012.08.016","volume":"115","author":"N Durrande","year":"2013","unstructured":"Durrande, N., Ginsbourger, D., Roustant, O., Carraro, L.: ANOVA kernels and RKHS of zero mean functions for model-based sensitivity analysis. J. Multivar. Anal. 115, 57\u201367 (2013)","journal-title":"J. Multivar. Anal."},{"key":"1358_CR18","doi-asserted-by":"crossref","unstructured":"D\u0169ng, D., Temlyakov, V.N., Ullrich, T.: Hyperbolic cross approximation. In: Advanced Courses in Mathematics\u2014CRM Barcelona. Birkh\u00e4user, Cham (2018)","DOI":"10.1007\/978-3-319-92240-9"},{"key":"1358_CR19","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-642-31703-3","volume-title":"Sparse Grids and Applications","author":"J Garcke","year":"2013","unstructured":"Garcke, J.: Sparse grids in a nutshell. In: Garcke, J., Griebel, M. (eds.) Sparse Grids and Applications, pp. 57\u201380. Springer, Berlin (2013)"},{"key":"1358_CR20","unstructured":"Krieg, D., Pozharska, K., Ullrich, M., Ullrich, T.: ISampling recovery in the uniform norm. ArXiv e-prints 2305.07539 (2023)"},{"key":"1358_CR21","unstructured":"Grez, G.A.S., Vidakovic, B.: Least squares wavelet-based estimation for additive regression models using non equally-spaced designs (2018)"},{"key":"1358_CR22","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s003650010010","volume":"16","author":"M Griebel","year":"2000","unstructured":"Griebel, M., Knapek, S.: Optimized tensor-product approximation spaces. Constr. Approx. 16, 525\u2013540 (2000)","journal-title":"Constr. Approx."},{"issue":"5","key":"1358_CR23","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1016\/j.jco.2010.04.003","volume":"26","author":"M Griebel","year":"2010","unstructured":"Griebel, M., Kuo, F.Y., Sloan, I.H.: The smoothing effect of the ANOVA decomposition. J. Complex. 26(5), 523\u2013551 (2010)","journal-title":"J. Complex."},{"issue":"2","key":"1358_CR24","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s002110050450","volume":"83","author":"M Griebel","year":"1999","unstructured":"Griebel, M., Oswald, P., Schiekofer, T.: Sparse grids for boundary integral equations. Numer. Math. 83(2), 279\u2013312 (1999)","journal-title":"Numer. Math."},{"key":"1358_CR25","volume-title":"Sparse Grid Quadrature in High Dimensions with Applications in Finance and Insurance. Lecture Notes in Computational Science and Engineering","author":"M Holtz","year":"2011","unstructured":"Holtz, M.: Sparse Grid Quadrature in High Dimensions with Applications in Finance and Insurance. Lecture Notes in Computational Science and Engineering, vol. 77. Springer, Berlin (2011)"},{"key":"1358_CR26","doi-asserted-by":"crossref","unstructured":"Ishigami, T., Homma, T.: An importance quantification technique in uncertainty analysis for computer models. In: Proceedings. First International Symposium on Uncertainty Modeling and Analysis, pp. 398\u2013403 (1990)","DOI":"10.1109\/ISUMA.1990.151285"},{"key":"1358_CR27","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00365-021-09555-0","volume":"54","author":"L K\u00e4mmerer","year":"2021","unstructured":"K\u00e4mmerer, L., Ullrich, T., Volkmer, T.: Worst case recovery guarantees for least squares approximation using random samples. Constr. Approx. 54, 295\u2013352 (2021)","journal-title":"Constr. Approx."},{"key":"1358_CR28","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.jco.2013.07.001","volume":"30","author":"T K\u00fchn","year":"2014","unstructured":"K\u00fchn, T., Sickel, W., Ullrich, T.: Approximation numbers of Sobolev embeddings\u2014sharp constants and tractability. J. Complex. 30, 95\u2013116 (2014)","journal-title":"J. Complex."},{"issue":"270","key":"1358_CR29","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1090\/S0025-5718-09-02319-9","volume":"79","author":"FY Kuo","year":"2009","unstructured":"Kuo, F.Y., Sloan, I.H., Wasilkowski, G.W., Wo\u017aniakowski, H.: On decompositions of multivariate functions. Math. Comput. 79(270), 953\u2013966 (2009)","journal-title":"Math. Comput."},{"issue":"474","key":"1358_CR30","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1198\/016214505000001410","volume":"101","author":"R Liu","year":"2006","unstructured":"Liu, R., Owen, A.B.: Estimating mean dimensionality of analysis of variance decompositions. J. Am. Stat. Assoc. 101(474), 712\u2013721 (2006)","journal-title":"J. Am. Stat. Assoc."},{"key":"1358_CR31","doi-asserted-by":"publisher","DOI":"10.4171\/026","volume-title":"Tractability of Multivariate Problems Volume I: Linear Information. EMS Tracts in Mathematics","author":"E Novak","year":"2008","unstructured":"Novak, E., Wo\u017aniakowski, H.: Tractability of Multivariate Problems Volume I: Linear Information. EMS Tracts in Mathematics, vol. 6. European Mathematical Society, Zurich (2008)"},{"key":"1358_CR32","doi-asserted-by":"publisher","DOI":"10.4171\/084","volume-title":"Tractability of Multivariate Problems Volume II: Standard Information for Functionals. EMS Tracts in Mathematics","author":"E Novak","year":"2010","unstructured":"Novak, E., Wo\u017aniakowski, H.: Tractability of Multivariate Problems Volume II: Standard Information for Functionals. EMS Tracts in Mathematics, vol. 12. European Mathematical Society, Zurich (2010)"},{"key":"1358_CR33","doi-asserted-by":"publisher","DOI":"10.4171\/116","volume-title":"Tractability of Multivariate Problems Volume III: Standard Information for Operators. EMS Tracts in Mathematics","author":"E Novak","year":"2012","unstructured":"Novak, E., Wo\u017aniakowski, H.: Tractability of Multivariate Problems Volume III: Standard Information for Operators. EMS Tracts in Mathematics, vol. 18. European Mathematical Society, Zurich (2012)"},{"key":"1358_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04306-3","volume-title":"Numerical Fourier Analysis. Applied and Numerical Harmonic Analysis","author":"G Plonka","year":"2018","unstructured":"Plonka, G., Potts, D., Steidl, G., Tasche, M.: Numerical Fourier Analysis. Applied and Numerical Harmonic Analysis. Birkh\u00e4user, Boston (2018)"},{"key":"1358_CR35","first-page":"137","volume-title":"Wavelets: Theory, Algorithms, and Applications","author":"G Plonka","year":"1994","unstructured":"Plonka, G., Tasche, M.: A unified approach to periodic wavelets. In: Chui, C.K., Montefusco, L., Puccio, L. (eds.) Wavelets: Theory, Algorithms, and Applications, pp. 137\u2013151. Academic Press, San Diego (1994)"},{"issue":"5","key":"1358_CR36","doi-asserted-by":"publisher","first-page":"2393","DOI":"10.1137\/20M1354921","volume":"59","author":"D Potts","year":"2021","unstructured":"Potts, D., Schmischke, M.: Approximation of high-dimensional periodic functions with Fourier-based methods. SIAM J. Numer. Anal. 59(5), 2393\u20132429 (2021)","journal-title":"SIAM J. Numer. Anal."},{"issue":"4","key":"1358_CR37","doi-asserted-by":"publisher","first-page":"1301","DOI":"10.1137\/21M1407707","volume":"3","author":"D Potts","year":"2021","unstructured":"Potts, D., Schmischke, M.: Interpretable approximation of high-dimensional data. SIAM J. Math. Data Sci. 3(4), 1301\u20131323 (2021)","journal-title":"SIAM J. Math. Data Sci."},{"issue":"3","key":"1358_CR38","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1137\/21M1410580","volume":"60","author":"K Pozharska","year":"2022","unstructured":"Pozharska, K., Ullrich, T.: A note on sampling recovery of multivariate functions in the uniform norm. SIAM J. Numer. Anal. 60(3), 1363\u20131384 (2022)","journal-title":"SIAM J. Numer. Anal."},{"issue":"2","key":"1358_CR39","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1016\/j.jat.2009.01.001","volume":"161","author":"W Sickel","year":"2009","unstructured":"Sickel, W., Ullrich, T.: Tensor products of Sobolev\u2013Besov spaces and applications to approximation from the hyperbolic cross. J. Approx. Theory 161(2), 748\u2013786 (2009)","journal-title":"J. Approx. Theory"},{"issue":"1\u20133","key":"1358_CR40","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0378-4754(00)00270-6","volume":"55","author":"IM Sobol","year":"2001","unstructured":"Sobol, I.M.: Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates. Math. Comput. Simul. 55(1\u20133), 271\u2013280 (2001)","journal-title":"Math. Comput. Simul."},{"key":"1358_CR41","volume-title":"Support Vector Machines","author":"I Steinwart","year":"2008","unstructured":"Steinwart, I., Christmann, A.: Support Vector Machines, 1st edn. Springer, Cham (2008)","edition":"1"},{"key":"1358_CR42","volume-title":"Approximation of Periodic Functions. Computational Mathematics and Analysis Series","author":"V Temlyakov","year":"1993","unstructured":"Temlyakov, V.: Approximation of Periodic Functions. Computational Mathematics and Analysis Series. Nova Science Publishers Inc., Commack, NY (1993)"},{"key":"1358_CR43","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10208-011-9099-z","volume":"12","author":"J Tropp","year":"2012","unstructured":"Tropp, J.: User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12, 389\u2013434 (2012)","journal-title":"Found. Comput. Math."},{"key":"1358_CR44","volume-title":"Experiments\u2014Planning, Analysis, and Optimization","author":"CFJ Wu","year":"2011","unstructured":"Wu, C.F.J., Hamada, M.S.: Experiments\u2014Planning, Analysis, and Optimization. Wiley, New York (2011)"},{"key":"1358_CR45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12248-4","volume-title":"Regularity and Approximability of Electronic Wave Functions. Lecture Notes in Mathematics","author":"H Yserentant","year":"2010","unstructured":"Yserentant, H.: Regularity and Approximability of Electronic Wave Functions. Lecture Notes in Mathematics. Springer, Berlin (2010)"}],"container-title":["Numerische Mathematik"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-023-01358-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00211-023-01358-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-023-01358-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T22:02:39Z","timestamp":1729634559000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00211-023-01358-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":45,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1358"],"URL":"https:\/\/doi.org\/10.1007\/s00211-023-01358-8","relation":{},"ISSN":["0029-599X","0945-3245"],"issn-type":[{"value":"0029-599X","type":"print"},{"value":"0945-3245","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"3 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}