Exponential inequalities for sums of random vectors

This paper presents some generalizations of S. N. Bernstein's exponential bounds on probabilities of large deviations to the vector case. Inequalities for probabilities of large deviations of sums of independent random vectors are derived under a Cramér's type restriction on the rate of growth of absolute moments of the summands. Estimates are obtained for random vectors with values in Banach space, Sharper bounds hold in the case of finite-dimensional Euclidean or separable Hilbert spaces.     

Analytic hypoellipticity for sums of squares and the Treves conjecture

We are concerned with the problem of real analytic regularity of the solutions of sums of squares with real analytic coefficients. Treves conjecture states that an operator of this type is analytic hypoelliptic if and only if all the strata in the Poisson–Treves stratification are symplectic.We produce a model operator, $P_1$, having a single symplectic stratum and prove that it is Gevrey $s_0$ hypoelliptic and not better. See Theorem 2.1 for a definition of $s_0$. We also show that this phenomenon has a microlocal character.We point out explicitly that this is a counterexample to the sufficient part of Treves conjecture and not to the necessary part, which is still an open problem.     

Linear restrictions and two step least squares with applications

In this paper we consider the full rank regression model with arbitrary covariance matrix: Y = Xß + ε. It is shown that the effect of restricting the information Y to T = A′Y may be analyzed through an associatedi regression problem which is amenable to solution by two step least squares. The results are applied to the important case of missing observations, where some classical results are rederived.     

Sums of squares based approximation algorithms for MAX-SAT

We investigate the Semidefinite Programming based sums of squares (SOS) decomposition method, designed for global optimization of polynomials, in the context of the (Maximum) Satisfiability problem. To be specific, we examine the potential of this theory for providing tests for unsatisfiability and providing MAX-SAT upper bounds. We compare the SOS approach with existing upper bound and rounding techniques for the MAX-2-SAT case of Goemans and Williamson [Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42(6) (1995) 1115-1145] and Feige and Goemans [Approximating the value of two prover proof systems, with applications to MAX2SAT and MAXDICUT, in: Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182-189] and the MAX-3-SAT case of Karloff and Zwick [A 7/8-approximation algorithm for MAX 3SAT? in: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, USA, IEEE Press, New York, 1997], which are based on Semidefinite Programming as well. We prove that for each of these algorithms there is an SOS-based counterpart which provides upper bounds at least as tight, but observably tighter in particular cases. Also, we propose a new randomized rounding technique based on the optimal solution of the SOS Semidefinite Program (SDP) which we experimentally compare with the appropriate existing rounding techniques. Further we investigate the implications to the decision variant SAT and compare experimental results with those yielded from the higher lifting approach of Anjos [On semidefinite programming relaxations for the satisfiability problem, Math. Methods Oper. Res. 60(3) (2004) 349-367; An improved semidefinite programming relaxation for the satisfiability problem, Math. Programming 102(3) (2005) 589-608; Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems, J. Satisfiability Boolean Modeling Comput. 1 (2005) 1-47].We give some impression of the fraction of the so-called unit constraints in the various SDP relaxations. From a mathematical viewpoint these constraints should be easily dealt within an algorithmic setting, but seem hard to be avoided as extra constraints in an SDP setting. Finally, we briefly indicate whether this work could have implications in finding counterexamples to uncovered cases in Hilbert's Positivstellensatz.     

Robin特征值问题与含边界项的Hardy型积分不等式

在H~1(Ω)中,基于紧性原理和变分方法,讨论Robin边界条件下椭圆特征值问题的解,获得了一个新的带边界项的Hardy型不等式.     

Regressions for sums of squares of spacings

Starting with a new formula for the regression of sum of squares of spacings (SSS) with respect to the maximum we present a characterization of a family of beta type mixtures in terms of the constancy of regression of normalized SSS of order statistics. Related characterization for records describes a family of minima of independent Weibull distributions.     

Strict inequality of Robin eigenvalues for elliptic differential operators on Lipschitz domains

On a bounded Lipschitz domain we consider two selfadjoint operator realizations of the same second order elliptic differential expression subject to Robin boundary conditions, where the coefficients in the boundary conditions are functions. We prove that inequality between these functions on the boundary implies strict inequality between the eigenvalues of the two operators, provided that the inequality of the functions in the boundary conditions is strict on an arbitrarily small nonempty, open set.     

Vertex PI indices of four sums of graphs

Suppose that e is an edge of a graph G. Denote by m_e(G) the number of vertices of G that are not equidistant from both ends of e. Then the vertex PI index of G is defined as the summation of m_e(G) over all edges e of G. In this paper we give the explicit expressions for the vertex PI indices of four sums of two graphs in terms of other indices of two individual graphs, which correct the main results in a paper published in Ars Combin. 98 (2011).     

On some discrete inequalities in two independent variables

In this paper we establish some new nonlinear difference inequalities. We also present an application of one inequality to certain nonlinear sum-difference equation.     

Nonlocal Robin Laplacians and some remarks on a paper by Filonov on eigenvalue inequalities

The aim of this paper is twofold: First, we characterize an essentially optimal class of boundary operators Θ which give rise to self-adjoint Laplacians −ΔΘ,Ω in L²(Ω;dnx) with (nonlocal and local) Robin-type boundary conditions on bounded Lipschitz domains Ω⊂Rn, n∈N, n?2. Second, we extend Friedlander's inequalities between Neumann and Dirichlet Laplacian eigenvalues to those between nonlocal Robin and Dirichlet Laplacian eigenvalues associated with bounded Lipschitz domains Ω, following an approach introduced by Filonov for this type of problems.     

On stable least squares solution to the system of linear inequalities

The system of inequalities is transformed to the least squares problem on the positive ortant. This problem is solved using orthogonal transformations which are memorized as products. Author’s previous paper presented a method where at each step all the coefficients of the system were transformed. This paper describes a method applicable also to large matrices. Like in revised simplex method, in this method an auxiliary matrix is used for the computations. The algorithm is suitable for unstable and degenerate problems primarily.      

On the number of primitive representations of integers as sums of squares

Formulas for the number of primitive representations of any integer n as a sum of k squares are given, for 2 ≤ k ≤ 8, and for certain values of n, for 9 ≤ k ≤ 12. The formulas have a similar structure and are striking for their simplicity. Dedicated to Richard Askey on the occasion of his 70th birthday. 2000 Mathematics Subject Classification Primary—11E25; Secondary—05A15, 33E05.     

The Nicolas and Robin inequalities with sums of two squares

In 1984, G. Robin proved that the Riemann hypothesis is true if and only if the Robin inequality σ(n) < e ^γ n log log n holds for every integer n > 5040, where σ(n) is the sum of divisors function, and γ is the Euler–Mascheroni constant. We exhibit a broad class of subsets S{\mathcal {S}} of the natural numbers such that the Robin inequality holds for all but finitely many n ? S{n \in \mathcal {S}} . As a special case, we determine the finitely many numbers of the form n = a ² + b ² that do not satisfy the Robin inequality. In fact, we prove our assertions with the Nicolas inequality n/φ(n) < e ^γ log log n; since σ(n)/n < n/φ(n) for n > 1 our results for the Robin inequality follow at once.     

Nonnegative functions as squares or sums of squares

We prove that, for n?4, there are C^∞ nonnegative functions f of n variables (and even flat ones for n?5) which are not a finite sum of squares of C² functions. For n=1, where a decomposition in a sum of two squares is always possible, we investigate the possibility of writing f=g². We prove that, in general, one cannot require a better regularity than g∈C¹. Assuming that f vanishes at all its local minima, we prove that it is possible to get g∈C² but that one cannot require any additional regularity.     

On sums of squares of k-nomials

In 2005, Boman et al. introduced the concept of factor width for a real symmetric positive semidefinite matrix. This is the smallest positive integer k for which the matrix A can be written as $A=V{V}^T$ with each column of V containing at most k non-zeros. The cones of matrices of bounded factor width give a hierarchy of inner approximations to the PSD cone. In the polynomial optimization context, a Gram matrix of a polynomial having factor width k corresponds to the polynomial being a sum of squares of polynomials of support at most k. Recently, Ahmadi and Majumdar [1], explored this connection for case $k=2$ and proposed to relax the reliance on polynomials that are sums of squares in semidefinite programming to polynomials that are sums of binomial squares In this paper, we prove some results on the geometry of the cones of matrices with bounded factor widths and their duals, and use them to derive new results on the limitations of certificates of nonnegativity of quadratic forms by sums of k-nomial squares using standard multipliers. In particular we show that they never help for symmetric quadratics, for any quadratic if $k=2$, and any quaternary quadratic if $k=3$. Furthermore we give some evidence that those are a complete list of such cases.     

Sparsity in sums of squares of polynomials

Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and semidefinite programming (SDP) relaxation of polynomial optimization problems. We discuss effective methods to obtain a simpler representation of a sparse polynomial as a sum of squares of sparse polynomials by eliminating redundancy.A considerable part of this work was conducted while this author was visiting Tokyo Institute of Technology. Research supported by Kosef R004-000-2001-00200Mathematics Subject Classification (1991): 90C22, 90C26, 90C30     

Non-existence of degree bounds for weighted sums of squares representations

Given a fixed family of polynomials , we study the problem of representing polynomials in the form

(*)

f=s₀+s₁h₁++s_rh_r