Toeplitz condition numbers as an <Emphasis Type="Italic">H</Emphasis><Superscript>∞</Superscript> interpolation problem

The condition numbers CN(T) = ∥T∥ · ∥T⁻¹∥ of Toeplitz and analytic n × n matrices T are studied. It is shown that the supremum of CN(T) over all such matrices with ∥T∥ ≤ 1 and the given minimum of eigenvalues r = min |λ_i| > 0 behaves as the corresponding supremum over all n × n matrices (i.e., as (Kronecker)), and this equivalence is uniform in n and r. The proof is based on a use of the Sarason-Sz.Nagy-Foias commutant lifting theorem. Bibliography: 2 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 355, 2008, pp. 173–179.     

A note on the powers of Cesàro bounded operators

In this note we give a negative answer to Zemánek’s question (1994) of whether it always holds that a Cesàro bounded operator T on a Hilbert space with a single spectrum satisfies $ \mathop {\lim }\limits_{n \to \infty } $ \mathop {\lim }\limits_{n \to \infty } ∥T ⁿ⁺¹ − T ⁿ ∥ = 0.     

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 embedding trees into uniformly convex Banach spaces

We investigate the minimum value ofD =D(n) such that anyn-point tree metric space (T, ρ) can beD-embedded into a given Banach space (X, ∥·∥); that is, there exists a mappingf :T →X with 1/D ρ(x,y) ≤ ∥f(x) −f(y)∥ ≤ρ(x,y) for anyx,y εT. Bourgain showed thatD(n) grows to infinity for any superreflexiveX (and this characterized super-reflexivity), and forX =ℓ _p, 1 <p < ∞, he proved a quantitative lower bound of const·(log logn)^min(1/2,1/p). We give another, completely elementary proof of this lower bound, and we prove that it is tight (up to the value of the constant). In particular, we show that anyn-point tree metric space can beD-embedded into a Euclidean space, with no restriction on the dimension, withD =O(√log logn). This paper contains results from my thesis [Mat89] from 1989. Since the subject of bi-Lipschitz embeddings is becoming increasingly popular, in 1997 I finally decided to publish this English version. Supported by Czech Republic Grant GAČR 0194 and by Charles University grants No. 193, 194.     

Nondeterminism of Linear Operators and Lower Entropy Estimates

Let u be a (bounded, linear) operator from a Hilbert space ℋ into the Banach space C(T), the space of continuous functions on the compact metric space T. We introduce and investigate numbers τ _n (u), n≥1, measuring the degree of determinism of the operator u. The slower τ _n (u) decreases, the less determined are functions in the range of u by their values on a certain set of points. It is shown that n ^−1/2 τ _n (u)≤2e _n (u), where e _n (u) are the (dyadic) entropy numbers of u. Furthermore, we transform the notion of strong local nondeterminism from the language of stochastic processes into that of linear operators. This property, together with a lower entropy estimate for the compact space T, leads to a lower estimate for τ _n (u), hence also for e _n (u). These results are used to prove sharp lower entropy estimates for some integral operators, among them, Riemann–Liouville operators with values in C(T) for some fractal set T. Some multi-dimensional extensions are treated as well.      

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     

Asymptotic behavior of solutions to viscous conservation laws with slowly varying external forces

This paper considers the existence and large time behavior of solutions to the convection-diffusion equation u _t −Δu+b(x)·∇(u|u| ^{q −1})=f(x, t) in ℝ ⁿ ×[0,∞), where f(x, t) is slowly decaying and q≥1+1/n (or in some particular cases q≥1). The initial condition u ₀ is supposed to be in an appropriate L ^p space. Uniform and nonuniform decay of the solutions will be established depending on the data and the forcing term.This work is partially supported by an AMO Grant     

Commutators in model spaces

Let θ be an inner function, let K _θ = H ² ⊖ θH ², and let S_θ : K_θ → S_θ be defined by the formula S_θf = P_θzf, where f ∈ K_θ is the orthogonal projection of H² onto K_θ. Consider the set A of all trace class operators L : K_θ → K_θ, L = ∑(·,u_n)v_n, ∑∥u_n∥∥v_n∥ < ∞ (u_n, v_n ∈ K_θ), such that ∑ū_n v_n ∈ H ₀ ¹ . It is shown that trace class commutators of the form XS_θ − S_θX (where X is a bounded linear operator on K_θ) are dense in A in the trace class norm. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 333, 2006, pp. 54–61.     

Negative result in pointwise 3-convex polynomial approximation

Let Δ³ be the set of functions three times continuously differentiable on [−1, 1] and such that f″′(x) ≥ 0, x ∈ [−1, 1]. We prove that, for any n ∈ ℕ and r ≥ 5, there exists a function f ∈ C ^r [−1, 1] ⋂ Δ³ [−1, 1] such that ∥f ^(r)∥ _{C[−1, 1]} ≤ 1 and, for an arbitrary algebraic polynomial P ∈ Δ³ [−1, 1], there exists x such that

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

Invariant Subspaces for Banach Space Operators with a Multiply Connected Spectrum

We consider a multiply connected domain where denotes the unit disk and denotes the closed disk centered at with radius r _j for j = 1, . . . , n. We show that if T is a bounded linear operator on a Banach space X whose spectrum contains ∂Ω and does not contain the points λ₁, λ₂, . . . , λ _n , and the operators T and r _j (T − λ _j I)⁻¹ are polynomially bounded, then there exists a nontrivial common invariant subspace for T ^* and (T − λ _j I)^*-1.     

A Rank Theorem of Operators between Banach Spaces

Suppose that E and F are two Banach spaces and that B(E, F) is the space of all bounded linear operators from E to F. Let T ₀∈B(E, F) with a generalized inverse T ₀ ⁺∈B(F, E). This paper shows that, for every T∈B(E, F) with ‖T ₀ ⁺ (T−T ₀)‖<1, B ≡ (I + T ₀ ⁺(T−T ₀))⁻¹ T ₀ ⁺ is a generalized inverse of T if and only if (I−T ₀ ⁺ T ₀)N(T) = N(T ₀), where N(·) stands for the null space of the operator inside the parenthesis. This result improves a useful theorem of Nashed and Cheng and further shows that a lemma given by Nashed and Cheng is valid in the case where T ₀ is a semi-Fredholm operator but not in general.     

A note on quadratic forms

We extend an interesting theorem of Yuan [12] for two quadratic forms to three matrices. Let C ₁, C ₂, C ₃ be three symmetric matrices in ℜ ^n×n , if max{x ^T C ₁ x,x ^T C ₂ x,x ^T C ₃ x}≥0 for all x∈ℜ ⁿ , it is proved that there exist t _i ≥0 (i=1,2,3) such that ∑ _i=1 ³ t _i =1 and ∑ _i=1 ³ t _i C _i has at most one negative eigenvalue. Received February 18, 1997 / Revised version received October 1, 1997? Published online June 11, 1999     

Almost sure central limit theorems for random functions

Let {Xn,-∞< n <∞} be a sequence of independent identically distributed random variables with EX1 = 0, EX12 = 1 and let Sn =∑k=1∞Xk, and Tn = Tn(X1,…,Xn) be a random function such that Tn = ASn Rn, where supn E|Rn| <∞and Rn = o(n~(1/2)) a.s., or Rn = O(n1/2-2γ) a.s., 0 <γ< 1/8. In this paper, we prove the almost sure central limit theorem (ASCLT) and the function-typed almost sure central limit theorem (FASCLT) for the random function Tn. As a consequence, it can be shown that ASCLT and FASCLT also hold for U-statistics, Von-Mises statistics, linear processes, moving average processes, error variance estimates in linear models, power sums, product-limit estimators of a continuous distribution, product-limit estimators of a quantile function, etc.     

Analogues of the “zero-two” law for positive linear contractions inL p andC(X)

LetT be a positive linear contraction inL ^p (1≦p<∞), then we show that lim ‖T ^pf −T ⁿ⁺¹ f‖ _p ≦(1 − ε)2^1/p (f∈L _p ⁺ , ε>0 independent off) implies already lim_n n→∞ ‖T ⁿf −T ⁿ⁺¹ n+1f ‖_p p=0. Several other related results as well as uniform variants of these are also given. Finally some similar results inLsu/t8 andC(X) are shown.     

Fast diffusion flow on manifolds of nonpositive curvature

We consider the fast diffusion equation (FDE) u _t = Δu ^m (0 < m < 1) on a nonparabolic Riemannian manifold M. Existence of weak solutions holds. Then we show that the validity of Euclidean–type Sobolev inequalities implies that certain L ^p −L ^q smoothing effects of the type ∥u(t)∥ _q ≤ Ct ^−α ∥u ₀∥^γ _p , the case q = ∞ being included. The converse holds if m is sufficiently close to one. We then consider the case in which the manifold has the addition gap property min σ(−Δ) > 0. In that case solutions vanish in finite time, and we estimate from below and from above the extinction time.      

Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard

Given an m×n integer matrix A of full row rank, we consider the problem of computing the maximum of ∥B ^-1 A∥₂ where B varies over all bases of A. This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number was the determining factor in the complexity bound of Vavasis and Ye’s primal-dual interior-point algorithm. We prove that the problem of approximating this maximum norm, even within an exponential (in the dimension of A) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan [1]. Received November 13, 1998 / Revised version received January 20, 1999? Published online May 12, 1999     

L P boundedness of area function associated with operators on product spaces

Let L be the infinitesimal generator of an analytic semigroup on L2 (Rn) with suitable upper bounds on its heat kernels. Assume that L has a bounded holomorphic functional calculus on L2(Rn). In this paper,we define the Littlewood- Paley g function associated with L on Rn × Rn, denoted by GL(f)(x1, x2), and decomposition, we prove that ‖SL(f)‖p ≈‖GL(f)‖p ≈‖f‖p for 1 ＜ p ＜∞.     

Norm Attaining Operators and Pseudospectrum

It is shown that if 1 < p < ∞ and X is a subspace or a quotient of an ℓ_p-direct sum of finite dimensional Banach spaces, then for any compact operator T on X such that ∥I + T∥ > 1, the operator I + T attains its norm. A reflexive Banach space X and a bounded rank one operator T on X are constructed such that ∥I + T∥  > 1 and I + T does not attain its norm. The author would like to thank E. Shargorodsky for his interest and comments.     

An infeasible-interior-point potential-reduction algorithm for linear programming

n . The method is based on Rockafellar’s proximal point algorithm and a cutting-plane technique. At each step, we use an approximate proximal point p^a(x_k) of x_k to define a v_k∈∂_εkf(p^a(x_k)) with ε_k≤α∥v_k∥, where α is a constant. The method monitors the reduction in the value of ∥v_k∥ to identify when a line search on f should be used. The quasi-Newton step is used to reduce the value of ∥v_k∥. Without the differentiability of f, the method converges globally and the rate of convergence is Q-linear. Superlinear convergence is also discussed to extend the characterization result of Dennis and Moré. Numerical results show the good performance of the method. Received October 3, 1995 / Revised version received August 20, 1998 Published online January 20, 1999