Randomized quasi-Monte Carlo, via certain scramblings of digital nets, produces unbiased estimates of $\int_{[0,1]^d}f(\boldsymbol{x})\,\mathrm{d}\boldsymbol{x}$ with a variance that is $o(1/n)$ for any $f\in L^2[0,1]^d$. It also satisfies some non-asymptotic bounds where the variance is no larger than some $\Gamma<\infty$ times the ordinary Monte Carlo variance. For scrambled Sobol' points, this quantity $\Gamma$ grows exponentially in $d$. For scrambled Faure points, $\Gamma \leqslant \exp(1)\doteq 2.718$ in any dimension, but those points are awkward to use for large $d$. This paper shows that certain scramblings of Halton sequences have gains below an explicit bound that is $O(\log d)$ but not $O( (\log d)^{1-\epsilon})$ for any $\epsilon>0$ as $d\to\infty$. For $6\leqslant d\leqslant 10^6$, the upper bound on the gain coefficient is never larger than $3/2+\log(d/2)$.
相關內容
The property that the velocity $\boldsymbol{u}$ belongs to $L^\infty(0,T;L^2(\Omega)^d)$ is an essential requirement in the definition of energy solutions of models for incompressible fluids. It is, therefore, highly desirable that the solutions produced by discretisation methods are uniformly stable in the $L^\infty(0,T;L^2(\Omega)^d)$-norm. In this work, we establish that this is indeed the case for Discontinuous Galerkin (DG) discretisations (in time and space) of non-Newtonian models with $p$-structure, assuming that $p\geq \frac{3d+2}{d+2}$; the time discretisation is equivalent to the RadauIIA Implicit Runge-Kutta method. We also prove (weak) convergence of the numerical scheme to the weak solution of the system; this type of convergence result for schemes based on quadrature seems to be new. As an auxiliary result, we also derive Gagliardo-Nirenberg-type inequalities on DG spaces, which might be of independent interest.
The greedy and nearest-neighbor TSP heuristics can both have $\log n$ approximation factors from optimal in worst case, even just for $n$ points in Euclidean space. In this note, we show that this approximation factor is only realized when the optimal tour is unusually short. In particular, for points from any fixed $d$-Ahlfor's regular metric space (which includes any $d$-manifold like the $d$-cube $[0,1]^d$ in the case $d$ is an integer but also fractals of dimension $d$ when $d$ is real-valued), our results imply that the greedy and nearest-neighbor heuristics have \emph{additive} errors from optimal on the order of the \emph{optimal} tour length through \emph{random} points in the same space, for $d>1$.
In the context of the Cobb-Douglas productivity model we consider the $N \times N$ input-output linkage matrix $W$ for a network of $N$ firms $f_1, f_2, \cdots, f_N$. The associated influence vector $v_w$ of $W$ is defined in terms of the Leontief inverse $L_W$ of $W$ as $v_W = \frac{\alpha}{N} L_W \vec{\mathbf{1}}$ where $L_W = (I - (1-\alpha) W')^{-1}$, $W'$ denotes the transpose of $W$ and $I$ is the identity matrix. Here $\vec{\mathbf{1}}$ is the $N \times 1$ vector whose entries are all one. The influence vector is a metric of the importance for the firms in the production network. Under the realistic assumption that the data to compute the influence vector is incomplete, we prove bounds on the worst-case error for the influence vector that are sharp up to a constant factor. We also consider the situation where the missing data is binomially distributed and contextualize the bound on the influence vector accordingly. We also investigate how far off the influence vector can be when we only have data on nodes and connections that are within distance $k$ of some source node. A comparison of our results is juxtaposed against PageRank analogues. We close with a discussion on a possible extension beyond Cobb-Douglas to the Constant Elasticity of Substitution model, as well as the possibility of considering other probability distributions for missing data.
We introduce a novel formulation for the evolution of parametric curves by anisotropic curve shortening flow in ${\mathbb R}^d$, $d\geq2$. The reformulation hinges on a suitable manipulation of the parameterization's tangential velocity, leading to a strictly parabolic differential equation. Moreover, the derived equation is in divergence form, giving rise to a natural variational numerical method. For a fully discrete finite element approximation based on piecewise linear elements we prove optimal error estimates. Numerical simulations confirm the theoretical results and demonstrate the practicality of the method.
We show that the problem of counting the number of $n$-variable unate functions reduces to the problem of counting the number of $n$-variable monotone functions. Using recently obtained results on $n$-variable monotone functions, we obtain counts of $n$-variable unate functions up to $n=9$. We use an enumeration strategy to obtain the number of $n$-variable balanced monotone functions up to $n=7$. We show that the problem of counting the number of $n$-variable balanced unate functions reduces to the problem of counting the number of $n$-variable balanced monotone functions, and consequently, we obtain the number of $n$-variable balanced unate functions up to $n=7$. Using enumeration, we obtain the numbers of equivalence classes of $n$-variable balanced monotone functions, unate functions and balanced unate functions up to $n=6$. Further, for each of the considered sub-class of $n$-variable monotone and unate functions, we also obtain the corresponding numbers of $n$-variable non-degenerate functions.
Katona and Varga showed that for any rational number $t \in (1/2,1]$, no chordal graph is minimally $t$-tough. We conjecture that no chordal graph is minimally $t$-tough for $t>1/2$ and prove several results supporting the conjecture. In particular, we show that for $t>1/2$, no strongly chordal graph is minimally $t$-tough, no split graph is minimally $t$-tough, and no chordal graph with a universal vertex is minimally $t$-tough.
We examine a method for solving an infinite-dimensional tensor eigenvalue problem $H x = \lambda x$, where the infinite-dimensional symmetric matrix $H$ exhibits a translational invariant structure. We provide a formulation of this type of problem from a numerical linear algebra point of view and describe how a power method applied to $e^{-Ht}$ is used to obtain an approximation to the desired eigenvector. This infinite-dimensional eigenvector is represented in a compact way by a translational invariant infinite Tensor Ring (iTR). Low rank approximation is used to keep the cost of subsequent power iterations bounded while preserving the iTR structure of the approximate eigenvector. We show how the averaged Rayleigh quotient of an iTR eigenvector approximation can be efficiently computed and introduce a projected residual to monitor its convergence. In the numerical examples, we illustrate that the norm of this projected iTR residual can also be used to automatically modify the time step $t$ to ensure accurate and rapid convergence of the power method.
We present a new and straightforward derivation of a family $\mathcal{F}(h,\tau)$ of exponential splittings of Strang-type for the general linear evolutionary equation with two linear components. One component is assumed to be a time-independent, unbounded operator, while the other is a bounded one with explicit time dependence. The family $\mathcal{F}(h,\tau)$ is characterized by the length of the time-step $h$ and a continuous parameter $\tau$, which defines each member of the family. It is shown that the derivation and error analysis follows from two elementary arguments: the variation of constants formula and specific quadratures for integrals over simplices. For these Strang-type splittings, we prove their convergence which, depending on some commutators of the relevant operators, may be of first or second order. As a result, error bounds appear in terms of commutator bounds. Based on the explicit form of the error terms, we establish the influence of $\tau$ on the accuracy of $\mathcal{F}(h,\tau)$, allowing us to investigate the optimal value of $\tau$. This simple yet powerful approach establishes the connection between exponential integrators and splitting methods. Furthermore, the present approach can be easily applied to the derivation of higher-order splitting methods under similar considerations. Needless to say, the obtained results also apply to Strang-type splittings in the case of time independent-operators. To complement rigorous results, we present numerical experiments with various values of $\tau$ based on the linear Schr\"odinger equation.
We consider the problem of fitting a centered ellipsoid to $n$ standard Gaussian random vectors in $\mathbb{R}^d$, as $n, d \to \infty$ with $n/d^2 \to \alpha > 0$. It has been conjectured that this problem is, with high probability, satisfiable (SAT; that is, there exists an ellipsoid passing through all $n$ points) for $\alpha < 1/4$, and unsatisfiable (UNSAT) for $\alpha > 1/4$. In this work we give a precise analytical argument, based on the non-rigorous replica method of statistical physics, that indeed predicts a SAT/UNSAT transition at $\alpha = 1/4$, as well as the shape of a typical fitting ellipsoid in the SAT phase (i.e., the lengths of its principal axes). Besides the replica method, our main tool is the dilute limit of extensive-rank "HCIZ integrals" of random matrix theory. We further study different explicit algorithmic constructions of the matrix characterizing the ellipsoid. In particular, we show that a procedure based on minimizing its nuclear norm yields a solution in the whole SAT phase. Finally, we characterize the SAT/UNSAT transition for ellipsoid fitting of a large class of rotationally-invariant random vectors. Our work suggests mathematically rigorous ways to analyze fitting ellipsoids to random vectors, which is the topic of a companion work.
We discuss the numerical solution of initial value problems for $\varepsilon^2\,\varphi''+a(x)\,\varphi=0$ in the highly oscillatory regime, i.e., with $a(x)>0$ and $0<\varepsilon\ll 1$. We analyze and implement an approximate solution based on the well-known WKB-ansatz. The resulting approximation error is of magnitude $\mathcal{O}(\varepsilon^{N})$ where $N$ refers to the truncation order of the underlying asymptotic series. When the optimal truncation order $N_{opt}$ is chosen, the error behaves like $\mathcal{O}(\varepsilon^{-2}\exp(-c\varepsilon^{-1}))$ with some $c>0$.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191