  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 detected 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
shrinking-thresholding algorithm to obtain the minimizer. Moreover, we discuss
the possibility of incorporating smoothness information into the least-squares
problem. Numerical experiments in under-, overdetermined, and noisy settings
indicate the applicability of our algorithms. While we consider periodic
functions, the idea can be directly generalized to non-periodic functions as
well.
