In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$. This result is best possible, and improves a logarithmic lower bound shown by Chung, F\"uredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

We define the notion of a Ricci curvature lower bound for parametrized statistical models. Following the seminal ideas of Lott–Sturm–Villani, we define this notion based on the geodesic convexity of the Kullback–Leibler divergence in a Wasserstein statistical manifold, that is, a manifold of probability distributions endowed with a Wasserstein metric tensor structure. Within these definitions, which are based on Fisher information matrix and Wasserstein Christoffel symbols, the Ricci curvature is related to both, information geometry and Wasserstein geometry. These definitions allow us to formulate bounds on the convergence rate of Wasserstein gradient flows and information functional inequalities in parameter space. We discuss examples of Ricci curvature lower bounds and convergence rates in exponential family models.

We study a non-convex low-rank promoting penalty function, the transformed Schatten- 1 (TS1), and its applications in matrix completion. The TS1 penalty, as a matrix quasi-norm defined on its singular values, interpolates the rank and the nuclear norm through a nonnegative parameter a∈ (0,+∞). We consider the unconstrained TS1 regularized low-rank matrix recovery problem and develop a fixed point representation for its global minimizer. The TS1 thresholding functions are in closed analytical form for all parameter values. The TS1 threshold values differ in subcritical (supercritical) parameter regime where the TS1 threshold functions are continuous (discontinuous). We propose TS1 iterative thresholding algorithms and compare them with some state-of-the-art algorithms on matrix completion test problems. For problems with known rank, a fully adaptive TS1 iterative thresholding algorithm consistently performs the best under different conditions, where ground truth matrices are generated by multivariate Gaussian, (0,1) uniform and Chi-square distributions. For problems with unknown rank, TS1 algorithms with an additional rank estimation procedure approach the level of IRucL-q which is an iterative reweighted algorithm, non-convex in nature and best in performance.

We study inhomogeneous random graphs in the subcritical case. Among other results, we derive an exact formula for the size of the largest connected component scaled by log$n$, with$n$being the size of the graph. This generalizes a result for the “rank-1 case”. We also investigate branching processes associated with these graphs. In particular, we discover that the same well-known equation for the survival probability, whose positive solution determines the asymptotics of the size of the largest component in the supercritical case, also plays a crucial role in the subcritical case. However, now it is the$negative$solutions that come into play. We disclose their relationship to the distribution of the progeny of the branching process.

A computational method, based on l1-minimization, is proposed for the problem of link flow correction, when the available traffic flow data on many links in a road network are inconsistent with respect to the flow conservation law. Without extra information, the problem is generally ill-posed when a large portion of the link sensors are unhealthy. It is possible, however, to correct the corrupted link flows accurately with the proposed method under a recoverability condition if there are only a few bad sensors which are located at certain links. We analytically identify the links that are robust to miscounts and relate them to the geometric structure of the traffic network by introducing the recoverability concept and an algorithm for computing it. The recoverability condition for corrupted links is simply the associated recoverability being greater than 1. In a more realistic setting, besides the unhealthy link sensors, small measurement noises may be present at the other sensors. Under the same recoverability condition, our method guarantees to give an estimated traffic flow fairly close to the ground-truth data and leads to a bound for the correction error. Both synthetic and real-world examples are provided to demonstrate the effectiveness of the proposed method.

We present LBW-Net, an efficient optimization based method for quantization and training of the low bit-width convolutional neural networks (CNNs). Specifically, we quantize the weights to zero or powers of two by minimizing the Euclidean distance between full-precision weights and quantized weights during backpropagation. We characterize the combinatorial nature of the low bit-width quantization problem. For 2-bit (ternary) CNNs, the quantization of N weights can be done by an exact formula in O(N log N ) complexity. When the bit-width is three and above, we further propose a semi-analytical thresholding scheme with a single free parameter for quantization that is computationally inexpensive. The free parameter is further determined by network retraining and object detection tests. LBW-Net has several desirable advantages over full-precision CNNs, including considerable memory savings, energy efficiency, and faster deployment. Our experiments on PASCAL VOC dataset show that compared with its 32-bit floating-point counterpart, the performance of the 6-bit LBW-Net is nearly lossless in the object detection tasks, and can even do better in some real world visual scenes, while empirically enjoying more than 4× faster deployment.

No abstract uploaded!

We propose a numerical approach to solve variational problems on manifolds represented by the grid based particle method (GBPM) recently developed in Leung et al. (J. Comput. Phys. 230(7):25402561, 2011), Leung and Zhao (J. Comput. Phys. 228:77067728, 2009a, J. Comput. Phys. 228:29933024, 2009b, Commun. Comput. Phys. 8:758796, 2010). In particular, we propose a splitting algorithm for image segmentation on manifolds represented by unconnected sampling particles. To develop a fast minimization algorithm, we propose a new splitting method by generalizing the augmented Lagrangian method. To efficiently implement the resulting method, we incorporate with the local polynomial approximations of the manifold in the GBPM. The resulting method is flexible for segmentation on various manifolds including closed or open or even surfaces which are not orientable.