Grouped Transformations and Regularization in High-Dimensional Explainable ANOVA Approximation

In this paper we propose a tool for high-dimensional approximation based on trigonometric polynomials where we allow only low-dimensional interactions of variables. In a general high-dimensional setting, it is already possible to deal with special sampling sets such as sparse grids or rank-1 lattices. This requires black-box access to the function, i.e., the ability to evaluate it at any point. Here, we focus on scattered data points and grouped frequency index sets along the dimensions. From there we propose a fast matrix-vector multiplication, the grouped Fourier transform, for high-dimensional grouped index sets. Those transformations can be used in the application of the previously introduced method of approximating functions with low superposition dimension based on the analysis of variance (ANOVA) decomposition where there is a one-to-one correspondence from the ANOVA terms to our proposed groups. The method is able to dynamically detect important sets of ANOVA terms in the approximation. In this paper, we consider the involved least-squares problem and add different forms of regularization: classical Tikhonov-regularization, namely, regularized least squares, and the technique of group lasso, which promotes sparsity in the groups. As for the latter, there are no explicit solution formulas, which is why we applied the fast iterative shrinkage-thresholding algorithm to obtain the minimizer. Moreover, we discuss the possibility of incorporating smoothness information into the least-squares problem. Numerical experiments in underdetermined, overdetermined, and noisy settings indicate the applicability of our algorithms. While we consider periodic functions, the idea can be directly generalized to nonperiodic functions as well.