Asymptotic bounds for the expected L error of a multivariate kernel density estimator

The kernel estimator of a multivariate probability density function is studied. An asymptotic upper bound for the expected L¹ error of the estimator is derived. An asymptotic lower bound result and a formula for the exact asymptotic error are also given. The goodness of the smoothing parameter value derived by minimizing an explicit upper bound is examined in numerical simulations that consist of two different experiments. First, the L¹ error is estimated using numerical integration and, second, the effect of the choice of the smoothing parameter in discrimination tasks is studied.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

Bounding reflection length in an affine Coxeter group

In any Coxeter group, the conjugates of elements in the standard minimal generating set are called reflections, and the minimal number of reflections needed to factor a particular element is called its reflection length. In this article we prove that the reflection length function on an affine Coxeter group has a uniform upper bound. More precisely, we prove that the reflection length function on an affine Coxeter group that naturally acts faithfully and cocompactly on ℝ ⁿ is bounded above by 2n, and we also show that this bound is optimal. Conjecturally, spherical and affine Coxeter groups are the only Coxeter groups with a uniform bound on reflection length.     

On solving a D.C. programming problem by a sequence of linear programs

We are dealing with a numerical method for solving the problem of minimizing a difference of two convex functions (a d.c. function) over a closed convex set in ⁿ . This algorithm combines a new prismatic branch and bound technique with polyhedral outer approximation in such a way that only linear programming problems have to be solved.Parts of this research were accomplished while the third author was visiting the University of Trier, Germany, as a fellow of the Alexander von Humboldt foundation.     

On evaluating the rate function of large deviations for jump processes

This is a sequel to our joint paper^[4] in which upper bound estimates for large deviations for Markov chains are studied. The purpose of this paper is to characterize the rate function of large deviations for jump processes. In particular, an explicit expression of the rate function is given in the case of the process being symmetrizable.     

Fair upper bounds for the curvature in univariate convex interpolation

In convex interpolation the curvature of the interpolants should be as small as possible. We attack this problem by treating interpolation subject to bounds on the curvature. In view of the concexity the lower bound is equal to zero while the upper bound is assumed to be piecewise constant. The upper bounds are called fair with respect to a function class if the interpolation problem becomes solvable for all data sets in strictly convex position. We derive fair a priori bounds for classes of quadraticC ¹, cubicC ², and quarticC ³ splines on refined grids.     

D.C. Versus Copositive Bounds for Standard QP

The standard quadratic program (QPS) is min_xεΔx^TQx, where is the simplex Δ = {x ⩽ 0 ∣ ∑_i=1ⁿ x_i = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=S−T, where S and T are both positive semidefinite, and bounding x^T Sx (convex on Δ) and −x^Tx (concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound.     

Information Complexity of Multivariate Fredholm Integral Equations in Sobolev Classes

In this paper, the complexity of full solution of Fredholm integral equations of the second kind with data from the Sobolev classW^r₂is studied. The exact order of information complexity is derived. The lower bound is proved using a Gelfand number technique. The upper bound is shown by providing a concrete algorithm of optimal order, based on a specific hyperbolic cross approximation of the kernel function. Numerical experiments are included, comparing the optimal algorithm with the standard Galerkin method.     

On complexity of round transformations

A modern block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). Clearly, the most important attribute of a block cipher is its security. However, with respect to the hardware implementation, a good block cipher has to have a reasonable complexity as well. In this paper, we study complexity of round transformations satisfying some basic security criteria. There are several ways to define the complexity of a round transformation, and to choose “necessary” security criteria. It turns out, that for our purpose, it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. We require that the Boolean function F possesses some fundamental properties imposed on each block cipher for security reasons; namely, we require that the function is a strictly non-linear bijection and that it has a good diffusion. The total number of variables in the normal algebraic form of the component functions of F is taken as its complexity. We find the minimum complexity of such functions, and this way we establish a lower bound on complexity of all round transformations. To show that the lower bound is the best possible, we construct a round transformation F^′ attaining the bound. We stress that it is not an aspiration of this paper to construct a round transformation which would be of practical use; F^′ is useful only from the theoretical point of view.     

A dual algorithm for the one-machine scheduling problem

A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn ² and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.     

A family of three-point methods of optimal order for solving nonlinear equations

A family of three-point iterative methods for solving nonlinear equations is constructed using a suitable parametric function and two arbitrary real parameters. It is proved that these methods have the convergence order eight requiring only four function evaluations per iteration. In this way it is demonstrated that the proposed class of methods supports the Kung-Traub hypothesis (1974) [3] on the upper bound 2ⁿ of the order of multipoint methods based on n+1 function evaluations. Consequently, this class of root solvers possesses very high computational efficiency. Numerical examples are included to demonstrate exceptional convergence speed with only few function evaluations.     

Hermite pseudospectral approximations. An error estimate

We find an error bound for the pseudospectral approximation of a function in terms of Hermite functions, hn(x)=e−x²Hn(x), in certain weighted Sobolev spaces. We use properties of Hermite polynomials, as well as an asymptotic expression for their largest zeroes to achieve the mentioned estimate.     

The effect of random restrictions on formula size

We consider the formula size complexity of boolean functions over the base consisting of ∧, ∨, and ¬ gates. In 1961 Subbotovskaya proved that, for any boolean function on n variables, setting all but a randomly chosen ?n variables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor. This fact was used by Subbotovskaya to derive a lower bound of Ω(n^1.5) for the formula size of the parity function, and more recently by Andreev who exhibited at lower bound of ΩC(n^2.5/log^O(1)(n)) for a function in P. We present the first improvement of Subbotovskaya's result, showing that the expected formual complexity of a function restricted as above is at most an O(?^γ) franction of its original complexity, for This allows us to give an improved lower bound of Ω(n^2.556…) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP. © 1993 John Wiley & Sons, Inc.     

Persistence of Anderson localization in Schrödinger operators with decaying random potentials

We show persistence of both Anderson and dynamical localization in Schrödinger operators with non-positive (attractive) random decaying potential. We consider an Anderson-type Schrödinger operator with a non-positive ergodic random potential, and multiply the random potential by a decaying envelope function. If the envelope function decays slower than |x|^-2 at infinity, we prove that the operator has infinitely many eigenvalues below zero. For envelopes decaying as |x|^-α at infinity, we determine the number of bound states below a given energy E<0, asymptotically as α↓0. To show that bound states located at the bottom of the spectrum are related to the phenomenon of Anderson localization in the corresponding ergodic model, we prove: (a) these states are exponentially localized with a localization length that is uniform in the decay exponent α; (b) dynamical localization holds uniformly in α.     

Absolute uniqueness of minimal surfaces bounded by contours with a one-to-one projection onto a plane

In this paper the uniqueness of the always existing Douglas-Radó solution to Plateau’s Problem of finding a minimal surface of the type of the disc to a given rectifiable Jordan Curve Γ in ?³ is considered in combination with the question: When is the solution surface also a graph? So only contours with a one-to-one projection onto a plane are candidates. The uniqueness is generalized to all genera and orientations and the non orientable case and then called “absolute”. It is demonstrated, that if it we have a continuous family of catenoids as support surfaces or barriers at the non convex projected part of the C ² contour, assured by the non negativity of a function of the radii of the necks of the catenoids and the contour, the Douglas-Radó solution is absolute unique and a graph. Especially there are no further restrictions to the projection of the contour than C ²-smoothness. As easy first consequences, the earlier result of Sauvigny, using Scherk’s surface as support surfaces for certain contours with a non convex projection, is generalized to absolute uniqueness and the problem initiating, famous uniqueness and existence result in case of a convex projection of Radó, Kneser and Meeks is also carried over to absolute uniqueness. Finally, by a generic example using our mentioned main fruit of investigation, the non necessity of any curvature bound, any bound on function norms, any height bound, and Williams local tangential Lipschitz condition for the whole contour for the existence of a solution for the minimal surface equation or uniqueness of parametric minimal surfaces is shown. This covers more than all known sufficient conditions, i.e. the well known 4π curvature bound of Nitsche, Sauvigny’s uniform concavity-, Lau’s smallness in the C ^0,1-norm condition and Meeks restriction of the deviation from the plane in the C ²-norm. The article is strongly geometrical in spirit so enabling the use of geometrical imagination and intuition in the realms of results and techniques from many different, including very advanced and abstract, mathematical fields. As the proofs are very complete, transparent and proceed in little steps, covering also new elementary results, the article is predestined for educational employment. Especially for its use of the maximum principle in a very sophistcated, long run, merged with topology, way and the new setting of surfaces with a Riemannian structure and usual derivations for handling the non-orientable case.     

Class of tight bounds on the Q‐function with closed‐form upper bound on relative error

In this paper, we propose a novel class of parametric bounds on the Q‐function, which are lower bounds for 1 ≤ a < 3 and x > x_t = (a (a‐1) / (3‐a))^1/2, and upper bound for a = 3. We prove that the lower and upper bounds on the Q‐function can have the same analytical form that is asymptotically equal, which is a unique feature of our class of tight bounds. For the novel class of bounds and for each particular bound from this class, we derive the beneficial closed‐form expression for the upper bound on the relative error. By comparing the bound tightness for moderate and large argument values not only numerically, but also analytically, we demonstrate that our bounds are tighter compared with the previously reported bounds of similar analytical form complexity.     

Regularity Index of Fat Points in the Projective Plane

In this paper we determine a new upper bound for the regularity index of fat points of P², without requiring any geometric condition on the points. This bound is intermediate between Segre′s bound, that holds for points in the general position, and the more general bound, that is attained when the points are collinear: in fact, both of these bounds can be recovered as particular cases. Furthermore, our bound cannot, in general, be sharpened: in fact, it is attained if there are either many collinear points or collinear points with high multiplicities.     

Upper and Lower Bounds on Resonances for Manifolds Hyperbolic Near Infinity

For a conformally compact manifold that is hyperbolic near infinity and of dimension n + 1, we complete the proof of the optimal O(r ⁿ⁺¹) upper bound on the resonance counting function, correcting a mistake in the existing literature. In the case of a compactly supported perturbation of a hyperbolic manifold, we establish a Poisson formula expressing the regularized wave trace as a sum over scattering resonances. This leads to an r ⁿ⁺¹ lower bound on the counting function for scattering poles.     

Regularized Newton Methods for Convex Minimization Problems with Singular Solutions

This paper studies convergence properties of regularized Newton methods for minimizing a convex function whose Hessian matrix may be singular everywhere. We show that if the objective function is LC², then the methods possess local quadratic convergence under a local error bound condition without the requirement of isolated nonsingular solutions. By using a backtracking line search, we globalize an inexact regularized Newton method. We show that the unit stepsize is accepted eventually. Limited numerical experiments are presented, which show the practical advantage of the method.