A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

Small into-isomorphism from L∞(A,μ) into L∞(B,υ)

In this paper we shall assert that if T is an isomorphism of L_∞(Ω₁, A, μ) into L_∞(Ω₂, B, υ) satisfying the condition ‖T‖·‖T ⁻¹‖⩽1+ɛ for ɛ∈ , then is close to an isometry with an error less than 6ε in some conditions.     

Norms of powers of absolutely convergent fourier series

Letf(t) = ∑a _k e ^ikt be infinitely differentiable on R, |f(t)|<1. It is known that under these assumptions ‖ⁿ‖ converges to a finite limitl asn → ∞ (l ² = sec(arga),a = (f′(0))² -f″(0)). We obtain here more precise results: (i) an asymptotic series (in powers ofn ^-1/2) for the Fourier coefficientsa _nk off ⁿ , which holds uniformly ink asn → ∞; (ii) an asymptotic series (this time only powers ofn ^-1 are present!) for ‖f ⁿ ‖; (iii) the fact that ifi ^j f ^(j)(0) is real forj = 1,2,..., 2h + 2 then ‖f ⁿ ‖ = l + o(n ^-h ),n → ∞. More generally, we obtain analogous finite asymptotic expansions whenf is assumed to be differentiable only finitely many times.     

Von Neumann-Jordan Constants of Absolute Normalized Norms on C^n

In this note, we give some estimations of the Von Neumann-Jordan constant C _{N J} (∥·∥_ψ) of Banach space (ℂ ⁿ , ∥·∥_ψ), where ∥·∥_ψ is the absolute normalized norm on ℂ ⁿ given by function ψ. In the case where ψ and φ are comparable, n=2 and C _{N J} (∥·∥_ψ)=1, we obtain a formula of computing C _{N J} (∥·∥_ψ). Our results generalize some results due to Saito and others. Received May 11, 2002, Accepted November 20, 2002 This work is partly supported by NNSF of China (No. 19771056)     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

The riesz turndown collar theorem giving an asymptotic estimate of the powers of an operator under the ritt condition

For Banach space operatorsT satisfying the Tadmor-Ritt condition ‖(zI−T)⁻¹‖≤C|z−1|⁻¹, |z|>1, we show how to use the Riesz turndown collar theorem to estimate sup _n≥0‖T ⁿ‖. A similar estimate is shown for lim sup _n ‖T ⁿ‖ in terms of the Ritt constantM=lim sup _z→1‖(1−z)(zI−T)⁻¹‖. We also obtain an estimate of the functional calculus for these operators proving, in particular, that ‖f(T)‖≤C _q‖f‖ _Mult , where ‖·‖ _Mult stands for the multiplier norm of the Cauchy-Stieltjes integrals over a Lusin type cone domain depending onC and a parameterq, 0<q<1. Notation.D denotes the open unit disc of the complex plane,D={z∈ℂ:|z|<1}, andT={z∈ℂ:|z|=1} is the unit circle.H ^∞ is the Banach algebra of bounded analytic functions onD equipped with the supremum norm ‖.‖_∞.     

The bicompletion of an asymmetric normed linear space

A biBanach space is an asymmetric normed linear space (X,‖·‖) such that the normed linear space (X,‖·‖^s) is a Banach space, where ‖x‖^s= max {‖x‖,‖-x‖} for all x∈X. We prove that each asymmetric normed linear space (X,‖·‖) is isometrically isomorphic to a dense subspace of a biBanach space (Y,‖·‖_Y). Furthermore the space (Y,‖·‖_Y) is unique (up to isometric isomorphism). This revised version was published online in August 2006 with corrections to the Cover Date.     

Estimates of the periods of periodic points for nonexpansive operators

Suppose thatE is a finite-dimensional Banach space with a polyhedral norm ‖·‖, i.e., a norm such that the unit ball inE is a polyhedron. ℝ ⁿ with the sup norm or ℝ ⁿ with thel ₁-norm are important examples. IfD is a bounded set inE andT:D→D is a map such that ‖T(y)−T(z)‖≤ ‖y−z‖ for ally andz inE, thenT is called nonexpansive with respect to ‖·‖, and it is known that for eachx ∈D there is an integerp=p(x) such that lim _j→∞ T ^jp (x) exists. Furthermore, there exists an integerN, depending only on the dimension ofE and the polyhedral norm onE, such thatp(x)≤N: see [1,12,18,19] and the references to the literature there. In [15], Scheutzow has raised a question about the optimal choice ofN whenE=ℝ ⁿ ,D=K ⁿ , the set of nonnegative vectors in ℝ ⁿ , and the norm is thel ₁-norm. We provide here a reasonably sharp answer to Scheutzow’s question, and in fact we provide a systematic way to generate examples and use this approach to prove that our estimates are optimal forn≤24. See Theorem 2.1, Table 2.1 and the examples in Section 3. As we show in Corollary 2.3, these results also provide information about the caseD=ℝ ⁿ , i.e.,T:ℝ ⁿ →ℝ ⁿ isl ₁-nonexpansive. In addition, it is conjectured in [12] thatN=2 ⁿ whenE=ℝ ⁿ and the norm is the sup norm, and such a result is optimal, if true. Our theorems here show that a sharper result is true for an important subclass of nonexpansive mapsT:(ℝ ⁿ ,‖ · ‖_∞)→(ℝ ⁿ ,‖ · ‖_∞). Partially supported by NSF DMS89-03018.     

Positive definite functions and stable random vectors

We say that a random vector X = (X ₁, …, X _n ) in ℝ ⁿ is an n-dimensional version of a random variable Y if, for any a ∈ ℝ ⁿ , the random variables Σa _i X _i and γ(a)Y are identically distributed, where γ: ℝ ⁿ → [0,∞) is called the standard of X. An old problem is to characterize those functions γ that can appear as the standard of an n-dimensional version. In this paper, we prove the conjecture of Lisitsky that every standard must be the norm of a space that embeds in L ₀. This result is almost optimal, as the norm of any finite-dimensional subspace of L _p with p ∈ (0, 2] is the standard of an n-dimensional version (p-stable random vector) by the classical result of P. Lèvy. An equivalent formulation is that if a function of the form f(‖ · ‖ _K ) is positive definite on ℝ ⁿ , where K is an origin symmetric star body in ℝ ⁿ and f: ℝ → ℝ is an even continuous function, then either the space (ℝ ⁿ , ‖·‖ _K ) embeds in L ₀ or f is a constant function. Combined with known facts about embedding in L ₀, this result leads to several generalizations of the solution of Schoenberg’s problem on positive definite functions.     

Fourier analysis with respect to bilinear maps

Several results about convolution and about Fourier coefficients for X-valued functions defined on t he torus satisfying the condition sup ｜｜y｜｜=1∫-π^π｜｜ B （f （e^iθ）, y）｜｜dθ/2π〈 ∞ for a bounded bilinear map B ： X × Y → Z are presented and some applications are given.     

The convergence rate of Euler means sequence

Let denote the Euler means of the Fourier series of the 2π-perodic function f(x). For an integer q>0, setting ℰ _nq (ω)=sup‖f−ℰ _n (q,f)‖, the precise value of is obtained.     

Weighted <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> boundedness for multilinear fractional integral on product spaces

For 0 < α < mn and nonnegative integers n ≥ 2, m ≥ 1, the multilinear fractional integral is defined by

On linear isometries of Banach lattices in <Emphasis Type="Italic">C</Emphasis><Subscript>0</Subscript>(Ω)-spaces

Consider the space C0(Ω) endowed with a Banach lattice-norm ‖ · ‖ that is not assumed to be the usual spectral norm ‖ · ‖_∞ of the supremum over Ω. A recent extension of the classical Banach-Stone theorem establishes that each surjective linear isometry U of the Banach lattice (C ₀(Ω), ‖ · ‖) induces a partition Π of Ω into a family of finite subsets S ⊂ Ω along with a bijection T: Π → Π which preserves cardinality, and a family [u(S): S ∈ Π] of surjective linear maps u(S): C(T(S)) → C(S) of the finite-dimensional C*-algebras C(S) such that

Concerning the order of approximation of periodic continuous functions by trigonometric interpolation polynomials

Letx _kn=2θk/n,k=0,1 …n−1 (n odd positive integer). LetR _n(x) be the unique trigonometric polynomial of order 2n satisfying the interpolatory conditions:R _n(x_kn)=f(x_kn),R _n ^(j)(x_kn)=0,j=1,2,4,k=0,1…,n−1. We setw ₂(t,f) as the second modulus of continuity off(x). Then we prove that |R _n(x)-f(x)|=0(nw₂(1/nf)). We also examine the question of lower estimate of ‖R _n-f‖. This generalizes an earlier work of the author.     

Norm conditions for real-algebra isomorphisms between uniform algebras

Let A and B be uniform algebras. Suppose that α ≠ 0 and A ₁ ⊂ A. Let ρ, τ: A ₁ → A and S, T: A ₁ → B be mappings. Suppose that ρ(A ₁), τ(A ₁) and S(A ₁), T(A ₁) are closed under multiplications and contain expA and expB, respectively. If ‖S(f)T(g) − α‖_∞ = ‖ρ(f)τ(g) − α‖_∞ for all f, g ∈ A ₁, S(e ₁)⁻¹ ∈ S(A ₁) and S(e ₁) ∈ T(A ₁) for some e ₁ ∈ A ₁ with ρ(e ₁) = 1, then there exists a real-algebra isomorphism $ \tilde S $ \tilde S : A → B such that $ \tilde S $ \tilde S (ρ(f)) = S(e ₁)⁻¹ S(f) for every f ∈ A ₁. We also give some applications of this result.     

Higher order Lipschitz classes of functions and absolutely convergent Fourier series

We introduce the higher order Lipschitz classes Λ _r (α) and λ _r (α) of periodic functions by means of the rth order difference operator, where r = 1, 2, ..., and 0 < α ≦ r. We study the smoothness property of a function f with absolutely convergent Fourier series and give best possible sufficient conditions in terms of its Fourier coefficients in order that f belongs to one of the above classes. This research was supported by the Hungarian National Foundation for Scientific Research under Grant T 046 192.     

The Hardy-Littlewood theorem for trigonometric series with generalized monotone coefficients

Earlier we introduced a continuous scale of monotony for sequences (classes M _α, α ≥ 0), where, for example, M ₀ is the set of all nonnegative vanishing sequences, M ₁ is the class of all nonincreasing sequences, tending to zero, etc. In addition, we extended several results obtained for trigonometric series with monotone convex coefficients onto more general classes. The main result of this paper is a generalization of the well-known Hardy—Littlewood theorem for trigonometric series, whose coefficients belong to classes M _α, where α ∈ ( $ \tfrac{1} {2} Earlier we introduced a continuous scale of monotony for sequences (classes M _α, α ≥ 0), where, for example, M ₀ is the set of all nonnegative vanishing sequences, M ₁ is the class of all nonincreasing sequences, tending to zero, etc. In addition, we extended several results obtained for trigonometric series with monotone convex coefficients onto more general classes. The main result of this paper is a generalization of the well-known Hardy—Littlewood theorem for trigonometric series, whose coefficients belong to classes M _α, where α ∈ (, 1). Namely, the following assertion is true. Let α ∈ (, 1), < p < 2, a sequence a ∈ M _α, and . Then the series cos nx converges on (0,2π) to a finite function f(x) and f(x) ∈ L _p (0,2π). Original Russian Text ? M.I. D’yachenko, 2008, published in Izvestiya Vysshikh Uchebnykh Zavedenii, Matematika, 2008, No. 5, pp. 38–47.     

Recurrence in unipotent groups and ergodic nonabelian group extensions

LetT be a measure-preserving and ergodic transformation of a standard probability space (X,S, μ) and letf:X → SUT _d (ℝ) be a Borel map into the group of unipotent upper triangulard ×d matrices. We modify an argument in [12] to obtain a sufficient condition for the recurrence of the random walk defined byf, in terms of the asymptotic behaviour of the distributions of the suitably scaled mapsf(n,x)=(fT ⁿ⁻¹·fT ⁿ⁻²…fT·f). We give examples of recurrent cocycles with values in the continuous Heisenberg group H₁(ℝ)=SUT₃(ℝ), and we use a recurrent cocycle to construct an ergodic skew-product extension of an irrational rotation by the discrete Heisenberg group H₁(ℤ)=SUT₃(ℤ). The author was partially supported by the FWF research project P16004-MAT.     

An ergodic theorem on Banach lattices

E is a Banach lattice that is weakly sequentially complete and has a weak unitu. TLf _n=ϕ means that the infimum of |f _n−ϕ| andu converges strongly to zero.T is a positive contraction operator onE andA _n=(1/n)(I+T+...+T ⁿ⁻¹). Without an additional assumption onE, the “truncated limit” TLA _nf need not exist forf inE. This limit exists for eachf ifE satisfies the following additional assumption (C): For everyf inE ₊ and for every numberα>0, there is a numberβ=β(f, α) such that ifg is inE ₊, ‖g‖≦1, 0≦f′≦f and ‖f′‖>α then ‖f′+g‖≧‖g‖+β. Research of this author is partially supported by NSERC Grant A3974. Research of this author is partially supported by NSF Grant 8301619.     

Normed algebras of differentiable functions on compact plane sets

We investigate the completeness and completions of the normed algebras (D ⁽¹⁾(X), ‖ · ‖) for perfect, compact plane sets X. In particular, we construct a radially self-absorbing, compact plane set X such that the normed algebra (D ⁽¹⁾(X), ‖ · ‖) is not complete. This solves a question of Bland and Feinstein. We also prove that there are several classes of connected, compact plane sets X for which the completeness of (D ⁽¹⁾(X), ‖ · ‖) is equivalent to the pointwise regularity of X. For example, this is true for all rectifiably connected, polynomially convex, compact plane sets with empty interior, for all star-shaped, compact plane sets, and for all Jordan arcs in ℂ.