Apr 27 2017

math.NA arXiv:1704.08213v1

In this dissertation we study the tractability of the information-based complexity $n(\varepsilon,d)$ for $d$-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $d$. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the $L_{\infty}$-approximation of certain classes of $C^{\infty}$-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the $L_{\infty}$-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the $L_1$-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $\sqrt{d}$ only.

Optimal transportation provides a means of lifting distances between points on a geometric domain to distances between signals over the domain, expressed as probability distributions. On a graph, transportation problems can be used to express challenging tasks involving matching supply to demand with minimal shipment expense; in discrete language, these become minimum-cost network flow problems. Regularization typically is needed to ensure uniqueness for the linear ground distance case and to improve optimization convergence; state-of-the-art techniques employ entropic regularization on the transportation matrix. In this paper, we explore a quadratic alternative to entropic regularization for transport over a graph. We theoretically analyze the behavior of quadratically-regularized graph transport, characterizing how regularization affects the structure of flows in the regime of small but nonzero regularization. We further exploit elegant second-order structure in the dual of this problem to derive an easily-implemented Newton-type optimization algorithm.

Apr 27 2017

math.NA arXiv:1704.08128v1

In this paper we extend the application of Hamiltonian Boundary Value Methods (HBVMs), a class of energy-conserving Runge-Kutta methods for Hamiltonian problems, to the numerical solution of Hamiltonian systems with holonomic constraints. The extension is obtained through a straightforward use of the so called line integral approach on which the methods rely, which is here used also for dealing with the constraints. As a result, the modified methods conserve both the Hamiltonian and the constraints, as is shown in their analysis. Some numerical tests are reported, to give evidence of the theoretical findings.

Apr 27 2017

math.NA arXiv:1704.08072v1

We consider the multilinear pagerank problem studied in [Gleich, Lim and Yu, Multilinear Pagerank, 2015], which is a system of quadratic equations with stochasticity and nonnegativity constraints. We use the theory of quadratic vector equations to prove several properties of its solutions and suggest new numerical algorithms. In particular, we prove the existence of a certain minimal solution, which does not always coincide with the stochastic one that is required by the problem. We use an interpretation of the solution as a Perron eigenvector to devise new fixed-point algorithms for its computation, and pair them with a homotopy continuation strategy. The resulting numerical method is more reliable than the existing alternatives, being able to solve a larger number of problems.

Apr 27 2017

math.NA arXiv:1704.08046v1

We study the exponent of the exponential rate of convergence in terms of the number of degrees of freedom for various non-standard $hp$-finite element spaces employing reduced cardinality basis. More specifically, we show that serendipity finite element methods and discontinuous Galerkin finite element methods with total degree $\mathcal{P}_p$ basis have a faster exponential convergence with respect to the number of degrees of freedom than their counterparts employing the tensor product $\mathcal{Q}_p$ basis for quadrilateral/hexahedral elements, for piecewise analytic problems under $p$-refinement. The above results are proven by using a new $p$-optimal error bound for the $L^2$-orthogonal projection onto the total degree $\mathcal{P}_p$ basis, and for the $H^1$-projection onto the serendipity finite element space over tensor product elements with dimension $d\geq2$. These new $p$-optimal error bounds lead to a larger exponent of the exponential rate of convergence with respect to the number of degrees of freedom. Moreover, these results show that part of the basis functions in $\mathcal{Q}_p$ basis play no roles in achieving the $hp$-optimal error bound in the Sobolev space. The sharpness of theoretical results is also verified by a series of numerical examples.

Apr 27 2017

math.NA arXiv:1704.07995v1

In this article, we consider discrete schemes for a fractional diffusion equation involving a tempered fractional derivative in time. We present a semi-discrete scheme by using the local discontinuous Galerkin (LDG) discretization in the spatial variables. We prove that the semi-discrete scheme is unconditionally stable in $L^2$ norm and convergence with optimal convergence rate $\mathcal{O}(h^{k+1})$. We develop a class of fully discrete LDG schemes by combining the weighted and shifted Lubich difference operators with respect to the time variable, and establish the error estimates. Finally, numerical experiments are presented to verify the theoretical results.

Apr 27 2017

math.NA arXiv:1704.07912v1

This paper introduces a new generalized polynomial chaos expansion (PCE) comprising multivariate Hermite orthogonal polynomials in dependent Gaussian random variables. The second-moment properties of Hermite polynomials reveal a weakly orthogonal system when obtained for a general Gaussian probability measure. Still, the exponential integrability of norm allows the Hermite polynomials to constitute a complete set and hence a basis in a Hilbert space. The completeness is vitally important for the convergence of the generalized PCE to the correct limit. The optimality of the generalized PCE and the approximation quality due to truncation are discussed. New analytical formulae are proposed to calculate the mean and variance of a generalized PCE approximation of a general output variable in terms of the expansion coefficients and statistical properties of Hermite polynomials. However, unlike in the classical PCE, calculating the coefficients of the generalized PCE requires solving a coupled system of linear equations. Besides, the variance formula of the generalized PCE contains additional terms due to statistical dependence among Gaussian variables. The additional terms vanish when the Gaussian variables are statistically independent, reverting the generalized PCE to the classical PCE. Numerical examples illustrate the generalized PCE approximation in estimating the statistical properties of various output variables.

In this article we explore an algorithm for diffeomorphic random sampling of nonuniform probability distributions on Riemannian manifolds. The algorithm is based on optimal information transport (OIT)---an analogue of optimal mass transport (OMT). Our framework uses the deep geometric connections between the Fisher-Rao metric on the space of probability densities and the right-invariant information metric on the group of diffeomorphisms. The resulting sampling algorithm is a promising alternative to OMT, in particular as our formulation is semi-explicit, free of the nonlinear Monge--Ampere equation. Compared to Markov Chain Monte Carlo methods, we expect our algorithm to stand up well when a large number of samples from a low dimensional nonuniform distribution is needed.