亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

This paper studies the approximation error of ReLU networks in terms of the number of intrinsic parameters (i.e., those depending on the target function $f$). First, we prove by construction that, for any Lipschitz continuous function $f$ on $[0,1]^d$ with a Lipschitz constant $\lambda>0$, a ReLU network with $n+2$ intrinsic parameters can approximate $f$ with an exponentially small error $5\lambda \sqrt{d}\,2^{-n}$ measured in the $L^p$-norm for $p\in [1,\infty)$. More generally for an arbitrary continuous function $f$ on $[0,1]^d$ with a modulus of continuity $\omega_f(\cdot)$, the approximation error is $\omega_f(\sqrt{d}\, 2^{-n})+2^{-n+2}\omega_f(\sqrt{d})$. Next, we extend these two results from the $L^p$-norm to the $L^\infty$-norm at a price of $3^d n+2$ intrinsic parameters. Finally, by using a high-precision binary representation and the bit extraction technique via a fixed ReLU network independent of the target function, we design, theoretically, a ReLU network with only three intrinsic parameters to approximate H\"older continuous functions with an arbitrarily small error.

The metric dimension dim(G) of a graph $G$ is the minimum cardinality of a subset $S$ of vertices of $G$ such that each vertex of $G$ is uniquely determined by its distances to $S$. It is well-known that the metric dimension of a graph can be drastically increased by the modification of a single edge. Our main result consists in proving that the increase of the metric dimension of an edge addition can be amortized in the sense that if the graph consists of a spanning tree $T$ plus $c$ edges, then the metric dimension of $G$ is at most the metric dimension of $T$ plus $6c$. We then use this result to prove a weakening of a conjecture of Eroh et al. The zero forcing number $Z(G)$ of $G$ is the minimum cardinality of a subset $S$ of black vertices (whereas the other vertices are colored white) of $G$ such that all the vertices will turned black after applying finitely many times the following rule: a white vertex is turned black if it is the only white neighbor of a black vertex. Eroh et al. conjectured that, for any graph $G$, $dim(G)\leq Z(G) + c(G)$, where $c(G)$ is the number of edges that have to be removed from $G$ to get a forest. They proved the conjecture is true for trees and unicyclic graphs. We prove a weaker version of the conjecture: $dim(G)\leq Z(G)+6c(G)$ holds for any graph. We also prove that the conjecture is true for graphs with edge disjoint cycles, widely generalizing the unicyclic result of Eroh et al.

We present a novel approach to adaptive optimal design of groundwater surveys - a methodology for choosing the location of the next monitoring well. Our dual-weighted approach borrows ideas from Bayesian Optimisation and goal-oriented error estimation to propose the next monitoring well, given that some data is already available from existing wells. Our method is distinct from other optimal design strategies in that it does not rely on Fisher Information and it instead directly exploits the posterior uncertainty and the expected solution to a dual (or adjoint) problem to construct an acquisition function that optimally reduces the uncertainty in the model as a whole and some engineering quantity of interest in particular. We demonstrate our approach in the context of 2D groundwater flow example and show that employing the expectation of the dual solution as a weighting function improves the posterior estimate of the quantity of interest on average by a factor of 3, compared to the baseline approach, where only the posterior uncertainty is considered.

We study the classical expander codes, introduced by Sipser and Spielman \cite{SS96}. Given any constants $0< \alpha, \varepsilon < 1/2$, and an arbitrary bipartite graph with $N$ vertices on the left, $M < N$ vertices on the right, and left degree $D$ such that any left subset $S$ of size at most $\alpha N$ has at least $(1-\varepsilon)|S|D$ neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly $\frac{\alpha N}{2 \varepsilon }$. This is strictly better than the best known previous result of $2(1-\varepsilon ) \alpha N$ \cite{Sudan2000note, Viderman13b} whenever $\varepsilon < 1/2$, and improves the previous result significantly when $\varepsilon $ is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever $\varepsilon < \frac{1}{4}$. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.

In the Non-Uniform $k$-Center problem, a generalization of the famous $k$-center clustering problem, we want to cover the given set of points in a metric space by finding a placement of balls with specified radii. In $t$-NU$k$C Problem, we assume that the number of distinct radii is equal to $t$, and we are allowed to use $k_i$ balls of radius $r_i$, for $1 \le i \le t$. This problem was introduced by Chakrabarty et al. [ACM Trans. Alg. 16(4):46:1-46:19], who showed that a constant approximation for $t$-NU$k$C is not possible if $t$ is unbounded. On the other hand, they gave a bicriteria approximation that violates the number of allowed balls as well as the given radii by a constant factor. They also conjectured that a constant approximation for $t$-NU$k$C should be possible if $t$ is a fixed constant. Since then, there has been steady progress towards resolving this conjecture -- currently, a constant approximation for $3$-NU$k$C is known via the results of Chakrabarty and Negahbani [IPCO 2021], and Jia et al. [To appear in SOSA 2022]. We push the horizon by giving an $O(1)$-approximation for the Non-Uniform $k$-Center for $4$ distinct types of radii. Our result is obtained via a novel combination of tools and techniques from the $k$-center literature, which also demonstrates that the different generalizations of $k$-center involving non-uniform radii, and multiple coverage constraints (i.e., colorful $k$-center), are closely interlinked with each other. We hope that our ideas will contribute towards a deeper understanding of the $t$-NU$k$C problem, eventually bringing us closer to the resolution of the CGK conjecture.

The Half-Space Matching (HSM) method has recently been developed as a new method for the solution of 2D scattering problems with complex backgrounds, providing an alternative to Perfectly Matched Layers (PML) or other artificial boundary conditions. Based on half-plane representations for the solution, the scattering problem is rewritten as a system coupling (1) a standard finite element discretisation localised around the scatterer and (2) integral equations whose unknowns are traces of the solution on the boundaries of a finite number of overlapping half-planes contained in the domain. While satisfactory numerical results have been obtained for real wavenumbers, well-posedness and equivalence of this HSM formulation to the original scattering problem have been established only for complex wavenumbers. In the present paper we show, in the case of a homogeneous background, that the HSM formulation is equivalent to the original scattering problem also for real wavenumbers, and so is well-posed, provided the traces satisfy radiation conditions at infinity analogous to the standard Sommerfeld radiation condition. As a key component of our argument we show that, if the trace on the boundary of a half-plane satisfies our new radiation condition, then the corresponding solution to the half-plane Dirichlet problem satisfies the Sommerfeld radiation condition in a slightly smaller half-plane. We expect that this last result will be of independent interest, in particular in studies of rough surface scattering.

We consider GMRES applied to discretisations of the high-frequency Helmholtz equation with strong trapping; recall that in this situation the problem is exponentially ill-conditioned through an increasing sequence of frequencies. Under certain assumptions about the distribution of the eigenvalues, we prove upper bounds on how the number of GMRES iterations grows with the frequency. Our main focus is on boundary-integral-equation formulations of the exterior Dirichlet and Neumann obstacle problems in 2- and 3-d; for these problems, we investigate numerically the sharpness (in terms of dependence on frequency) of both our bounds and various quantities entering our bounds. This paper is therefore the first comprehensive study of the frequency-dependence of the number of GMRES iterations for Helmholtz boundary-integral equations under trapping.

For a graph class $\mathcal{C}$, the $\mathcal{C}$-Edge-Deletion problem asks for a given graph $G$ to delete the minimum number of edges from $G$ in order to obtain a graph in $\mathcal{C}$. We study the $\mathcal{C}$-Edge-Deletion problem for $\mathcal{C}$ the permutation graphs, interval graphs, and other related graph classes. It follows from Courcelle's Theorem that these problems are fixed parameter tractable when parameterized by treewidth. In this paper, we present concrete FPT algorithms for these problems. By giving explicit algorithms and analyzing these in detail, we obtain algorithms that are significantly faster than the algorithms obtained by using Courcelle's theorem.

The induced odd cycle packing number $iocp(G)$ of a graph $G$ is the maximum integer $k$ such that $G$ contains an induced subgraph consisting of $k$ pairwise vertex-disjoint odd cycles. Motivated by applications to geometric graphs, Bonamy et al.~\cite{indoc} proved that graphs of bounded induced odd cycle packing number, bounded VC dimension, and linear independence number admit a randomized EPTAS for the independence number. We show that the assumption of bounded VC dimension is not necessary, exhibiting a randomized algorithm that for any integers $k\ge 0$ and $t\ge 1$ and any $n$-vertex graph $G$ of induced odd cycle packing number at most $k$ returns in time $O_{k,t}(n^{k+4})$ an independent set of $G$ whose size is at least $\alpha(G)-n/t$ with high probability. In addition, we present $\chi$-boundedness results for graphs with bounded odd cycle packing number, and use them to design a QPTAS for the independence number only assuming bounded induced odd cycle packing number.

Algebraic Riccati equations with indefinite quadratic terms play an important role in applications related to robust controller design. While there are many established approaches to solve these in case of small-scale dense coefficients, there is no approach available to compute solutions in the large-scale sparse setting. In this paper, we develop an iterative method to compute low-rank approximations of stabilizing solutions of large-scale sparse continuous-time algebraic Riccati equations with indefinite quadratic terms. We test the developed approach for dense examples in comparison to other established matrix equation solvers, and investigate the applicability and performance in large-scale sparse examples.