We study the classical Laplace asymptotic expansion of $\int_{\mathbb R^d} f(x)e^{-nv(x)}dx$ in high dimensions $d$. We derive an error bound to the expansion when truncated to arbitrary order. The error bound is fully explicit except for absolute constants, and it depends on $d$, $n$, and operator norms of the derivatives of $v$ and $f$ in a neighborhood of the minimizer of $v$.
相關內容
Incorporating probabilistic terms in mathematical models is crucial for capturing and quantifying uncertainties of real-world systems. However, stochastic models typically require large computational resources to produce meaningful statistics. For such reason, the development of reduction techniques becomes essential for enabling efficient and scalable simulations of complex scenarios while quantifying the underlying uncertainties. In this work, we study the accuracy of Polynomial Chaos (PC) surrogate expansion of the probability space on a bifurcating phenomena in fluid dynamics, namely the Coand\u{a} effect. In particular, we propose a novel non-deterministic approach to generic bifurcation problems, where the stochastic setting gives a different perspective on the non-uniqueness of the solution, also avoiding expensive simulations for many instances of the parameter. Thus, starting from the formulation of the Spectral Stochastic Finite Element Method (SSFEM), we extend the methodology to deal with solutions of a bifurcating problem, by working with a perturbed version of the deterministic model. We discuss the link between the deterministic and the stochastic bifurcation diagram, highlighting the surprising capability of PC polynomials coefficients of giving insights on the deterministic solution manifold.
We study the problem of Hamiltonian structure learning from real-time evolution: given the ability to apply $e^{-\mathrm{i} Ht}$ for an unknown local Hamiltonian $H = \sum_{a = 1}^m \lambda_a E_a$ on $n$ qubits, the goal is to recover $H$. This problem is already well-understood under the assumption that the interaction terms, $E_a$, are given, and only the interaction strengths, $\lambda_a$, are unknown. But how efficiently can we learn a local Hamiltonian without prior knowledge of its interaction structure? We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area, all while achieving the gold standard of Heisenberg-limited scaling. In particular, our algorithm recovers the Hamiltonian to $\varepsilon$ error with total evolution time $O(\log (n)/\varepsilon)$, and has the following appealing properties: (1) it does not need to know the Hamiltonian terms; (2) it works beyond the short-range setting, extending to any Hamiltonian $H$ where the sum of terms interacting with a qubit has bounded norm; (3) it evolves according to $H$ in constant time $t$ increments, thus achieving constant time resolution. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracy $\varepsilon$ with total evolution time beating the standard limit of $1/\varepsilon^2$.
We study linear polynomial approximation of functions in weighted Sobolev spaces $W^r_{p,w}(\mathbb{R}^d)$ of mixed smoothness $r \in \mathbb{N}$, and their optimality in terms of Kolmogorov and linear $n$-widths of the unit ball $\boldsymbol{W}^r_{p,w}(\mathbb{R}^d)$ in these spaces. The approximation error is measured by the norm of the weighted Lebesgue space $L_{q,w}(\mathbb{R}^d)$. The weight $w$ is a tensor-product Freud weight. For $1\le p,q \le \infty$ and $d=1$, we prove that the polynomial approximation by de la Vall\'ee Poussin sums of the orthonormal polynomial expansion of functions with respect to the weight $w^2$, is asymptotically optimal in terms of relevant linear $n$-widths $\lambda_n\big(\boldsymbol{W}^r_{p,w}(\mathbb{R}, L_{q,w}(\mathbb{R})\big)$ and Kolmogorov $n$-widths $d_n\big(\boldsymbol{W}^r_{p,w}(\mathbb{R}), L_{q,w}(\mathbb{R})\big)$ for $1\le q \le p <\infty$. For $1\le p,q \le \infty$ and $d\ge 2$, we construct linear methods of hyperbolic cross polynomial approximation based on tensor product of successive differences of dyadic-scaled de la Vall\'ee Poussin sums, which are counterparts of hyperbolic cross trigonometric linear polynomial approximation, and give some upper bounds of the error of these approximations for various pair $p,q$ with $1 \le p, q \le \infty$. For some particular weights $w$ and $d \ge 2$, we prove the right convergence rate of $\lambda_n\big(\boldsymbol{W}^r_{2,w}(\mathbb{R}^d), L_{2,w}(\mathbb{R}^d)\big)$ and $d_n\big(\boldsymbol{W}^r_{2,w}(\mathbb{R}^d), L_{2,w}(\mathbb{R}^d)\big)$ which is performed by a constructive hyperbolic cross polynomial approximation.
Reed in 1998 conjectured that every graph $G$ satisfies $\chi(G) \leq \lceil \frac{\Delta(G)+1+\omega(G)}{2} \rceil$. As a partial result, he proved the existence of $\varepsilon > 0$ for which every graph $G$ satisfies $\chi(G) \leq \lceil (1-\varepsilon)(\Delta(G)+1)+\varepsilon\omega(G) \rceil$. We propose an analogue conjecture for digraphs. Given a digraph $D$, we denote by $\vec{\chi}(D)$ the dichromatic number of $D$, which is the minimum number of colours needed to partition $D$ into acyclic induced subdigraphs. We let $\overleftrightarrow{\omega}(D)$ denote the size of the largest biclique (a set of vertices inducing a complete digraph) of $D$ and $\tilde{\Delta}(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We conjecture that every digraph $D$ satisfies $\vec{\chi}(D) \leq \lceil \frac{\tilde{\Delta}(D)+1+\overleftrightarrow{\omega}(D)}{2} \rceil$, which if true implies Reed's conjecture. As a partial result, we prove the existence of $\varepsilon >0$ for which every digraph $D$ satisfies $\vec{\chi}(D) \leq \lceil (1-\varepsilon)(\tilde{\Delta}(D)+1)+\varepsilon\overleftrightarrow{\omega}(D) \rceil$. This implies both Reed's result and an independent result of Harutyunyan and Mohar for oriented graphs. To obtain this upper bound on $\vec{\chi}$, we prove that every digraph $D$ with $\overleftrightarrow{\omega}(D) > \frac{2}{3}(\Delta_{\max}(D)+1)$, where $\Delta_{\max}(D) = \max_{v\in V(D)} \max(d^+(v),d^-(v))$, admits an acyclic set of vertices intersecting each biclique of $D$, which generalises a result of King.
We develop a monotone, two-scale discretization for a class of integrodifferential operators of order $2s$, $s \in (0,1)$. We apply it to develop numerical schemes, and derive pointwise convergence rates, for linear and obstacle problems governed by such operators. As applications of the monotonicity, we provide error estimates for free boundaries and a convergent numerical scheme for a concave fully nonlinear, nonlocal, problem.
We consider structured approximation of measures in Wasserstein space $\mathrm{W}_p(\mathbb{R}^d)$ for $p\in[1,\infty)$ using general measure approximants compactly supported on Voronoi regions derived from a scaled Voronoi partition of $\mathbb{R}^d$. We show that if a full rank lattice $\Lambda$ is scaled by a factor of $h\in(0,1]$, then approximation of a measure based on the Voronoi partition of $h\Lambda$ is $O(h)$ regardless of $d$ or $p$. We then use a covering argument to show that $N$-term approximations of compactly supported measures is $O(N^{-\frac1d})$ which matches known rates for optimal quantizers and empirical measure approximation in most instances. Additionally, we generalize our construction to nonuniform Voronoi partitions, highlighting the flexibility and robustness of our approach for various measure approximation scenarios. Finally, we extend these results to noncompactly supported measures with sufficient decay. Our findings are pertinent to applications in computer vision and machine learning where measures are used to represent structured data such as images.
A $k$-uniform hypergraph $H = (V, E)$ is $k$-partite if $V$ can be partitioned into $k$ sets $V_1, \ldots, V_k$ such that every edge in $E$ contains precisely one vertex from each $V_i$. We call such a graph $n$-balanced if $|V_i| = n$ for each $i$. An independent set $I$ in $H$ is balanced if $|I\cap V_i| = |I\cap V_j|$ for each $1 \leq i, j \leq k$, and a coloring is balanced if each color class induces a balanced independent set in $H$. In this paper, we provide a lower bound on the balanced independence number $\alpha_b(H)$ in terms of the average degree $D = |E|/n$, and an upper bound on the balanced chromatic number $\chi_b(H)$ in terms of the maximum degree $\Delta$. Our results recover those of recent work of Chakraborti for $k = 2$.
We prove that for every positive integer $d$ and forest $F$, the class of intersection graphs of axis-aligned boxes in $\mathbb{R}^d$ with no induced $F$ subgraph is (polynomially) $\chi$-bounded.
Consider a data matrix $Y = [\mathbf{y}_1, \cdots, \mathbf{y}_N]$ of size $M \times N$, where the columns are independent observations from a random vector $\mathbf{y}$ with zero mean and population covariance $\Sigma$. Let $\mathbf{u}_i$ and $\mathbf{v}_j$ denote the left and right singular vectors of $Y$, respectively. This study investigates the eigenvector/singular vector overlaps $\langle {\mathbf{u}_i, D_1 \mathbf{u}_j} \rangle$, $\langle {\mathbf{v}_i, D_2 \mathbf{v}_j} \rangle$ and $\langle {\mathbf{u}_i, D_3 \mathbf{v}_j} \rangle$, where $D_k$ are general deterministic matrices with bounded operator norms. We establish the convergence in probability of these eigenvector overlaps toward their deterministic counterparts with explicit convergence rates, when the dimension $M$ scales proportionally with the sample size $N$. Building on these findings, we offer a more precise characterization of the loss for Ledoit and Wolf's nonlinear shrinkage estimators of the population covariance $\Sigma$.
In combinatorics on words, the well-studied factor complexity function $\rho_{\bf x}$ of a sequence ${\bf x}$ over a finite alphabet counts, for any nonnegative integer $n$, the number of distinct length-$n$ factors of $\mathbf{x}$. In this paper, we introduce the reflection complexity function $r_{\bf x}$ to enumerate the factors occurring in a sequence ${\bf x}$, up to reversing the order of symbols in a word. We introduce and prove general results on $r_{\bf x}$ regarding its growth properties and relationship with other complexity functions. We prove a Morse-Hedlund-type result characterizing eventually periodic sequences in terms of their reflection complexity, and we deduce a characterization of Sturmian sequences. Furthermore, we investigate the reflection complexity of quasi-Sturmian, episturmian, $(s+1)$-dimensional billiard, and complementation-symmetric Rote, and rich sequences. Furthermore, we prove that if ${\bf x}$ is $k$-automatic, then $r_{\bf x}$ is computably $k$-regular, and we use the software $\mathtt{Walnut}$ to evaluate the reflection complexity of automatic sequences, such as the Thue-Morse sequence. We note that there are still many unanswered questions about this measure.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191