Daniel Potts

Sebastian Neumayer, Daniel Potts, Fabian Taubert

We investigate the approximation of solution operators for partial differential equations (PDEs) using sparse high-dimensional techniques. Building on a dimension-incremental framework, we combine product basis expansions with sparse recovery methods, specifically orthogonal matching pursuit (OMP), to substantially reduce the required sample size compared with a previously considered cubature-based approach. We evaluate the resulting method numerically on several examples, comparing it against both cubature-based sparse approximation and Fourier neural operators in terms of accuracy, runtime, and sample size. The experiments show that our approach considerably reduces the number of required PDE solves relative to its predecessor while maintaining competitive accuracy, particularly when the solution admits a sparse representation in the chosen basis. Furthermore, the recovered sparse index sets yield interpretable insights into the relevant variables and parameter interactions.

Lutz Kämmerer, Daniel Potts, Toni Volkmer

The reconstruction of high-dimensional sparse signals is a challenging task in a wide range of applications. In order to deal with high-dimensional problems, efficient sparse fast Fourier transform algorithms are essential tools. The second and third authors have recently proposed a dimension-incremental approach, which only scales almost linear in the number of required sampling values and almost quadratic in the arithmetic complexity with respect to the spatial dimension $d$. Using reconstructing rank-1 lattices as sampling scheme, the method showed reliable reconstruction results in numerical tests but suffers from relatively large numbers of samples and arithmetic operations. Combining the preferable properties of reconstructing rank-1 lattices with small sample and arithmetic complexities, the first author developed the concept of multiple rank-1 lattices. In this paper, both concepts - dimension-incremental reconstruction and multiple rank-1 lattices - are coupled, which yields a distinctly improved high-dimensional sparse fast Fourier transform. Moreover, the resulting algorithm is analyzed in detail with respect to success probability, number of required samples, and arithmetic complexity. In comparison to single rank-1 lattices, the utilization of multiple rank-1 lattices results in a reduction in the complexities by an almost linear factor with respect to the sparsity. Various numerical tests confirm the theoretical results, the high performance, and the reliability of the proposed method.

Daniel Potts, Laura Weidensager

We propose two algorithms for boosting random Fourier feature models for approximating high-dimensional functions. These methods utilize the classical and generalized analysis of variance (ANOVA) decomposition to learn low-order functions, where there are few interactions between the variables. Our algorithms are able to find an index set of important input variables and variable interactions reliably. Furthermore, we generalize already existing random Fourier feature models to an ANOVA setting, where terms of different order can be used. Our algorithms have the advantage of interpretability, meaning that the influence of every input variable is known in the learned model, even for dependent input variables. We give theoretical as well as numerical results that our algorithms perform well for sensitivity analysis. The ANOVA-boosting step reduces the approximation error of existing methods significantly.

Kseniya Akhalaya, Franziska Nestler, Daniel Potts

Support Vector Machines (SVMs) are an important tool for performing classification on scattered data, where one usually has to deal with many data points in high-dimensional spaces. We propose solving SVMs in primal form using feature maps based on trigonometric functions or wavelets. In small dimensional settings the Fast Fourier Transform (FFT) and related methods are a powerful tool in order to deal with the considered basis functions. For growing dimensions the classical FFT-based methods become inefficient due to the curse of dimensionality. Therefore, we restrict ourselves to multivariate basis functions, each of which only depends on a small number of dimensions. This is motivated by the well-known sparsity of effects and recent results regarding the reconstruction of functions from scattered data in terms of truncated analysis of variance (ANOVA) decompositions, which makes the resulting model even interpretable in terms of importance of the features as well as their couplings. The usage of small superposition dimensions has the consequence that the computational effort no longer grows exponentially but only polynomially with respect to the dimension. In order to enforce sparsity regarding the basis coefficients, we use the frequently applied $\ell_2$-norm and, in addition, $\ell_1$-norm regularization. The found classifying function, which is the linear combination of basis functions, and its variance can then be analyzed in terms of the classical ANOVA decomposition of functions. Based on numerical examples we show that we are able to recover the signum of a function that perfectly fits our model assumptions. Furthermore, we perform classification on different artificial and real-world data sets. We obtain better results with $\ell_1$-norm regularization, both in terms of accuracy and clarity of interpretability.

Daniel Potts, Michael Schmischke

The distribution of data points is a key component in machine learning. In most cases, one uses min-max normalization to obtain nodes in $[0,1]$ or Z-score normalization for standard normal distributed data. In this paper, we apply transformation ideas in order to design a complete orthonormal system in the $\mathrm{L}_2$ space of functions with the standard normal distribution as integration weight. Subsequently, we are able to apply the explainable ANOVA approximation for this basis and use Z-score transformed data in the method. We demonstrate the applicability of this procedure on the well-known forest fires data set from the UCI machine learning repository. The attribute ranking obtained from the ANOVA approximation provides us with crucial information about which variables in the data set are the most important for the detection of fires.

Daniel Potts, Michael Schmischke

In this paper we apply the previously introduced approximation method based on the ANOVA (analysis of variance) decomposition and Grouped Transformations to synthetic and real data. The advantage of this method is the interpretability of the approximation, i.e., the ability to rank the importance of the attribute interactions or the variable couplings. Moreover, we are able to generate an attribute ranking to identify unimportant variables and reduce the dimensionality of the problem. We compare the method to other approaches on publicly available benchmark datasets.

Melanie Kircheis, Daniel Potts

Various applications such as MRI, solution of PDEs, etc. need to perform an inverse nonequispaced fast Fourier transform (NFFT), i. e., compute $M$ Fourier coefficients from given $N$ nonequispaced data. In the present paper we consider direct methods for the inversion of the NFFT. We introduce algorithms for the setting $M=N$ as well as for the underdetermined and overdetermined cases. For the setting $M=N$ a direct method of complexity $\mathcal O(N\log N)$ is presented which utilizes Lagrange interpolation and the fast summation. For the remaining cases, we use the matrix representation of the NFFT to deduce our algorithms. Thereby, we are able to compute an inverse NFFT up to a certain accuracy by dint of a modified adjoint NFFT in $\mathcal O(M\log M+N)$ arithmetic operations. Finally, we show that these approaches can also be explained by means of frame approximation.

Dominik Alfke, Daniel Potts, Martin Stoll et al.

The graph Laplacian is a standard tool in data science, machine learning, and image processing. The corresponding matrix inherits the complex structure of the underlying network and is in certain applications densely populated. This makes computations, in particular matrix-vector products, with the graph Laplacian a hard task. A typical application is the computation of a number of its eigenvalues and eigenvectors. Standard methods become infeasible as the number of nodes in the graph is too large. We propose the use of the fast summation based on the nonequispaced fast Fourier transform (NFFT) to perform the dense matrix-vector product with the graph Laplacian fast without ever forming the whole matrix. The enormous flexibility of the NFFT algorithm allows us to embed the accelerated multiplication into Lanczos-based eigenvalues routines or iterative linear system solvers and even consider other than the standard Gaussian kernels. We illustrate the feasibility of our approach on a number of test problems from image segmentation to semi-supervised learning based on graph-based PDEs. In particular, we compare our approach with the Nyström method. Moreover, we present and test an enhanced, hybrid version of the Nyström method, which internally uses the NFFT.

Ralf Hielscher, Daniel Potts, Michael Quellmalz

In spherical surface wave tomography, one measures the integrals of a function defined on the sphere along great circle arcs. This forms a generalization of the Funk--Radon transform, which assigns to a function its integrals along full great circles. We show a singular value decomposition (SVD) for the surface wave tomography provided we have full data. Since the inversion problem is overdetermined, we consider some special cases in which we only know the integrals along certain arcs. For the case of great circle arcs with fixed opening angle, we also obtain an SVD that implies the injectivity, generalizing a previous result for half circles in [Groemer, On a spherical integral transform and sections of star bodies, Monatsh. Math., 126(2):117--124, 1998]. Furthermore, we derive a numerical algorithm based on the SVD and illustrate its merchantability by numerical tests.

Stefan Kunis, Daniel Potts

A fast and reliable algorithm for the optimal interpolation of scattered data on the torus by multivariate trigonometric polynomials is presented. The algorithm is based on a variant of the conjugate gradient method in combination with the fast Fourier transforms for nonequispaced nodes. The main result is that under mild assumptions the total complexity for solving the interpolation problem at M arbitrary nodes is of order O(M logM). This result is obtained by the use of localised trigonometric kernels where the localisation is chosen in accordance to the spatial dimension d. Numerical examples show the efficiency of the new algorithm.