Fast hyperbolic wavelet regression meets ANOVA

DOI10.1007/S00211-023-01358-8zbMATH Open1528.41030arXiv2108.13197OpenAlexW3196926354MaRDI QIDQ6165230FDOQ6165230

Authors: Laura Lippert, Daniel Potts, Tino Ullrich 

Publication date: 4 July 2023

Published in: Numerische Mathematik (Search for Journal in Brave)

Abstract: We use hyperbolic wavelet regression for the fast reconstruction of high-dimensional functions having only low dimensional variable interactions. Compactly supported periodic Chui-Wang wavelets are used for the tensorized hyperbolic wavelet basis. In a first step we give a self-contained characterization of tensor product Sobolev-Besov spaces on the $d$-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 $log$-terms that do not depend on $d$ 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.

Full work available at URL: https://arxiv.org/abs/2108.13197

Recommendations

• Variable transformations in combination with wavelets and ANOVA for high-dimensional approximation
• Grouped transformations and regularization in high-dimensional explainable ANOVA approximation
• Approximation of high-dimensional periodic functions with Fourier-based methods
• Learning multivariate functions with low-dimensional structures using polynomial bases
• ANOVA approximation with mixed tensor product basis on scattered points

Mathematics Subject Classification ID

Numerical methods for wavelets (65T60) Multidimensional problems (41A63) Inequalities in approximation (Bernstein, Jackson, Nikol'ski?-type inequalities) (41A17) Algorithms for approximation of functions (65D15) Rate of convergence, degree of approximation (41A25)

Cites Work

• Support Vector Machines
• Title not available (Why is that?)
• Ten Lectures on Wavelets
• Tensor products of Sobolev-Besov spaces and applications to approximation from the hyperbolic cross
• Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
• Sparse grids
• Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates
• User-friendly tail bounds for sums of random matrices
• \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations
• Title not available (Why is that?)
• Approximation of functions of few variables in high dimensions
• Iterative Solution Methods
• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Optimized tensor-product approximation spaces
• On the stability and accuracy of least squares approximations
• Regularity and approximability of electronic wave functions
• Approximation numbers of Sobolev embeddings-sharp constants and tractability
• On decompositions of multivariate functions
• Estimating Mean Dimensionality of Analysis of Variance Decompositions
• Sparse grids for boundary integral equations
• Hyperbolic wavelet approximation
• Sparse grids and applications. Selected contributions based on the presentations at the workshop, Bonn, Germany, May 16--20, 2011
• Sparse grid quadrature in high dimensions with applications in finance and insurance
• Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic PDEs
• Approximation of high-dimensional periodic functions with Fourier-based methods
• ANOVA kernels and RKHS of zero mean functions for model-based sensitivity analysis
• Title not available (Why is that?)
• The smoothing effect of the ANOVA decomposition
• Numerical Fourier analysis
• Optimal weighted least-squares methods
• A note on sampling recovery of multivariate functions in the uniform norm
• Interpretable approximation of high-dimensional data
• On the convergence rate of sparse grid least squares regression
• Optimal pointwise sampling for \(L^2\) approximation
• Worst-case recovery guarantees for least squares approximation using random samples
• Experiments: planning, analysis, and optimization
• Error Estimates for Multivariate Regression on Discretized Function Spaces

Cited In (3)

• Variable transformations in combination with wavelets and ANOVA for high-dimensional approximation
• ANOVA approximation with mixed tensor product basis on scattered points
• Sparse additive function decompositions facing basis transforms

This page was built for publication: Fast hyperbolic wavelet regression meets ANOVA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165230)