Representing a Functional Curve by Curves with Fewer Peaks

In this paper, we study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Representing a function (or its curve) by certain classes of structurally simpler functions (or their curves) is a basic mathematical problem. Problems of this kind also find applications in applied areas such as intensity-modulated radiation therapy (IMRT). Let f\bf f be an input piecewise linear functional curve of size n. We consider several variations of the problems. (1) Uphill–downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing (uphill) and one nonincreasing (downhill), such that their sum exactly or approximately represents f\bf f. (2) Unimodal representation (UR): Find a set of unimodal (single-peak) curves such that their sum exactly or approximately represents f\bf f. (3) Fewer-peak representation (FPR): Find a piecewise linear curve with at most k peaks that exactly or approximately represents f\bf f. Furthermore, for each problem, we consider two versions. For the UDPR problem, we study its feasibility version: Given ε>0, determine whether there is a feasible UDPR solution for f\bf f with an approximation error ε; its min-ε version: Compute the minimum approximation error ε ^∗ such that there is a feasible UDPR solution for f\bf f with error ε ^∗. For the UR problem, we study its min-k version: Given ε>0, find a feasible solution with the minimum number k ^∗ of unimodal curves for f\bf f with an error ε; its min-ε version: given k>0, compute the minimum error ε ^∗ such that there is a feasible solution with at most k unimodal curves for f\bf f with error ε ^∗. For the FPR problem, we study its min-k version: Given ε>0, find one feasible curve with the minimum number k ^∗ of peaks for f\bf f with an error ε; its min-ε version: given k≥0, compute the minimum error ε ^∗ such that there is a feasible curve with at most k peaks for f\bf f with error ε ^∗. Little work has been done previously on solving these functional curve representation problems. We solve all the problems (except the UR min-ε version) in optimal O(n) time, and the UR min-ε version in O(n+mlog m) time, where m<n is the number of peaks of f\bf f. Our algorithms are based on new geometric observations and interesting techniques.     

Homogenization of a parabolic signorini boundary value problem in a thick plane junction

We consider a parabolic Signorini boundary value problem in a thick plane junction Ω _ε which is the union of a domain Ω₀ and a large number of ε−periodically situated thin rods. The Signorini conditions are given on the vertical sides of the thin rods. The asymptotic analysis of this problem is done as ε → 0, i.e., when the number of the thin rods infinitely increases and their thickness tends to zero. With the help of the integral identity method we prove a convergence theorem and show that the Signorini conditions are transformed (as ε → 0) in differential inequalities in the region that is filled up by the thin rods in the limit passage. Bibliography: 31 titles. Illustrations: 1 figure.     

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₊.      

Stabilized Asymptotics of solutions to reaction-diffusion systems with a small parameter

For solutions of reaction-diffusion systems under Dirichlet or Neumann boundary conditions, having a small parameter ε as a coefficient to the time derivative of the first component, the principal term of the asymptotics with respect to ε is found for all t>0. This principal term is a solution of the system, obtained as a limit for ε=0, and has a finite number of discontinuities; the continuous parts, beginning from the second, are situated on finite-dimensional unstable manifolds passing through stationary points of the limit system. Bibliography: 4 titles. Translated from Trudy Seminara imeni I. G. Petrovskogo, No. 17, pp. 128–152, 1994.     

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.     

The centralizing theorem for left normal groups of units in compact monoids

A group G of units in a monoid S is called left normal if sG ⊆ Gs for all s ε S. The centralizer Z of G in S is the set of all s ε S with sg=gs for all g ε G. Always l ε Z, and if S has a zero 0, then 0 ε Z. We show that in a compact connected monoid S with zero the centralizer Z of any left normal (closed) group G of units is connected. This work was supported by NSF.     

Estimation and detection of a function from tensor product spaces

We observe an unknown function of d variables ƒ(t), t ∈ [0, 1]^d, in the white Gaussian noise of level ε > 0. We assume that {ie4526-01}, where {ie4526-02} is a ball in the Hilbert space {ie4526-03} of tensor product structure. Under minimax setup, we consider two problems: estimate ƒ (for quadratic losses) and detect ƒ, i.e., test the null hypothesis H₀: ƒ = 0 against the alternatives {ie4526-04}. We are interested in the case {ie4526-05}. We study sharp, rate, and log-asymptotics (as ε → 0 and d → ∞) in the problems. In particular, we show that log-asymptotics are essentially different for d ≪ log ε⁻¹ and d ≫ log ε⁻¹. Bibliography: 19 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 351, 2007, pp. 180–218.     

On a biharmonic equation involving nearly critical exponent

This paper is concerned with a biharmonic equation under the Navier boundary condition , u > 0 in Ω and u = Δu = 0 on ∂Ω, where Ω is a smooth bounded domain in , n ≥ 5, and ε > 0. We study the asymptotic behavior of solutions of (P _−ε) which are minimizing for the Sobolev quotient as ε goes to zero. We show that such solutions concentrate around a point x ₀ ∈Ω as ε → 0, moreover x ₀ is a critical point of the Robin’s function. Conversely, we show that for any nondegenerate critical point x ₀ of the Robin’s function, there exist solutions of (P _−ε) concentrating around x ₀ as ε → 0. Finally we prove that, in contrast with what happened in the subcritical equation (P _−ε), the supercritical problem (P _+ε) has no solutions which concentrate around a point of Ω as ε → 0. Work finished when the authors were visiting Mathematics Department of the University of Roma “La Sapienza”. They would like to thank the Mathematics Department for its warm hospitality. The authors also thank Professors Massimo Grossi and Filomena Pacella for their constant support.     

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.     

On eigenfunctions localized in a neighborhood of the lateral surface of a thin domain

We study the spectrum of the boundary-value problem for the Laplace operator in a thin domain Ω(ε) obtained by small perturbation of the cylinder Ω(ε)=ω×(-ε/2.ε/2) ⊂ ℝ³in a neighborhood of the lateral surface. The Dirichlet condition is imposed on the bases of the cylinder, and the Dirichlet condition or the Neumann condition is imposed on the remaining part of ∂Ω(ε). We construct and justify asymptotic formulas (as ε→+0) for eigenvalues and eigenfunctions. In view of a special form of the lateral surface, there are eigenfunctions of boundary-layer type that exponentially decrease far from the lateral surface. For the mixed boundary-value problem such a localization is possible in neighborhoods of local maxima of the curvature of the contour ∂ω. This property of eigenfunctions is a characteristic feature of the first points of the spectrum (in particular, the first eigenvalue) and, under the passage from Ω(h)₍₎ to Ω(h), the spectrum itself has perturbation O(h⁻²). Bibliography: 29 titles. Translated fromProblemy Matematicheskogo Analiza, No. 19, 1999, pp. 105–149.     

The asymptotic behavior of a solution to the boundary-value problem in a degenerate domain with rapidly oscillating boundary

We construct and justify the asymptotics (as ε → +0) of a solution of the mixed boundary-value problem for the Poisson equation in the domain obtained by joining two sets Ω₊ and Ω_- by a large number of thin (of width O (ε)) curvilinear strips (a hub and a rim with a large number of spokes). As a resulting limit problem describing the principal terms of exterior expansions (in Ω_± and in the set ω occupied by the strips) we take the problem of conjugating the partial differential equations and an ordinary differential equation depending on a parameter. Bibliography: 16 titles; Illustrations: 1 figure. Translated fromProblemy Matematicheskogo Analiza, No. 14, 1995, pp. 63–90.     

Justification of a quasistationary approximation for the Stefan problem

Unique solvability of the one-phase Stefan problem with a small multiplier ε at the time derivative in the equation is proved on a certain time interval independent of ε for ε ∈ (0, ε₀). The solution to the Stefan problem is compared with the solution to the Hele-Show problem, which describes the process of melting materials with zero specific heat ε and can be regarded as a quasistationary approximation for the Stefan problem. It is shown that the difference of the solutions has order . This provides a justification of the quasistationary approximation. Bibliography: 23 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 348, 2007, pp. 209–253.     

An ε-relaxation method for separable convex cost generalized network flow problems

We generalize the ε-relaxation method of [14] for the single commodity, linear or separable convex cost network flow problem to network flow problems with positive gains. The method maintains ε-complementary slackness at all iterations and adjusts the arc flows and the node prices so as to satisfy flow conservation upon termination. Each iteration of the method involves either a price change on a node or a flow change along an arc or a flow change along a simple cycle. Complexity bounds for the method are derived. For one implementation employing ε-scaling, the bound is polynomial in the number of nodes N, the number of arcs A, a certain constant Γ depending on the arc gains, and ln(ε⁰/), where ε⁰ and denote, respectively, the initial and the final tolerance ε. Received: November 10, 1996 / Accepted: October 1999?Published online April 20, 2000     

A singularly perturbed spectral problem for a biharmonic operator with Neumann conditions

We study a mathematical model of a composite plate that consists of two components with similar elastic properties but different distributions of density. The area of the domain occupied by one of the components is infinitely small as ε → 0. We investigate the asymptotic behavior of the eigenvalues and eigenfunctions of the boundary-value problem for a biharmonic operator with Neumann conditions as ε → 0. We describe four different cases of the limiting behavior of the spectrum, depending on the ratio of densities of the medium components. In particular, we describe the so-called Sanches-Palensia effect of local vibrations: A vibrating system has a countable series of proper frequencies infinitely small as ε → 0 and associated with natural forms of vibrations localized in the domain of perturbation of density. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 11, pp. 1467–1475, November, 1999.     

Range Minima Queries with Respect to a Random Permutation,and Approximate Range Counting

In approximate halfspace range counting, one is given a set P of n points in ℝ ^d , and an ε>0, and the goal is to preprocess P into a data structure which can answer efficiently queries of the form: Given a halfspace h, compute an estimate N such that (1−ε)|P∩h|≤N≤(1+ε)|P∩h|.     

Piecewise Continuous Controls in Dieudonné-Rashevsky Type Problems

This paper considers multidimensional control problems governed by a first-order PDE system. It is known that, if the structure of the problem is linear-convex, then the so-called ε-maximum principle, a set of necessary optimality conditions involving a perturbation parameter ε > 0, holds. Assuming that the optimal controls are piecewise continuous, we are able to drop the perturbation parameter within the conditions, proving the Pontryagin maximum principle with piecewise regular multipliers (measures). The Lebesgue and Hahn decompositions of the multipliers lead to refined maximum conditions. Our proof is based on the Baire classification of the admissible controls.     

Codimension one minimal cycles with coefficients inZ orZ p , and variational functionals on fibered spaces

Given a compact, oriented Riemannian manifold M, without boundary, and a codimension-one homology class in H_* (M, Z) (or, respectively, in H_* (M, Z_p) with p an odd prime), we consider the problem of finding a cycle of least area in the given class: this is known as the homological Plateau’s problem. We propose an elliptic regularization of this problem, by constructing suitable fiber bundles ξ (resp. ζ) on M, and one-parameter families of functionals defined on the regular sections of ξ, (resp. ζ), depending on a small parameter ε. As ε → 0, the minimizers of these functionals are shown to converge to some limiting section, whose discontinuity set is exactly the minimal cycle desired.     

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.     

The Wave Front Set of the Wigner Distribution and Instantaneous Frequency

We prove a formula expressing the gradient of the phase function of a function f:ℝ ^d ↦ℂ as a normalized first frequency moment of the Wigner distribution for fixed time. The formula holds when f is the Fourier transform of a distribution of compact support, or when f belongs to a Sobolev space H ^d/2+1+ε (ℝ ^d ) where ε>0. The restriction of the Wigner distribution to fixed time is well defined provided a certain condition on its wave front set is satisfied. Therefore we first need to study the wave front set of the Wigner distribution of a tempered distribution.