Cover-based bounds on the numerical rank of Gaussian kernels

A popular approach for analyzing high-dimensional datasets is to perform dimensionality reduction by applying non-parametric affinity kernels. Usually, it is assumed that the represented affinities are related to an underlying low-dimensional manifold from which the data is sampled. This approach works under the assumption that, due to the low-dimensionality of the underlying manifold, the kernel has a low numerical rank. Essentially, this means that the kernel can be represented by a small set of numerically-significant eigenvalues and their corresponding eigenvectors.We present an upper bound for the numerical rank of Gaussian convolution operators, which are commonly used as kernels by spectral manifold-learning methods. The achieved bound is based on the underlying geometry that is provided by the manifold from which the dataset is assumed to be sampled. The bound can be used to determine the number of significant eigenvalues/eigenvectors that are needed for spectral analysis purposes. Furthermore, the results in this paper provide a relation between the underlying geometry of the manifold (or dataset) and the numerical rank of its Gaussian affinities.The term cover-based bound is used because the computations of this bound are done by using a finite set of small constant-volume boxes that cover the underlying manifold (or the dataset). We present bounds for finite Gaussian kernel matrices as well as for the continuous Gaussian convolution operator. We explore and demonstrate the relations between the bounds that are achieved for finite and continuous cases. The cover-oriented methodology is also used to provide a relation between the geodesic length of a curve and the numerical rank of Gaussian kernel of datasets that are sampled from it.     

Lower bounds for combinatorial problems on graphs

Nontrivial lower bounds are given for the computation time of various combinatorial problems on graphs under a linear or algebraic decision tree model. An $\text{Ω(n}{}^3\text{log}\text{n)}$ bound is obtained for a “travelling salesman problem” on a weighted complete graph of n vertices. Moreover it is shown that the same bound is valid for the “subgraph detection problem” with respect to property P if P is hereditary and determined by components. Thus an $\text{Ω(n}{}^3\text{log}\text{n)}$ bound is established in a unified way for a rather large class of problems.     

The effect of redundancy on probability bounds

Lower bounds on the probability of a union obtained by applying optimal bounds to subsets of events can provide excellent bounds. Comparisons are made with bounds obtained by linear programming and in the cases considered, the best bound is obtained with a subset that contains no redundant events contributing to the union. It is shown that redundant events may increase or decrease the value of a lower bound but surprisingly even removal of a non-redundant event can increase the bound.     

Improved processor bounds for combinatorial problems in RNC

Our main result improves the known processor bound by a factor ofn ⁴ (maintaining the expected parallel running time,O(log³ n)) for the following important problem:find a perfect matching in a general or in a bipartite graph with n vertices. A solution to that problem is used in parallel algorithms for several combinatorial problems, in particular for the problems of finding i) a (perfect) matching of maximum weight, ii) a maximum cardinality matching, iii) a matching of maximum vertex weight, iv) a maximums-t flow in a digraph with unit edge capacities. Consequently the known algorithms for those problems are substantially improved.The results of this paper have been presented at the 26-th Annual IEEE Symp. FOCS, Portland, Oregon (October 1985).Partially supported by NSF Grants MCS 8303139 and DCR 8511713.Supporeted by NSF Grants MCS 8203232 and DCR 8507573.     

Computational bounds for local search in combinatorial optimization

The results related to finding local optima in combinatorial optimization are overviewed. The class of polynomial-time local search problems (class PLS) is considered. By analogy with Cook’s theorem, the existence of most complicated problems in this class is established. The number of steps in local descent algorithms is estimated in the worst and average cases. The local search determination of exact and approximate solutions with guaranteed error bounds is discussed.     

Two-sided combinatorial volume bounds for non-obtuse hyperbolic polyhedra

We give a method for computing upper and lower bounds for the volume of a non-obtuse hyperbolic polyhedron in terms of the combinatorics of the 1-skeleton. We introduce an algorithm that detects the geometric decomposition of good 3-orbifolds with planar singular locus and underlying manifold S ³. The volume bounds follow from techniques related to the proof of Thurston’s Orbifold Theorem, Schläfli’s formula, and previous results of the author giving volume bounds for right-angled hyperbolic polyhedra.     

Upper bounds on probability thresholds for asymmetric Ramsey properties

Given two graphs G and H, we investigate for which functions the random graph (the binomial random graph on n vertices with edge probability p) satisfies with probability that every red‐blue‐coloring of its edges contains a red copy of G or a blue copy of H. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which G and H are complete graphs of arbitrary size. In our proof we present an alternative to the so‐called deletion method, which was introduced by Rödl and Ruciński in their study of symmetric Ramsey properties of random graphs (i.e. the case G = H), and has been used in many proofs of similar results since then.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 1–28, 2014     

Minimizing loss probability bounds for portfolio selection

In this paper, we derive a portfolio optimization model by minimizing upper and lower bounds of loss probability. These bounds are obtained under a nonparametric assumption of underlying return distribution by modifying the so-called generalization error bounds for the support vector machine, which has been developed in the field of statistical learning. Based on the bounds, two fractional programs are derived for constructing portfolios, where the numerator of the ratio in the objective includes the value-at-risk (VaR) or conditional value-at-risk (CVaR) while the denominator is any norm of portfolio vector. Depending on the parameter values in the model, the derived formulations can result in a nonconvex constrained optimization, and an algorithm for dealing with such a case is proposed. Some computational experiments are conducted on real stock market data, demonstrating that the CVaR-based fractional programming model outperforms the empirical probability minimization.     

Improving probability bounds by optimization over subsets

The simple device of maximization over subsets of events can provide substantial improvement over the Dawson-Sankoff degree two lower bound on the probability of a union of events and can also exceed a sharper bound that uses individual and pairwise joint event probabilities developed by Kuai, Alajaji, and Takahara. In each of their examples, the maximized bound achieves the exact probability of the union using a subset of events containing no redundant events of the original set of events.     

Polynomial bounds for probability generating functions. II

Summary Consider the set of proper probability distributions on the nonnegative integers having the first k moments (fixed) in common. It is desired to find the element of this set whose corresponding probability generating function (p.g.f.) lies entirely above or below the others. Using convexity arguments, it is shown that the extremal distribution exists, is unique, and is necessarily an element of a certain subclass of the class of all (k + 1)-point distributions. This subclass is entirely characterized by the geometrical properties of its set of support. The alternation of upper and lower bounds with the parity of k is also explained. There is mention of how the techniques developed here apply to more general discrete optimization problems, and the connection with the theory of cyclic polytopes is also discussed.This work was partially supported by Army Research Office Grant #DAHCO 04-74-G-0178 awarded to the Department of Statistics, Princeton University     

Bond percolation critical probability bounds for three Archimedean lattices

Rigorous bounds for the bond percolation critical probability are determined for three Archimedean lattices: .7385 < p_c((3, 12²) bond) < .7449, .6430 < p_c((4, 6, 12) bond) < .7376, .6281 < p_c((4, 8²) bond) < .7201. Consequently, the bond percolation critical probability of the (3, 12²) lattice is strictly larger than those of the other ten Archimedean lattices. Thus, the (3, 12²) bond percolation critical probability is possibly the largest of any vertex‐transitive graph with bond percolation critical probability that is strictly less than one. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 507–518, 2002     

The union of minimal hitting sets: Parameterized combinatorial bounds and counting

A k-hitting set in a hypergraph is a set of at most k vertices that intersects all hyperedges. We study the union of all inclusion-minimal k-hitting sets in hypergraphs of rank r (where the rank is the maximum size of hyperedges). We show that this union is relevant for certain combinatorial inference problems and give worst-case bounds on its size, depending on r and k. For r=2 our result is tight, and for each r3 we have an asymptotically optimal bound and make progress regarding the constant factor. The exact worst-case size for r3 remains an open problem. We also propose an algorithm for counting all k-hitting sets in hypergraphs of rank r. Its asymptotic runtime matches the best one known for the much more special problem of finding one k-hitting set. The results are used for efficient counting of k-hitting sets that contain any particular vertex.     

Sharp probability bounds for the binomial moment problem with symmetry

Sharp bounds in terms of the first few binomial moments are found for the probability of a union of events, when the random variable denoting the number of events that occur follows symmetric distribution. Connection between the bounds of this paper and the bounds from a special case of the binomial moment problem of Prekopa (1995) is shown. As a special case, bounds for the probability when the underlying probability distribution is unimodal-symmetric are also found.     

Heat kernel bounds,conservation of probability and the feller property

Dedicated to Professor Shmuel Agmon     

Computing bounds for the probability of the union of events by different methods

Let A ₁,??,A _n be arbitrary events. The underlying problem is to give lower and upper bounds on the probability P(A ₁?????A _n ) based on $P(A_{i_{1}}\cap\cdots\cap A_{i_{k}})$ , 1??i ₁<?<i _k ??n, where k=1,??,d, and d??n (usually d?n) is a certain integer, called the order of the problem or the bound. Most bounding techniques fall in one of the following two main categories: those that use (hyper)graph structures and the ones based on binomial moment problems. In this paper we compare bounds from the two categories with each other, in particular the bounds yielded by univariate and multivariate moment problems are compared with Bukszár??s hypermultitree bounds. In the comparison we considered several numerical examples, most of which have important practical applications, e.g., the approximation of the values of multivariate cumulative distribution functions or the calculation of network reliability. We compare the bounds based on how close they are to the real value and the time required to compute them, however, the problems arising in the implementations of the methods as well as the limitations of the usability of the bounds are also illustrated.     

Improved upper bounds for the critical probability of oriented percolation in two dimensions

We refine the method of our previous paper [2] which gave upper bounds for the critical probability in two-dimensional oriented percolation. We use our refinement to show that © 1994 John Wiley & Sons, Inc.