Kolmogorov Entropy for Classes of Convex Functions

Kolmogorov ε-entropy of a compact set in a metric space measures its metric massivity and thus replaces its dimension which is usually infinite. The notion quantifies the compactness property of sets in metric spaces, and it is widely applied in pure and applied mathematics. The ε-entropy of a compact set is the most economic quantity of information that permits a recovery of elements of this set with accuracy ε. In the present article we study the problem of asymptotic behavior of the ε-entropy for uniformly bounded classes of convex functions in L _p -metric proposed by A.I.   Shnirelman. The asymptotic of the Kolmogorov ε-entropy for the compact metric space of convex and uniformly bounded functions equipped with L _p -metric is ε ^−1/2, ε→0₊.      

Kolmogorov＇s ε-Entropy of Bounded Sets in Discrete Spaces and Attractors of Dissipative Lattice Systems

We obtain an estimate of the upper bound for Kolmogorov＇s ε-entropy for the bounded sets with small ＂tail＂ in discrete spaces, then we present a sufficient condition for the existence of a global attractor for dissipative lattice systems in a reflexive Banach discrete space and establish an upper bound of Kolmogorov＇s ε-entropy of the global attractor for lattice systems.     

On the absolute <Emphasis Type="Italic">ɛ</Emphasis>-entropy of some compact set of infinitely differentiable periodic functions

We calculate the principal term of the asymptotics of the Kolmogorov ɛ-entropy of some compact set of periodic infinitely differentiable functions that is continuously embedded into the space of continuous periodic functions.     

Linear versus Non-Linear Acquisition of Step-Functions

We address in this article the following two closely related problems. 1. How to represent functions with singularities (up to a prescribed accuracy) in a compact way. 2. How to reconstruct such functions from a small number of measurements. The stress is on a comparison of linear and non-linear approaches. As a model case, we use piecewise-constant functions on [0,1], in particular, the Heaviside jump function ℋ _t =χ _[0,t]. Considered as a curve in the Hilbert space L ²([0,1]) it is completely characterized by the fact that any two its disjoint chords are orthogonal. We reinterpret this fact in a context of step-functions in one or two variables. Next, we study the limitations on representability and reconstruction of piecewise-constant functions by linear and semi-linear methods. Our main tools in this problem are Kolmogorov’s n-width and ε-entropy, as well as Temlyakov’s (N,m)-width. On the positive side, we show that a very accurate non-linear reconstruction is possible. It goes through a solution of certain specific non-linear systems of algebraic equations. We discuss the form of these systems and methods of their solution, stressing their relation to Moment Theory and Complex Analysis. Finally, we informally discuss two problems in Computer Imaging which are parallel to problems 1 and 2 above: compression of still images and video-sequences on one side, and image reconstruction from indirect measurement (for example, in Computer Tomography), on the other. This research was supported by the ISF, Grant No. 304/05, and by the Minerva Foundation.     

Optimally Space Localized Polynomials with Applications in Signal Processing

For the filtering of peaks in periodic signals, we specify polynomial filters that are optimally localized in space. The space localization of functions f having an expansion in terms of orthogonal polynomials is thereby measured by a generalized mean value ε(f). Solving an optimization problem including the functional ε(f), we determine those polynomials out of a polynomial space that are optimally localized. We give explicit formulas for these optimally space localized polynomials and determine in the case of the Jacobi polynomials the relation of the functional ε(f) to the position variance of a well-known uncertainty principle. Further, we will consider the Hermite polynomials as an example on how to get optimally space localized polynomials in a non-compact setting. Finally, we investigate how the obtained optimal polynomials can be applied as filters in signal processing.     

Refined estimates for the ɛ-entropy of the classesKH 0 α

By the methods of differential pulse-code modulation and “generalized” polygonal lines, we obtain almost exact estimates for the ɛ-entropy of classes simulating signals of various types. The complexity of coding and reconstruction of functions from the classes under consideration is investigated. We present a numerical solution of the problem of minimization of constants in the order-of-magnitude inequality for the ɛ-entropy of the classesKH ₀ ^α Institute of Mathematics, Ukrainian Academy of Sciences, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 6, pp. 760–764, June, 1994.     

Beyond all orders: Singular perturbations in a mapping

Summary We consider a family ofq-dimensional (q>1), volume-preserving maps depending on a small parameterε. Asε → 0⁺ these maps asymptote to flows which attain a heteroclinic connection. We show that for smallε the heteroclinic connection breaks up and that the splitting between its components scales withε likeε ^γexp[-β/ε]. We estimateβ using the singularities of theε → 0⁺ heteroclinic orbit in the complex plane. We then estimateγ using linearization about orbits in the complex plane. These estimates, as well as the assertions regarding the behavior of the functions in the complex plane, are supported by our numerical calculations. Deceased.     

Upper Semicontinuity and Kolmogorov ε-Entropy of Global Attractor for κ-Dimensional Lattice Dynamical System Corresponding to Klein-Gordon-SchrSdinger Equation

In this paper, we establish the existence of a global attractor for a coupled κ-dimensional lattice dynamical system governed by a discrete version of the Klein-Gordon-SchrSdinger Equation. An estimate of the upper bound of the Kohnogorov ε-entropy of the global attractor is made by a method of element decomposition and the covering property of a polyhedron by balls of radii ε in a finite dimensional space. Finally, a scheme to approximate the global attractor by the global attractors of finite-dimensional ordinary differential systems is presented .     

Exact order of relative widths of classes <Emphasis Type="Italic">W</Emphasis><Stack><Subscript>1</Subscript><Superscript>r</Superscript></Stack> in the space <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>

We determine the exact order of relative widths of classes W ₁ ^r of periodic functions in the space L ₁ as n → ∞ under restrictions on higher derivatives of approximating functions. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 10, pp. 1409–1417, October, 2005.     

<Emphasis Type="Italic">ε</Emphasis>-Optimality and <Emphasis Type="Italic">ε</Emphasis>-Lagrangian Duality for a Nonconvex Programming Problem with an Infinite Number of Constraints

In this paper, ε-optimality conditions are given for a nonconvex programming problem which has an infinite number of constraints. The objective function and the constraint functions are supposed to be locally Lipschitz on a Banach space. In a first part, we introduce the concept of regular ε-solution and propose a generalization of the Karush-Kuhn-Tucker conditions. These conditions are up to ε and are obtained by weakening the classical complementarity conditions. Furthermore, they are satisfied without assuming any constraint qualification. Then, we prove that these conditions are also sufficient for ε-optimality when the constraints are convex and the objective function is ε-semiconvex. In a second part, we define quasisaddlepoints associated with an ε-Lagrangian functional and we investigate their relationships with the generalized KKT conditions. In particular, we formulate a Wolfe-type dual problem which allows us to present ε-duality theorems and relationships between the KKT conditions and regular ε-solutions for the dual. Finally, we apply these results to two important infinite programming problems: the cone-constrained convex problem and the semidefinite programming problem.     

关于连续映射半群拓扑熵的一点注记

本文研究了度量空间中连续映射构成半群的拓扑熵.利用Patr′ao~([8])的方法,给出了度量空间中两种有限个连续映射构成的半群的拓扑d-熵的定义,比较了两种拓扑d-熵的大小.证明了局部紧致可分度量空间上有限个真映射构成的半群的拓扑d-熵和它的一点紧化空间上对应的拓扑熵相等.上面结果推广了Patr′ao的相应结论.     

Value and perfection in stochastic games

A stochastic game isvalued if for every playerk there is a functionr ^k:S→R from the state spaceS to the real numbers such that for every ε>0 there is an ε equilibrium such that with probability at least 1−ε no states is reached where the future expected payoff for any playerk differs fromr ^k(s) by more than ε. We call a stochastic gamenormal if the state space is at most countable, there are finitely many players, at every state every player has only finitely many actions, and the payoffs are uniformly bounded and Borel measurable as functions on the histories of play. We demonstrate an example of a recursive two-person non-zero-sum normal stochastic game with only three non-absorbing states and limit average payoffs that is not valued (but does have ε equilibria for every positive ε). In this respect two-person non-zero-sum stochastic games are very different from their zero-sum varieties. N. Vieille proved that all such non-zero-sum games with finitely many states have an ε equilibrium for every positive ε, and our example shows that any proof of this result must be qualitatively different from the existence proofs for zero-sum games. To show that our example is not valued we need that the existence of ε equilibria for all positive ε implies a “perfection” property. Should there exist a normal stochastic game without an ε equilibrium for some ε>0, this perfection property may be useful for demonstrating this fact. Furthermore, our example sews some doubt concerning the existence of ε equilibria for two-person non-zero-sum recursive normal stochastic games with countably many states. This research was supported financially by the German Science Foundation (Deutsche Forschungsgemeinschaft) and the Center for High Performance Computing (Technical University, Dresden). The author thanks Ulrich Krengel and Heinrich Hering for their support of his habilitation at the University of Goettingen, of which this paper is a part.     

Pseudo-dimension and entropy of manifolds formed by affine-invariant dictionary

We consider the manifolds H _n(φ) formed by all possible linear combinations of n functions from the set {φ(A⋅+b)}, where x→Ax+b is arbitrary affine mapping in the space ℝ^d. For example, neural networks and radial basis functions are the manifolds of type H _n(φ). We obtain estimates for pseudo-dimension of the manifold H _n(φ) for wide collection of the generator function φ. The estimates have the order O(d ² n) in degree scale, that is the order is proportional to number of parameters of the manifold H _n(φ). Moreover the estimates for ɛ-entropy of the manifold H _n(φ) are obtained. Mathematics subject classifications (2000) 41A46, 41A50, 42A61, 42C10 V. Maiorov: Supported by the Center for Absorption in Science, Ministry of Immigrant Absorption, State of Israel.     

A Dynamical System Associated with Newton's Method for Parametric Approximations of Convex Minimization Problems

We study the existence and asymptotic convergence when t→+∞ for the trajectories generated by where is a parametric family of convex functions which approximates a given convex function f we want to minimize, and ε(t) is a parametrization such that ε(t)→ 0 when t→+∞ . This method is obtained from the following variational characterization of Newton's method: where H is a real Hilbert space. We find conditions on the approximating family and the parametrization to ensure the norm convergence of the solution trajectories u(t) toward a particular minimizer of f . The asymptotic estimates obtained allow us to study the rate of convergence as well. The results are illustrated through some applications to barrier and penalty methods for linear programming, and to viscosity methods for an abstract noncoercive variational problem. Comparisons with the steepest descent method are also provided. Accepted 5 December 1996     

Trigonometric widths of the classes B p,θ r of functions of many variables in the space L q

We obtain estimates exact in order for the trigonometric widths of the Besov classes B _p,θ^r of periodic functions of many variables in the space L _q for 1 ≤ p ≤ 2 < q < p/(p - 1). Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 8, pp. 1089–1097, August, 1998.     

Asymptotic analysis of a parabolic semilinear problem with nonlinear boundary multiphase interactions in a perforated domain

We consider a parabolic semilinear problem with rapidly oscillating coefficients in a domain Ω_ε that is ε-periodically perforated by small holes of size O\mathcal {O}(ε). The holes are divided into two ε-periodical sets depending on the boundary interaction at their surfaces, and two different nonlinear Robin boundary conditions σ_ε(u _ε) + εκ _m (u _ε) = εg ^(m) _ε, m = 1, 2, are imposed on the boundaries of holes. We study the asymptotics as ε → 0 and establish a convergence theorem without using extension operators. An asymptotic approximation of the solution and the corresponding error estimate are also obtained. Bibliography: 60 titles. Illustrations: 1 figure.     

Asymptotic modelling of conductive thin sheets

We derive and analyse models which reduce conducting sheets of a small thickness ε in two dimensions to an interface and approximate their shielding behaviour by conditions on this interface. For this we consider a model problem with a conductivity scaled reciprocal to the thickness ε, which leads to a nontrivial limit solution for ε → 0. The functions of the expansion are defined hierarchically, i.e. order by order. Our analysis shows that for smooth sheets the models are well defined for any order and have optimal convergence meaning that the H ¹-modelling error for an expansion with N terms is bounded by O(ε ^N+1) in the exterior of the sheet and by O(ε ^N+1/2) in its interior. We explicitly specify the models of order zero, one and two. Numerical experiments for sheets with varying curvature validate the theoretical results.     

Imbedding of power series spaces and spaces of analytic functions

The diametral dimension of a nuclear Fréchet spaceE, which satisfies (DN) and (Ω), is related to power series spaces Λ₁(ε) and Λ_∞(ε) for some exponent sequence ε. It is proved thatE contains a complemented copy of Λ_∞(ε) provided the diametral dimensions ofE and Λ_∞(ε) are equal and ε is stable. Assuming Λ₁(ε) is nuclear, any subspace of Λ₁(ε) which satisfies (DN), can be imbedded intoE. Applications of these results to spaces of analytic functions are given. Support of Turkish Scientific and Technical Research Council is gratefully acknowledged.     

Linear widths of the classes B p,θ Ω of periodic functions of many variables in the space L q

We obtain exact order estimates for the linear widths of the classes B _p,θ ^Ω of periodic functions of many variables in the space L _q for certain values of the parameters p and q. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 1, pp. 93–104, January, 2006.