Search

This paper discusses the error and cost aspects of ill-posed integral equations when given discrete noisy point evaluations on a fine grid. Standard solution methods usually employ discretization schemes that are directly induced by the measurement points. Thus, they may scale unfavorably with the number of evaluation points, which can result in computational inefficiency. To address this issue, we propose an algorithm that achieves the same level of accuracy while significantly reducing computational costs. Our approach involves an initial averaging procedure to sparsify the underlying grid. To keep the exposition simple, we focus only on one-dimensional ill-posed integral equations that have sufficient smoothness. However, the approach can be generalized to more complicated two- and three-dimensional problems with appropriate modifications., Comment: 38 pages

We consider the problem of approximating the regression function from noisy vector-valued data by an online learning algorithm using an appropriate reproducing kernel Hilbert space (RKHS) as prior. In an online algorithm, i.i.d. samples become available one by one by a random process and are successively processed to build approximations to the regression function. We are interested in the asymptotic performance of such online approximation algorithms and show that the expected squared error in the RKHS norm can be bounded by $C^2 (m+1)^{-s/(2+s)}$, where $m$ is the current number of processed data, the parameter $0

We present an adaptive algorithm for the computation of quantities of interest involving the solution of a stochastic elliptic PDE where the diffusion coefficient is parametrized by means of a Karhunen-Lo\`eve expansion. The approximation of the equivalent parametric problem requires a restriction of the countably infinite-dimensional parameter space to a finite-dimensional parameter set, a spatial discretization and an approximation in the parametric variables. We consider a sparse grid approach between these approximation directions in order to reduce the computational effort and propose a dimension-adaptive combination technique. In addition, a sparse grid quadrature for the high-dimensional parametric approximation is employed and simultaneously balanced with the spatial and stochastic approximation. Our adaptive algorithm constructs a sparse grid approximation based on the benefit-cost ratio such that the regularity and thus the decay of the Karhunen-Lo\`eve coefficients is not required beforehand. The decay is detected and exploited as the algorithm adjusts to the anisotropy in the parametric variables. We include numerical examples for the Darcy problem with a lognormal permeability field, which illustrate a good performance of the algorithm: For sufficiently smooth random fields, we essentially recover the spatial order of convergence as asymptotic convergence rate with respect to the computational cost., Comment: 29 pages, 7 figures

Let $\Omega_i\subset\mathbb{R}^{n_i}$, $i=1,\ldots,m$, be given domains. In this article, we study the low-rank approximation with respect to $L^2(\Omega_1\times\dots\times\Omega_m)$ of functions from Sobolev spaces with dominating mixed smoothness. To this end, we first estimate the rank of a bivariate approximation, i.e., the rank of the continuous singular value decomposition. In comparison to the case of functions from Sobolev spaces with isotropic smoothness, compare \cite{GH14,GH19}, we obtain improved results due to the additional mixed smoothness. This convergence result is then used to study the tensor train decomposition as a method to construct multivariate low-rank approximations of functions from Sobolev spaces with dominating mixed smoothness. We show that this approach is able to beat the curse of dimension.

Many physical and mathematical models involve random fields in their input data. Examples are ordinary differential equations, partial differential equations and integro--differential equations with uncertainties in the coefficient functions described by random fields. They also play a dominant role in problems in machine learning. In this article, we do not assume to have knowledge of the moments or expansion terms of the random fields but we instead have only given discretized samples for them. We thus model some measurement process for this discrete information and then approximate the covariance operator of the original random field. Of course, the true covariance operator is of infinite rank and hence we can not assume to get an accurate approximation from a finite number of spatially discretized observations. On the other hand, smoothness of the true (unknown) covariance function results in effective low rank approximations to the true covariance operator. We derive explicit error estimates that involve the finite rank approximation error of the covariance operator, the Monte-Carlo-type errors for sampling in the stochastic domain and the numerical discretization error in the physical domain. This permits to give sufficient conditions on the three discretization parameters to guarantee that an error below a prescribed accuracy $\varepsilon$ is achieved., Comment: 40 pages

In this paper we present an algebraic dimension-oblivious two-level domain decomposition solver for discretizations of elliptic partial differential equations. The proposed parallel solver is based on a space-filling curve partitioning approach that is applicable to any discretization, i.e. it directly operates on the assembled matrix equations. Moreover, it allows for the effective use of arbitrary processor numbers independent of the dimension of the underlying partial differential equation while maintaining optimal convergence behavior. This is the core property required to attain a sparse grid based combination method with extreme scalability which can utilize exascale parallel systems efficiently. Moreover, this approach provides a basis for the development of a fault-tolerant solver for the numerical treatment of high-dimensional problems. To achieve the required data redundancy we are therefore concerned with large overlaps of our domain decomposition which we construct via space-filling curves. In this paper, we propose our space-filling curve based domain decomposition solver and present its convergence properties and scaling behavior. The results of numerical experiments clearly show that our approach provides optimal convergence and scaling behavior in arbitrary dimension utilizing arbitrary processor numbers., Comment: 28 pages, 11 figures, 1 table. arXiv admin note: substantial text overlap with arXiv:2103.03315

In this paper, we propose neural networks that tackle the problems of stability and field-of-view of a Convolutional Neural Network (CNN). As an alternative to increasing the network's depth or width to improve performance, we propose integral-based spatially nonlocal operators which are related to global weighted Laplacian, fractional Laplacian and inverse fractional Laplacian operators that arise in several problems in the physical sciences. The forward propagation of such networks is inspired by partial integro-differential equations (PIDEs). We test the effectiveness of the proposed neural architectures on benchmark image classification datasets and semantic segmentation tasks in autonomous driving. Moreover, we investigate the extra computational costs of these dense operators and the stability of forward propagation of the proposed neural networks.

We propose a simple domain decomposition method for $d$-dimensional elliptic PDEs which involves an overlapping decomposition into local subdomain problems and a global coarse problem. It relies on a space-filling curve to create equally sized subproblems and to determine a certain overlap based on the one-dimensional ordering of the space-filling curve. Furthermore we employ agglomeration and a purely algebraic Galerkin discretization in the construction of the coarse problem. This way, the use of $d$-dimensional geometric information is avoided. The subproblems are dealt with in an additive, parallel way, which gives rise to a subspace correction type linear iteration and a preconditioner for the conjugate gradient method. To make the algorithm fault-tolerant we store on each processor, besides the data of the associated subproblem, a copy of the coarse problem and also the data of a fixed amount of neighboring subproblems with respect to the one-dimensional ordering of the subproblems induced by the space-filling curve. This redundancy then allows to restore the necessary data if processors fail during the computation. Theory supports that the convergence rate of such a linear iteration method stays the same in expectation, and only its order constant deteriorates slightly due to the faults. We observe this in numerical experiments for the preconditioned conjugate gradient method in slightly weaker form as well. Altogether, we obtain a fault-tolerant, parallel and efficient domain decomposition method based on space-filling curves which is especially suited for higher-dimensional elliptic problems., Comment: 61 pages, 26 figures

Generalized Method of Moments (GMM) estimators in their various forms, including the popular Maximum Likelihood (ML) estimator, are frequently applied for the evaluation of complex econometric models with not analytically computable moment or likelihood functions. As the objective functions of GMM- and ML-estimators themselves constitute the approximation of an integral, more precisely of the expected value over the real world data space, the question arises whether the approximation of the moment function and the simulation of the entire objective function can be combined. Motivated by the popular Probit and Mixed Logit models, we consider double integrals with a linking function which stems from the considered estimator, e.g. the logarithm for Maximum Likelihood, and apply a sparse tensor product quadrature to reduce the computational effort for the approximation of the combined integral. Given H\"older continuity of the linking function, we prove that this approach can improve the order of the convergence rate of the classical GMM- and ML-estimator by a factor of two, even for integrands of low regularity or high dimensionality. This result is illustrated by numerical simulations of Mixed Logit and Multinomial Probit integrals which are estimated by ML- and GMM-estimators, respectively., Comment: 33 pages, 4 tables, 4 figures

Empirical economic research frequently applies maximum likelihood estimation in cases where the likelihood function is analytically intractable. Most of the theoretical literature focuses on maximum simulated likelihood (MSL) estimators, while empirical and simulation analyzes often find that alternative approximation methods such as quasi-Monte Carlo simulation, Gaussian quadrature, and integration on sparse grids behave considerably better numerically. This paper generalizes the theoretical results widely known for MSL estimators to a general set of maximum approximated likelihood (MAL) estimators. We provide general conditions for both the model and the approximation approach to ensure consistency and asymptotic normality. We also show specific examples and finite-sample simulation results.

The Karhunen-Lo\`{e}ve (KL) expansion is a popular method for approximating random fields by transforming an infinite-dimensional stochastic domain into a finite-dimensional parameter space. Its numerical approximation is of central importance to the study of PDEs with random coefficients. In this work, we analyze the approximation error of the Karhunen-Lo\`eve expansion for lognormal random fields. We derive error estimates that allow the optimal balancing of the truncation error of the expansion, the Quasi Monte-Carlo error for sampling in the stochastic domain and the numerical approximation error in the physical domain. The estimate is given in the number $M$ of terms maintained in the KL expansion, in the number of sampling points $N$, and in the discretization mesh size $h$ in the physical domain employed in the numerical solution of the eigenvalue problems during the expansion. The result is used to quantify the error in PDEs with random coefficients. We complete the theoretical analysis with numerical experiments in one and multiple stochastic dimensions.

In this article, we analyze tensor approximation schemes for continuous functions. We assume that the function to be approximated lies in an isotropic Sobolev space and discuss the cost when approximating this function in the continuous analogue of the Tucker tensor format or of the tensor train format. We especially show that the cost of both approximations are dimension-robust when the Sobolev space under consideration provides appropriate weights.

In this work, we apply stochastic collocation methods with radial kernel basis functions for an uncertainty quantification of the random incompressible two-phase Navier-Stokes equations. Our approach is non-intrusive and we use the existing fluid dynamics solver NaSt3DGPF to solve the incompressible two-phase Navier-Stokes equation for each given realization. We are able to empirically show that the resulting kernel-based stochastic collocation is highly competitive in this setting and even outperforms some other standard methods.

For low-dimensional data sets with a large amount of data points, standard kernel methods are usually not feasible for regression anymore. Besides simple linear models or involved heuristic deep learning models, grid-based discretizations of larger (kernel) model classes lead to algorithms, which naturally scale linearly in the amount of data points. For moderate-dimensional or high-dimensional regression tasks, these grid-based discretizations suffer from the curse of dimensionality. Here, sparse grid methods have proven to circumvent this problem to a large extent. In this context, space- and dimension-adaptive sparse grids, which can detect and exploit a given low effective dimensionality of nominally high-dimensional data, are particularly successful. They nevertheless rely on an axis-aligned structure of the solution and exhibit issues for data with predominantly skewed and rotated coordinates. In this paper we propose a preprocessing approach for these adaptive sparse grid algorithms that determines an optimized, problem-dependent coordinate system and, thus, reduces the effective dimensionality of a given data set in the ANOVA sense. We provide numerical examples on synthetic data as well as real-world data to show how an adaptive sparse grid least squares algorithm benefits from our preprocessing method.

We present convergence results in expectation for stochastic subspace correction schemes and their accelerated versions to solve symmetric positive-definite variational problems, and discuss their potential for achieving fault tolerance in an unreliable compute network. We employ the standard overlapping domain decomposition algorithm for PDE discretizations to discuss the latter aspect., Comment: 33 pages, 6 figures

We consider an incremental approximation method for solving variational problems in infinite-dimensional Hilbert spaces, where in each step a randomly and independently selected subproblem from an infinite collection of subproblems is solved. we show that convergence rates for the expectation of the squared error can be guaranteed under weaker conditions than previously established in [Constr. Approx. 44:1 (2016), 121-139]. A connection to the theory of learning algorithms in reproducing kernel Hilbert spaces is revealed., Comment: 15 pages

In this paper we provide a finite-sample and an infinite-sample representer theorem for the concatenation of (linear combinations of) kernel functions of reproducing kernel Hilbert spaces. These results serve as mathematical foundation for the analysis of machine learning algorithms based on compositions of functions. As a direct consequence in the finite-sample case, the corresponding infinite-dimensional minimization problems can be recast into (nonlinear) finite-dimensional minimization problems, which can be tackled with nonlinear optimization algorithms. Moreover, we show how concatenated machine learning problems can be reformulated as neural networks and how our representer theorem applies to a broad class of state-of-the-art deep learning methods.

It is known that the Brownian bridge or L\'evy-Ciesielski construction of Brownian paths almost surely converges uniformly to the true Brownian path. In the present article the focus is on the uniform error. In particular, we show constructively that at level $N$, at which there are $d=2^N$ points evaluated on the Brownian path, the uniform error and its square, and the uniform error of geometric Brownian motion, have upper bounds of order $\mathcal{O}(\sqrt{\ln d/d})$, matching the known orders. We apply the results to an option pricing example.

In this article, we present a cost-benefit analysis of the approximation in tensor products of Hilbert spaces of Sobolev-analytic type. The Sobolev part is defined on a finite dimensional domain, whereas the analytical space is defined on an infinite dimensional domain. As main mathematical tool, we use the $\varepsilon$-dimension of a subset in a Hilbert space. The $\varepsilon$-dimension gives the lowest number of linear information that is needed to approximate an element from the set in the norm of the Hilbert space up to an accuracy $\varepsilon>0$. From a practical point of view this means that we a priori fix an accuracy and ask for the amount of information to achieve this accuracy. Such an analysis usually requires sharp estimates on the cardinality of certain index sets which are in our case infinite-dimensional hyperbolic crosses. As main result, we obtain sharp bounds of the $\varepsilon$-dimension of the Sobolev-analytic-type function classes which depend only on the smoothness differences in the Sobolev spaces and the dimension of the finite dimensional domain where these spaces are defined. This implies in particular that, up to constants, the costs of the infinite dimensional (analytical) approximation problem is dominated by the finite-variate Sobolev approximation problem. We demonstrate this procedure with an examples of functions spaces stemming from the regularity theory of parametric partial differential equation.

In this paper, we introduce a new scheme for the efficient numerical treatment of the electronic Schr\"odinger equation for molecules. It is based on the combination of a many-body expansion, which corresponds to the so-called bond order dissection Anova approach, with a hierarchy of basis sets of increasing order. Here, the energy is represented as a finite sum of contributions associated to subsets of nuclei and basis sets in a telescoping sum like fashion. Under the assumption of data locality of the electronic density (nearsightedness of electronic matter), the terms of this expansion decay rapidly and higher terms may be neglected. We further extend the approach in a dimension-adaptive fashion to generate quasi-optimal approximations, i.e. a specific truncation of the hierarchical series such that the total benefit is maximized for a fixed amount of costs. This way, we are able to achieve substantial speed up factors compared to conventional first principles methods depending on the molecular system under consideration. In particular, the method can deal efficiently with molecular systems which include only a small active part that needs to be described by accurate but expensive models.

We present an approach to defining Hilbert spaces of functions depending on infinitely many variables or parameters, with emphasis on a weighted tensor product construction based on stable space splittings, The construction has been used in an exemplary way for guiding dimension- and scale-adaptive algorithms in application areas such as statistical learning theory, reduced order modeling, and information-based complexity. We prove results on compact embeddings, norm equivalences, and the estimation of $epsilon$-dimensions. A new condition for the equivalence of weighted ANOVA and anchored norms is also given., Comment: 35 pages

Multilevel quadrature methods for parametric operator equations such as the multilevel (quasi-) Monte Carlo method are closely related to the sparse tensor product approximation between the spatial variable and the parameter. In this article, we employ this fact and reverse the multilevel quadrature method via the sparse grid construction by applying differences of quadrature rules to finite element discretizations of increasing resolution. Besides being algorithmically more efficient if the underlying quadrature rules are nested, this way of performing the sparse tensor product approximation enables the easy use of non-nested and even adaptively refined finite element meshes. Especially, we present a rigorous error and regularity analysis of the fully discrete solution, taking into account the effect of polygonal approximations to a curved physical domain and the numerical approximation of the bilinear form. Our results facilitate the construction of efficient multilevel quadrature methods based on deterministic quadrature rules. Numerical results in three spatial dimensions are provided to illustrate the approach.

We give tight upper and lower bounds of the cardinality of the index sets of certain hyperbolic crosses which reflect mixed Sobolev-Korobov-type smoothness and mixed Sobolev-analytic-type smoothness in the infinite-dimensional case where specific summability properties of the smoothness indices are fulfilled. These estimates are then applied to the linear approximation of functions from the associated spaces in terms of the $\varepsilon$-dimension of their unit balls. Here, the approximation is based on linear information. Such function spaces appear for example for the solution of parametric and stochastic PDEs. The obtained upper and lower bounds of the approximation error as well as of the associated $\varepsilon$-complexities are completely independent of any dimension. Moreover, the rates are independent of the parameters which define the smoothness properties of the infinite-variate parametric or stochastic part of the solution. These parameters are only contained in the order constants. This way, linear approximation theory becomes possible in the infinite-dimensional case and corresponding infinite-dimensional problems get tractable.

We prove the convergence of greedy and randomized versions of Schwarz iterative methods for solving linear elliptic variational problems based on infinite space splittings of a Hilbert space. For the greedy case, we show a squared error decay rate of $O((m+1)^{-1})$ for elements of an approximation space $\mathcal{A}_1$ related to the underlying splitting. For the randomized case, we show an expected squared error decay rate of $O((m+1)^{-1})$ on a class $\mathcal{A}_{\infty}^{\pi}\subset \mathcal{A}_1$ depending on the probability distribution., Comment: Revised version, accepted in Constr. Approx