Strong tractability of multivariate integration using quasi-Monte Carlo algorithms

We study quasi-Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of depends on and the dimension . Strong tractability means that it does not depend on and is bounded by a polynomial in . The least possible value of the power of is called the -exponent of strong tractability. Sloan and Wozniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the -exponent of strong tractability is between 1 and 2. However, their proof is not constructive.

In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Wozniakowski's assumption. We show that quasi-Monte Carlo algorithms using Niederreiter's -sequences and Sobol sequences achieve the optimal convergence order for any 0$"> independent of the dimension with a worst case deterministic guarantee (where is the number of function evaluations). This implies that strong tractability with the best -exponent can be achieved in appropriate weighted Sobolev spaces by using Niederreiter's -sequences and Sobol sequences.

     

The power of standard information for multivariate approximation in the randomized setting

We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted -norm. We consider functions with an arbitrarily large number of variables, , and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points.

We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the th minimal errors, i.e., of the minimal errors among all algorithms using function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting.

We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor is polynomial in  (strong tractability), and polynomial in and (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check.

We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of , we prove that strong tractability is equivalent to tractability.

We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.

     

The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension

Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation.

Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor is bounded by for some exponent and some positive constant . The -exponent of tractability is defined as the smallest power of in these bounds. It is shown by using Monte Carlo quadrature that the -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.

     

Symmetry-breaking bifurcation of analytic solutions to free boundary problems: An application to a model of tumor growth

In this paper we develop a general technique for establishing analyticity of solutions of partial differential equations which depend on a parameter . The technique is worked out primarily for a free boundary problem describing a model of a stationary tumor. We prove the existence of infinitely many branches of symmetry-breaking solutions which bifurcate from any given radially symmetric steady state; these asymmetric solutions are analytic jointly in the spatial variables and in .

     

Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers

We study the approximation problem (or problem of optimal recovery in the $L_2$-norm) for weighted Korobov spaces with smoothness parameter $\a$. The weights $\gamma_j$ of the Korobov spaces moderate the behavior of periodic functions with respect to successive variables. The nonnegative smoothness parameter $\a$ measures the decay of Fourier coefficients. For $\a=0$, the Korobov space is the $L_2$ space, whereas for positive $\a$, the Korobov space is a space of periodic functions with some smoothness and the approximation problem corresponds to a compact operator. The periodic functions are defined on $[0,1]^d$ and our main interest is when the dimension $d$ varies and may be large. We consider algorithms using two different classes of information. The first class $\lall$ consists of arbitrary linear functionals. The second class $\lstd$ consists of only function values and this class is more realistic in practical computations. We want to know when the approximation problem is tractable. Tractability means that there exists an algorithm whose error is at most $\e$ and whose information cost is bounded by a polynomial in the dimension $d$ and in $\e^{-1}$. Strong tractability means that the bound does not depend on $d$ and is polynomial in $\e^{-1}$. In this paper we consider the worst case, randomized, and quantum settings. In each setting, the concepts of error and cost are defined differently and, therefore, tractability and strong tractability depend on the setting and on the class of information. In the worst case setting, we apply known results to prove that strong tractability and tractability in the class $\lall$ are equivalent. This holds if and only if $\a>0$ and the sum-exponent $s_{\g}$ of weights is finite, where $s_{\g}= \inf\{s>0 : \xxsum_{j=1}^\infty\g_j^s\,<\,\infty\}$. In the worst case setting for the class $\lstd$ we must assume that $\a>1$ to guarantee that functionals from $\lstd$ are continuous. The notions of strong tractability and tractability are not equivalent. In particular, strong tractability holds if and only if $\a>1$ and $\xxsum_{j=1}^\infty\g_j<\infty$. In the randomized setting, it is known that randomization does not help over the worst case setting in the class $\lall$. For the class $\lstd$, we prove that strong tractability and tractability are equivalent and this holds under the same assumption as for the class $\lall$ in the worst case setting, that is, if and only if $\a>0$ and $s_{\g} < \infty$. In the quantum setting, we consider only upper bounds for the class $\lstd$ with $\a>1$. We prove that $s_{\g}<\infty$ implies strong tractability. Hence for $s_{\g}>1$, the randomized and quantum settings both break worst case intractability of approximation for the class $\lstd$. We indicate cost bounds on algorithms with error at most $\e$. Let $\cc(d)$ denote the cost of computing $L(f)$ for $L\in \lall$ or $L\in \lstd$, and let the cost of one arithmetic operation be taken as unity. The information cost bound in the worst case setting for the class $\lall$ is of order $\cc (d) \cdot \e^{-p}$ with $p$ being roughly equal to $2\max(s_\g,\a^{-1})$. Then for the class $\lstd$ in the randomized setting, we present an algorithm with error at most $\e$ and whose total cost is of order $\cc(d)\e^{-p-2} + d\e^{-2p-2}$, which for small $\e$ is roughly $$ d\e^{-2p-2}. $$ In the quantum setting, we present a quantum algorithm with error at most $\e$ that uses about only $d + \log \e^{-1}$ qubits and whose total cost is of order $$ (\cc(d) +d) \e^{-1-3p/2}. $$ The ratio of the costs of the algorithms in the quantum setting and the randomized setting is of order $$ \frac{d}{\cc(d)+d}\,\left(\frac1{\e}\right)^{1+p/2}. $$ Hence, we have a polynomial speedup of order $\e^{-(1+p/2)}$. We stress that $p$ can be arbitrarily large, and in this case the speedup is huge.     

A nonconforming combination of the finite element and volume methods with an anisotropic mesh refinement for a singularly perturbed convection-diffusion equation

In this paper we formulate and analyze a discretization method for a 2D linear singularly perturbed convection-diffusion problem with a singular perturbation parameter . The method is based on a nonconforming combination of the conventional Galerkin piecewise linear triangular finite element method and an exponentially fitted finite volume method, and on a mixture of triangular and rectangular elements. It is shown that the method is stable with respect to a semi-discrete energy norm and the approximation error in the semi-discrete energy norm is bounded by with independent of the mesh parameter , the diffusion coefficient and the exact solution of the problem.

     

The probability that a slightly perturbed numerical analysis problem is difficult

We prove a general theorem providing smoothed analysis estimates for conic condition numbers of problems of numerical analysis. Our probability estimates depend only on geometric invariants of the corresponding sets of ill-posed inputs. Several applications to linear and polynomial equation solving show that the estimates obtained in this way are easy to derive and quite accurate. The main theorem is based on a volume estimate of -tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a spherical disk of radius . Besides and , this bound depends only on the dimension of the sphere and on the degree of the defining equations.

     

Optimal Order Quadrature Error Bounds for Infinite-Dimensional Higher-Order Digital Sequences

Quasi-Monte Carlo (QMC) quadrature rules using higher-order digital nets and sequences have been shown to achieve the almost optimal rate of convergence of the worst-case error in Sobolev spaces of arbitrary fixed smoothness \(\alpha \in \mathbb {N}\), \(\alpha \ge 2\). In a recent paper by the authors, it was proved that randomly digitally shifted order \(2\alpha \) digital nets in prime base b achieve the best possible rate of convergence of the root mean square worst-case error of order \(N^{-\alpha }(\log N)^{(s-1)/2}\) for \(N=b^m\), where N and s denote the number of points and the dimension, respectively, which implies the existence of an optimal order QMC rule. More recently, the authors provided an explicit construction of such an optimal order QMC rule by using Chen–Skriganov’s digital nets in conjunction with Dick’s digit interlacing composition. These results were for fixed number of points. In this paper, we give a more general result on an explicit construction of optimal order QMC rules for arbitrary fixed smoothness \(\alpha \in \mathbb {N}\) including the endpoint case \(\alpha =1\). That is, we prove that the projection of any infinite-dimensional order \(2\alpha +1\) digital sequence in prime base b onto the first s coordinates achieves the best possible rate of convergence of the worst-case error of order \(N^{-\alpha }(\log N)^{(s-1)/2}\) for \(N=b^m\). The explicit construction presented in this paper is not only easy to implement but also extensible in both N and s.     

On a singular perturbation problem involving a ``circular-well' potential

We study the asymptotic behavior, as a small parameter goes to 0, of the minimizers for a variational problem which involves a ``circular-well' potential, i.e., a potential vanishing on a closed smooth curve in . We thus generalize previous results obtained for the special case of the Ginzburg-Landau potential.

     

Stability of small amplitude boundary layers for mixed hyperbolic-parabolic systems

We consider an initial boundary value problem for a symmetrizable mixed hyperbolic-parabolic system of conservation laws with a small viscosity , When the boundary is noncharacteristic for both the viscous and the inviscid system, and the boundary condition dissipative, we show that converges to a solution of the inviscid system before the formation of shocks if the amplitude of the boundary layer is sufficiently small. This generalizes previous results obtained for invertible and the linear study of Serre and Zumbrun obtained for a pure Dirichlet's boundary condition.

     

Stability of disjointness preserving mappings

Let and be compact Hausdorff spaces and let . A linear mapping is called -disjointness preserving if implies that . If is a continuous or surjective -disjointness preserving linear mapping, we prove that there exists a disjointness preserving linear mapping satisfying . We also prove that every unbounded -disjointness preserving linear functional on is disjointness preserving.

     

An extension of Elton's theorem to complex Banach spaces

Let 0$"> be sufficiently small. Then, for , there exists such that if are vectors in the unit ball of a complex Banach space which satisfy

(where are independent complex Steinhaus random variables), then there exists a set , with , such that

for all (). The dependence on of the threshold proportion is sharp.

     

Optimal quadrature for Haar wavelet spaces

This article considers the error of the scrambled equidistribution quadrature rules in the worst-case, random-case, and average-case settings. The underlying space of integrands is a Hilbert space of multidimensional Haar wavelet series, . The asymptotic orders of the errors are derived for the case of the scrambled -nets and -sequences. These rules are shown to have the best asymptotic convergence rates for any random quadrature rule for the space of integrands .

     

Boundedness of the fractional integral on weighted Lebesgue and Lipschitz spaces

Necessary and sufficient conditions are given for the fractional integral operator to be bounded from weighted strong and weak spaces within the range into suitable weighted and Lipschitz spaces. We also characterize the weights for which can be extended to a bounded operator from weighted into a weighted Lipschitz space of order . Finally, under an additional assumption on the weight, we obtain necessary and sufficient conditions for the boundedness of between weighted Lipschitz spaces.

     

Rate of convergence of finite difference approximations for degenerate ordinary differential equations

In this paper we study finite difference approximations for the following linear stationary convection-diffusion equations:

where is allowed to be degenerate. We first propose a new weighted finite difference scheme, motivated by approximating the diffusion process associated with the equation in the strong sense. We show that, under certain conditions, this scheme converges with the first order rate and that such a rate is sharp. To the best of our knowledge, this is the first sharp result in the literature. Moreover, by using the connection between our scheme and the standard upwind finite difference scheme, we get the rate of convergence of the latter, which is also new.

     

Liberating the weights

A partial answer to why quasi-Monte Carlo (QMC) algorithms work well for multivariate integration was given in Sloan and Woźniakowski (J. Complexity 14 (1998) 1–33) by introducing weighted spaces. In these spaces the importance of successive coordinate directions is quantified by a sequence of weights. However, to be able to make use of weighted spaces for a particular application one has to make a choice of the weights.In this work, we take a more general view of the weights by allowing them to depend arbitrarily not only on the coordinates but also on the number of variables. Liberating the weights in this way allows us to give a recommendation for how to choose the weights in practice. This recommendation results from choosing the weights so as to minimize the error bound. We also consider how best to choose the underlying weighted Sobolev space within which to carry out the analysis.We revisit also lower bounds on the worst-case error, which change in many minor ways now, since the weights are allowed to depend on the number of variables, and we do not assume that the weights are uniformly bounded as has been assumed in previous papers. Necessary and sufficient conditions for QMC tractability and strong QMC tractability are obtained for the weighted Sobolev spaces with general weights.In the final section, we show that the analysis of variance decomposition of functions from one of the Sobolev spaces is equivalent to the decomposition of functions with respect to an orthogonal decomposition of this space.     

On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces

We develop and justify an algorithm for the construction of quasi-Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found ``component-by-component': the ()-th component of the generator vector and the shift are obtained by successive -dimensional searches, with the previous components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for -point rules with prime and all dimensions 1 to requires a total cost of operations. This may be reduced to operations at the expense of storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.

     

Duality of weighted anisotropic Besov and Triebel–Lizorkin spaces

Let A be an expansive dilation on ${{\mathbb R}^n}$ and w a Muckenhoupt ${\mathcal A_\infty(A)}$ weight. In this paper, for all parameters ${\alpha\in{\mathbb R} }$ and ${p,q\in(0,\infty)}$ , the authors identify the dual spaces of weighted anisotropic Besov spaces ${\dot B^\alpha_{p,q}(A;w)}$ and Triebel?CLizorkin spaces ${\dot F^\alpha_{p,q}(A;w)}$ with some new weighted Besov-type and Triebel?CLizorkin-type spaces. The corresponding results on anisotropic Besov spaces ${\dot B^\alpha_{p,q}(A; \mu)}$ and Triebel?CLizorkin spaces ${\dot F^\alpha_{p,q}(A; \mu)}$ associated with ${\rho_A}$ -doubling measure??? are also established. All results are new even for the classical weighted Besov and Triebel?CLizorkin spaces in the isotropic setting. In particular, the authors also obtain the ${\varphi}$ -transform characterization of the dual spaces of the classical weighted Hardy spaces on ${{\mathbb R}^n}$ .     

Extremal characterizations of asplund spaces

We prove new characterizations of Asplund spaces through certain extremal principles in nonsmooth analysis and optimization. The latter principles provide necessary conditions for extremal points of set systems in terms of Fréchet normals and -normals.

     

On Lelong-Bremermann Lemma

The main theorem of this note is the following refinement of the well-known Lelong-Bremermann Lemma:

Let be a continuous plurisubharmonic function on a Stein manifold of dimension Then there exists an integer , natural numbers , and analytic mappings such that the sequence of functions

converges to uniformly on each compact subset of .

In the case when is a domain in the complex plane, it is shown that one can take in the theorem above (Section 3); on the other hand, for -circular plurisubharmonic functions in the statement of this theorem is true with (Section 4). The last section contains some remarks and open questions.