Global Error Bounds for <Emphasis Type="Italic">γ</Emphasis>-paraconvex Multifunctions

In this paper, error bounds for γ-paraconvex multifunctions are considered. A Robinson-Ursescu type Theorem is given in normed spaces. Some results on the existence of global error bounds are presented. Perturbation error bounds are also studied.     

On Ostrowski’s disk theorem and lower bounds for the smallest eigenvalues and singular values

The paper refines the classical Ostrowski disk theorem and suggests lower bounds for the smallest-in-modulus eigenvalue and the smallest singular value of a square matrix under certain diagonal dominance conditions. A lower bound for the smallest-in-modulus eigenvalue of a product of m ≥ 2 matrices satisfying joint diagonal dominance conditions is obtained. The particular cases of the bounds suggested that correspond to the infinity norm are discussed separately and compared with some known results. Bibliography: 8 titles.     

On the number of edges in the transitive closure of a graph

A property of the square sum of partitions of integers is investigated. The square sum has a direct relation to the number of edges in the transitive closure of a graph. This paper is concerned with the problem of determining the minimum missing value in the sequence of square sums. Asymptotically tight lower and upper bounds on this value are obtained. A consequence of the main result for closure size prediction is also mentioned.     

Some results on the nonstationary ideal II

This paper is a continuation of [Gi]. We show that the upper bound of [Gi] on the strength of NS _μ ⁺ precipitous for a regular μ is exact. The upper bounds on the strength of NS_κ precipitous for inaccessible κ are reduced quite close to the lower bounds.     

Bounds and inequalities for the Perron root of a nonnegative matrix. III. Bounds dependent on simple paths and circuits

The paper presents new upper and lower bounds for the Perron root of a nonnegative matrix in terms of the simple circuits of length not exceeding k and the simple paths of length k, 1 ≤ k ≤ n, in the directed graph of the matrix. For each k, 1 ≤ k ≤ n, these bounds are intermediate between the circuit bounds and the path-dependent bounds suggested previously, and for k = 1 and k = n they reduce to the corresponding path-dependent bounds and the circuit bounds, respectively. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 69–93.     

Sharp Estimates for the Global Attractor of Scalar Reaction–Diffusion Equations with a Wentzell Boundary Condition

In this paper, we derive optimal upper and lower bounds on the dimension of the attractor A_W\mathcal{A}_{\mathrm{W}} for scalar reaction–diffusion equations with a Wentzell (dynamic) boundary condition. We are also interested in obtaining explicit bounds on the constants involved in our asymptotic estimates, and to compare these bounds to previously known estimates for the dimension of the global attractor A_K\mathcal{A}_{K}, K∈{D,N,P}, of reaction–diffusion equations subject to Dirichlet, Neumann and periodic boundary conditions. The explicit estimates we obtain show that the dimension of the global attractor A_W\mathcal {A}_{\mathrm{W}} is of different order than the dimension of A_K\mathcal{A}_{K}, for each K∈{D,N,P}, in all space dimensions that are greater than or equal to three.     

Overflow and losses in a network queue with a self-similar input

This paper considers a discrete time queuing system that models a communication network multiplexer which is fed by a self-similar packet traffic. The model has a finite buffer of size h, a number of servers with unit service time, and an input traffic which is an aggregation of independent source-active periods having Pareto-distributed lengths and arriving as Poisson batches. The new asymptotic upper and lower bounds to the buffer-overflow and packet-loss probabilities P are obtained. The bounds give an exact asymptotic of log P/log h when h → to ∞. These bounds decay algebraically slow with buffer-size growth and exponentially fast with excess of channel capacity over traffic rate. Such behavior of the probabilities shows that one can better combat traffic losses in communication networks by increasing channel capacity rather than buffer size. A comparison of the obtained bounds and the known upper and lower bounds is done. This revised version was published online in June 2006 with corrections to the Cover Date.     

Designs in Product Association Schemes

A number of important families of association schemes—such as the Hamming and Johnson schemes—enjoy the property that, in each member of the family, Delsarte t-designs can be characterised combinatorially as designs in a certain partially ordered set attached to the scheme. In this paper, we extend this characterisation to designs in a product association scheme each of whose components admits a characterisation of the above type. As a consequence of our main result, we immediately obtain linear programming bounds for a wide variety of combinatorial objects as well as bounds on the size and degree of such designs analogous to Delsarte's bounds for t-designs in Q-polynomial association schemes.     

New and old bounds for standard quadratic optimization: dominance,equivalence and incomparability

A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. Among the problems which can be transformed into a StQP are the general quadratic problem over a polytope, and the maximum clique problem in a graph. In this paper we present several new polynomial-time bounds for StQP ranging from very simple and cheap ones to more complex and tight constructions. The main tools employed in the conception and analysis of most bounds are Semidefinite Programming and decomposition of the objective function into a sum of two quadratic functions, each of which is easy to minimize. We provide a complete diagram of the dominance, incomparability, or equivalence relations among the bounds proposed in this and in previous works. In particular, we show that one of our new bounds dominates all the others. Furthermore, a specialization of such bound dominates Schrijver’s improvement of Lovász’s θ function bound for the maximum size of a clique in a graph.      

On contraction properties of Markov kernels

 We study Lipschitz contraction properties of general Markov kernels seen as operators on spaces of probability measures equipped with entropy-like ``distances'. Universal quantitative bounds on the associated ergodic constants are deduced from Dobrushin's ergodic coefficient. Strong contraction properties in Orlicz spaces for relative densities are proved under more restrictive mixing assumptions. We also describe contraction bounds in the entropy sense around arbitrary probability measures by introducing a suitable Dirichlet form and the corresponding modified logarithmic Sobolev constants. The interest in these bounds is illustrated on the example of inhomogeneous Gaussian chains. In particular, the existence of an invariant measure is not required in general. Received: 31 October 2000 / Revised version: 21 February 2003 / Published online: 12 May 2003 L. Miclo also thanks the hospitality and support of the Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brasil, where part of this work was done. Mathematics Subject Classification (2000): 60J05, 60J22, 37A30, 37A25, 39A11, 39A12, 46E39, 28A33, 47D07 Key words or phrases: Lipschitz contraction – Generalized relative entropy – Markov kernel – Dobrushin's ergodic coefficient – Orlicz norm – Dirichlet form – Spectral gap – Modified logarithmic Sobolev inequality – Inhomogeneous Gaussian chains – Loose of memory property     

On nonparametric classification with missing covariates

General procedures are proposed for nonparametric classification in the presence of missing covariates. Both kernel-based imputation as well as Horvitz-Thompson-type inverse weighting approaches are employed to handle the presence of missing covariates. In the case of imputation, it is a certain regression function which is being imputed (and not the missing values). Using the theory of empirical processes, the performance of the resulting classifiers is assessed by obtaining exponential bounds on the deviations of their conditional errors from that of the Bayes classifier. These bounds, in conjunction with the Borel-Cantelli lemma, immediately provide various strong consistency results.     

The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm

This paper is concerned with the minimum cost flow problem. It is shown that the class of dual algorithms which solve this problem consists of different variants of a common general algorithm. We develop a new variant which is, in fact, a new form of the ‘primal-dual algorithm’ and which has several interesting properties. It uses, explicitly only dual variables. The slope of the change in the (dual) objective is monotone. The bound on the maximum number of iterations to solve a problem with integral bounds on the flow is better than bounds for other algorithms. This paper is part of the author's doctoral dissertation submitted at Yale University.     

Polygons Needing Many Flipturns

A flipturn on a polygon consists of reversing the order of edges inside a pocket of the polygon, without changing lengths or slopes. Any polygon with n edges must be convexified after at most (n − 1)! flipturns. A recent paper showed that in fact it will be convex after at most n(n−3)/2 flipturns.We give here lower bounds.We construct a polygon such that if pockets are chosen in a bad way, at least (n − 2)²/4 flipturns are needed to convexify the polygon. In another construction, (n −1)²/8 flipturns are needed, regardless of the order in which pockets are chosen. All our bounds are adaptive to a pre-specified number of distinct slopes of the edges.     

Decentralized Adaptive Robust Tracking and Model Following for Large-Scale Systems Including Delayed State Perturbations in the Interconnections

The problem of decentralized robust tracking and model following is considered for a class of uncertain large-scale systems including delayed state perturbations in the interconnections. In this paper, it is assumed that the upper bounds of the delayed state perturbations, uncertainties, and external disturbances are unknown. A modified adaptation law with σ-modification is introduced to estimate such unknown bounds, and on the basis of the updated values of these unknown bounds, a class of decentralized local memoryless state feedback controllers is constructed for robust tracking of dynamical signals. The proposed decentralized adaptive robust tracking controllers can guarantee that the tracking errors between each time-delay subsystem and the corresponding local reference model without time-delay decrease uniformly asymptotically to zero. Finally, a numerical example is given to demonstrate the validity of the results.     

Convergence of CG and GMRES on a tridiagonal Toeplitz linear system

The Conjugate Gradient method (CG), the Minimal Residual method (MINRES), or more generally, the Generalized Minimal Residual method (GMRES) are widely used to solve a linear system Ax=b. The choice of a method depends on A’s symmetry property and/or definiteness), and MINRES is really just a special case of GMRES. This paper establishes error bounds on and sometimes exact expressions for residuals of CG, MINRES, and GMRES on solving a tridiagonal Toeplitz linear system, where A is Hermitian or just normal. These expressions and bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first or second kind. AMS subject classification (2000)  65F10, 65N22     

Some results on lower variance bounds useful in reliability modeling and estimation

In the present paper a general theorem that links characterizations of discrete life distributions based on relationship between failure rate and conditional expectations with those in terms of Chernoff-type inequalities is proposed. Exact expression for lower bounds to the variance is calculated for distributions belonging to the modified power series family, Ord family and mixture geometric models. It is shown that the bounds obtained here contain the Cramer–Rao and Chapman–Robbins inequalities as special cases. An application of the results to real data is also provided.     

Sigma–delta quantization errors and the traveling salesman problem

In transmission, storaging and coding of digital signals we frequently perform A/D conversion using quantization. In this paper we study the maximal and mean square errors as a result of quantization. We focus on the sigma–delta modulation quantization scheme in the finite frame expansion setting. We show that this problem is related to the classical Traveling Salesman Problem (TSP) in the Euclidean space. It is known [Benedetto et al., Sigma–delta () quantization and finite frames, IEEE Trans. Inform. Theory 52, 1990–2005 (2006)] that the error bounds from the sigma–delta scheme depends on the ordering of the frame elements. By examining a priori bounds for the Euclidean TSP we show that error bounds in the sigma–delta scheme is superior to those from the pulse code modulation (PCM) scheme in general. We also give a recursive algorithm for finding an ordering of the frame elements that will lead to good maximal error and mean square error. Supported in part by the National Science Foundation grant DMS-0139261.     

Estimates on polynomial exponential sums

In this paper we establish new bounds on exponential sums of high degree for general composite moduli. The sums considered are either Gauss sums or ‘sparse’ and we rely on earlier work in the case of prime modulus.     

Generalized qd algorithm and Markov–Bernstein inequalities for Jacobi weight

The Markov–Bernstein inequalities for the Jacobi measure remained to be studied in detail. Indeed the tools used for obtaining lower and upper bounds of the constant which appear in these inequalities, did not work, since it is linked with the smallest eigenvalue of a five diagonal positive definite symmetric matrix. The aim of this paper is to generalize the qd algorithm for positive definite symmetric band matrices and to give the mean to expand the determinant of a five diagonal symmetric matrix. After that these new tools are applied to the problem to produce effective lower and upper bounds of the Markov–Bernstein constant in the Jacobi case. In the last part we com pare, in the particular case of the Gegenbauer measure, the lower and upper bounds which can be deduced from this paper, with those given in Draux and Elhami (Comput J Appl Math 106:203–243, 1999) and Draux (Numer Algor 24:31–58, 2000).      

Strong bounds on perturbations

This paper provides strong bounds on perturbations over a collection of independent random variables, where ‘strong’ has to be understood as uniform w.r.t. some functional norm. Our analysis is based on studying the concept of weak differentiability. By applying a fundamental result from the theory of Banach spaces, we show that weak differentiability implies norm Lipschitz continuity. This result leads to bounds on the sensitivity of finite products of probability measures, in norm sense. We apply our results to derive bounds on perturbations for the transient waiting times in a G/G/1 queue. This research is supported by the Technology Foundation STW, applied science division of NWO and the technology programme of the Ministry of Economic Affairs.