We prove tight bounds on the site percolation threshold for $k$-uniform hypergraphs of maximum degree $\Delta$ and for $k$-uniform hypergraphs of maximum degree $\Delta$ in which any pair of edges overlaps in at most $r$ vertices. The hypergraphs that achieve these bounds are hypertrees, but unlike in the case of graphs, there are many different $k$-uniform, $\Delta$-regular hypertrees. Determining the extremal tree for a given $k, \Delta, r$ involves an optimization problem, and our bounds arise from a convex relaxation of this problem. By combining our percolation bounds with the method of disagreement percolation we obtain improved bounds on the uniqueness threshold for the hard-core model on hypergraphs satisfying the same constraints. Our uniqueness conditions imply exponential weak spatial mixing, and go beyond the known bounds for rapid mixing of local Markov chains and existence of efficient approximate counting and sampling algorithms. Our results lead to natural conjectures regarding the aforementioned algorithmic tasks, based on the intuition that uniqueness thresholds for the extremal hypertrees for percolation determine computational thresholds.
相關內容
Let the costs $C(i,j)$ for an instance of the asymmetric traveling salesperson problem be independent uniform $[0,1]$ random variables. We consider the efficiency of branch and bound algorithms that use the assignment relaxation as a lower bound. We show that w.h.p. the number of steps taken in any such branch and bound algorithm is $e^{\Omega(n^a)}$ for some small absolute constant $a>0$.
We introduce two new classes of covering codes in graphs for every positive integer $r$. These new codes are called local $r$-identifying and local $r$-locating-dominating codes and they are derived from $r$-identifying and $r$-locating-dominating codes, respectively. We study the sizes of optimal local 1-identifying codes in binary hypercubes. We obtain lower and upper bounds that are asymptotically tight. Together the bounds show that the cost of changing covering codes into local 1-identifying codes is negligible. For some small $n$ optimal constructions are obtained. Moreover, the upper bound is obtained by a linear code construction. Also, we study the densities of optimal local 1-identifying codes and local 1-locating-dominating codes in the infinite square grid, the hexagonal grid, the triangular grid, and the king grid. We prove that seven out of eight of our constructions have optimal densities.
The 3D reconstruction of simultaneous localization and mapping (SLAM) is an important topic in the field for transport systems such as drones, service robots and mobile AR/VR devices. Compared to a point cloud representation, the 3D reconstruction based on meshes and voxels is particularly useful for high-level functions, like obstacle avoidance or interaction with the physical environment. This article reviews the implementation of a visual-based 3D scene reconstruction pipeline on resource-constrained hardware platforms. Real-time performances, memory management and low power consumption are critical for embedded systems. A conventional SLAM pipeline from sensors to 3D reconstruction is described, including the potential use of deep learning. The implementation of advanced functions with limited resources is detailed. Recent systems propose the embedded implementation of 3D reconstruction methods with different granularities. The trade-off between required accuracy and resource consumption for real-time localization and reconstruction is one of the open research questions identified and discussed in this paper.
We develop an automated computational modeling framework for rapid gradient-based design of multistable soft mechanical structures composed of non-identical bistable unit cells with appropriate geometric parameterization. This framework includes a custom isogeometric analysis-based continuum mechanics solver that is robust and end-to-end differentiable, which enables geometric and material optimization to achieve a desired multistability pattern. We apply this numerical modeling approach in two dimensions to design a variety of multistable structures, accounting for various geometric and material constraints. Our framework demonstrates consistent agreement with experimental results, and robust performance in designing for multistability, which facilities soft actuator design with high precision and reliability.
Let $G$ be a graph on $n$ vertices with adjacency matrix $A$, and let $\mathbf{1}$ be the all-ones vector. We call $G$ controllable if the set of vectors $\mathbf{1}, A\mathbf{1}, \dots, A^{n-1}\mathbf{1}$ spans the whole space $\mathbb{R}^n$. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.
We introduce and study a scale of operator classes on the annulus that is motivated by the $\mathcal{C}_{\rho}$ classes of $\rho$-contractions of Nagy and Foia\c{s}. In particular, our classes are defined in terms of the contractivity of the double-layer potential integral operator over the annulus. We prove that if, in addition, complete contractivity is assumed, then one obtains a complete characterization involving certain variants of the $\mathcal{C}_{\rho}$ classes. Recent work of Crouzeix-Greenbaum and Schwenninger-de Vries allows us to also obtain relevant K-spectral estimates, generalizing existing results from the literature on the annulus. Finally, we exhibit a special case where these estimates can be significantly strengthened.
Let $E$ be a separable Banach space and let $X, X_1,\dots, X_n, \dots$ be i.i.d. Gaussian random variables taking values in $E$ with mean zero and unknown covariance operator $\Sigma: E^{\ast}\mapsto E.$ The complexity of estimation of $\Sigma$ based on observations $X_1,\dots, X_n$ is naturally characterized by the so called effective rank of $\Sigma:$ ${\bf r}(\Sigma):= \frac{{\mathbb E}_{\Sigma}\|X\|^2}{\|\Sigma\|},$ where $\|\Sigma\|$ is the operator norm of $\Sigma.$ Given a smooth real valued functional $f$ defined on the space $L(E^{\ast},E)$ of symmetric linear operators from $E^{\ast}$ into $E$ (equipped with the operator norm), our goal is to study the problem of estimation of $f(\Sigma)$ based on $X_1,\dots, X_n.$ The estimators of $f(\Sigma)$ based on jackknife type bias reduction are considered and the dependence of their Orlicz norm error rates on effective rank ${\bf r}(\Sigma),$ the sample size $n$ and the degree of H\"older smoothness $s$ of functional $f$ are studied. In particular, it is shown that, if ${\bf r}(\Sigma)\lesssim n^{\alpha}$ for some $\alpha\in (0,1)$ and $s\geq \frac{1}{1-\alpha},$ then the classical $\sqrt{n}$-rate is attainable and, if $s> \frac{1}{1-\alpha},$ then asymptotic normality and asymptotic efficiency of the resulting estimators hold. Previously, the results of this type (for different estimators) were obtained only in the case of finite dimensional Euclidean space $E={\mathbb R}^d$ and for covariance operators $\Sigma$ whose spectrum is bounded away from zero (in which case, ${\bf r}(\Sigma)\asymp d$).
This paper shows how to use the shooting method, a classical numerical algorithm for solving boundary value problems, to compute the Riemannian distance on the Stiefel manifold $\mathrm{St}(n,p)$, the set of $ n \times p $ matrices with orthonormal columns. The main feature is that we provide neat, explicit expressions for the Jacobians. To the author's knowledge, this is the first time some explicit formulas are given for the Jacobians involved in the shooting methods to find the distance between two given points on the Stiefel manifold. This allows us to perform a preliminary analysis for the single shooting method. Numerical experiments demonstrate the algorithms in terms of accuracy and performance. Finally, we showcase three example applications in summary statistics, shape analysis, and model order reduction.
We prove that if $X,Y$ are positive, independent, non-Dirac random variables and if for $\alpha,\beta\ge 0$, $\alpha\neq \beta$, $$ \psi_{\alpha,\beta}(x,y)=\left(y\,\tfrac{1+\beta(x+y)}{1+\alpha x+\beta y},\;x\,\tfrac{1+\alpha(x+y)}{1+\alpha x+\beta y}\right), $$ then the random variables $U$ and $V$ defined by $(U,V)=\psi_{\alpha,\beta}(X,Y)$ are independent if and only if $X$ and $Y$ follow Kummer distributions with suitably related parameters. In other words, any invariant measure for a lattice recursion model governed by $\psi_{\alpha,\beta}$ in the scheme introduced by Croydon and Sasada in \cite{CS2020}, is necessarily a product measure with Kummer marginals. The result extends earlier characterizations of Kummer and gamma laws by independence of $$ U=\tfrac{Y}{1+X}\quad\mbox{and}\quad V= X\left(1+\tfrac{Y}{1+X}\right), $$ which corresponds to the case of $\psi_{1,0}$. We also show that this independence property of Kummer laws covers, as limiting cases, several independence models known in the literature: the Lukacs, the Kummer-Gamma, the Matsumoto-Yor and the discrete Korteweg de Vries ones.
Hashing has been widely used in approximate nearest search for large-scale database retrieval for its computation and storage efficiency. Deep hashing, which devises convolutional neural network architecture to exploit and extract the semantic information or feature of images, has received increasing attention recently. In this survey, several deep supervised hashing methods for image retrieval are evaluated and I conclude three main different directions for deep supervised hashing methods. Several comments are made at the end. Moreover, to break through the bottleneck of the existing hashing methods, I propose a Shadow Recurrent Hashing(SRH) method as a try. Specifically, I devise a CNN architecture to extract the semantic features of images and design a loss function to encourage similar images projected close. To this end, I propose a concept: shadow of the CNN output. During optimization process, the CNN output and its shadow are guiding each other so as to achieve the optimal solution as much as possible. Several experiments on dataset CIFAR-10 show the satisfying performance of SRH.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191