Characterizations of the Poisson process as a renewal process via two conditional moments

Given two independent positive random variables, under some minor conditions, it is known that fromE(X^rX+Y)=a(X+Y)^r andE(X^sX+Y)=b(X+Y)^s, for certain pairs ofr ands, wherea andb are two constants, we can characterizeX andY to have gamma distributions. Inspired by this, in this article we will characterize the Poisson process among the class of renewal processes via two conditional moments. More precisely, let {A(t), t0} be a renewal process, with {S _k, k1} the sequence of arrival times, andF the common distribution function of the inter-arrival times. We prove that for some fixedn andk, kn, ifE(S _k ^r A(t)=n)=at^r andE(S _k ^s A(t)=n)=bt^s, for certain pairs ofr ands, wherea andb are independent oft, then {A(t), t0} has to be a Poisson process. We also give some corresponding results about characterizingFto be geometric whenF is discrete.Support for this research was provided in part by the National Science Council of the Republic of China, Grant No. NSC 81-0208-M110-06.     

An eigenvalue problem for the numerical range of a bounded linear operator

LetX be a complex Lebesgue space with a unique duality mapJ fromX toX ^*, the conjugate space ofX. LetA be a bounded linear operator onX. In this paper we obtain a non-linear eigenvalue problem for (A)=sup{Re: W(A} whereW(A)={J(x)A(x)) : x=1}, under the assumption that (A) and the convex hull ofW(A) for some linear operatorsA onl _p , 2<p<.     

Perturbation theory for pseudo-inverses

A perturbation theory for pseudo-inverses is developed. The theory is based on a useful decomposition (theorem 2.1) ofB ⁺ -A ⁺ whereB andA arem ×n matrices. Sharp estimates of B ⁺ -A ⁺ are derived for unitary invariant norms whenA andB are of the same rank and B -A is small. Under similar conditions the perturbation of a linear systemAx=b is studied. Realistic bounds on the perturbation ofx=A ⁺ b andr=b=Ax are given. Finally it is seen thatA ⁺ andB ⁺ can be compared if and only ifR(A) andR(B) as well asR(A ^H ) andR(B ^H ) are in the acute case. Some theorems valid only in the acute case are also proved.This work was sponsored in part by The Swedish Institute of Applied Mathematics.     

Interpolation problems and Toeplitz operators on multiply connected domains

LetR be a bounded domain in the complex plane bounded by n + 1 nonintersecting analytic Jordan curves, letE, F, andG be flat unitary vector bundles (in the sense of Abrahamse and Douglas) and let :F G and :E G be bounded analytic bundle maps. A condition is given for the existence of a bounded analytic map D:E F such that D = , together with an estimate for D. An interesting special case is the case whereE = G and = I _E , for which the condition involves a uniform lower bound for a class of Toeplitz operators overR, all of which are induced (formally) by the bundle map (N = rankE). When interpreted for a finite column of analytic scalar functions, this special case gives quantitative information on the corona theorem forR. The main tool is the Sz.Nagy-Foias commutant lifting theorem for regionsR recently obtained by the author.Research supported by National Science Foundation Grant No. MCS 77-00966.     

A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

We address the problem of finding a minimum weight baseB of a matroid when, in addition, each element of the matroid is colored with one ofm colors and there are upper and lower bound restrictions on the number of elements ofB with colori, fori = 1, 2,,m. This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity O(|EV|+|V| ²log|V|). HereV denotes the node set of the underlying bipartite graph, andE denotes its edge set. The second application is defined on a general connected graphG = (V,E) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with colori in the tree, for eachi. Our algorithm for this problem has complexity O(|EV|+m ² |V|+ m|V| ²). A special case of this constrained spanning tree problem occurs whenV ^* is a set of pairwise nonadjacent nodes ofG. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node ofV ^*. Then the complexity of our algorithm is O(|VE|+|V ^* V| ²). Finally, we discuss a new relaxation of the traveling salesman problem.This report was supported in part by NSF grant ECS 8601660.     

On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials

LetS be a triangulation of andf(z) = z ^d +a _d–1 z ^d–1++a ₀, a complex polynomial. LetF be the piecewise linear approximation off determined byS. For certainS, we establish an upper bound on the complexity of an algorithm which finds zeros ofF. This bound is a polynomial in terms ofn, max{a _i } _i , and measures of the sizes of simplices inS.     

Numerical decomposition of a convex function

Given then×p orthogonal matrixA and the convex functionf:R ⁿR, we find two orthogonal matricesP andQ such thatf is almost constant on the convex hull of ± the columns ofP, f is sufficiently nonconstant on the column space ofQ, and the column spaces ofP andQ provide an orthogonal direct sum decomposition of the column space ofA. This provides a numerically stable algorithm for calculating the cone of directions of constancy, at a pointx, of a convex function. Applications to convex programming are discussed.This work was supported by the National Science and Engineering Research Council of Canada (Grant No. A3388 and Summer Grant).     

Regular and normal closure operators and categorical compactness for groups

For a class of groupsF, closed under formation of subgroups and products, we call a subgroupA of a groupG F-regular provided there are two homomorphismsf, g: G » F, withF F, so thatA = {x G |f(x) =g(x)}.A is calledF-normal providedA is normal inG andG/A F. For an arbitrary subgroupA ofG, theF-regular (respectively,F-normal) closure ofA inG is the intersection of allF-regular (respectively,F-normal) subgroups ofG containingA. This process gives rise to two well behaved idempotent closure operators.A groupG is calledF-regular (respectively,F-normal) compact provided for every groupH, andF-regular (respectively,F-normal) subgroupA ofG × H, ₂(A) is anF-regular (respectively,F-normal) subgroup ofH. This generalizes the well known Kuratowski-Mrówka theorem for topological compactness.In this paper, theF-regular compact andF-normal compact groups are characterized for the classesF consisting of: all torsion-free groups, allR-groups, and all torsion-free abelian groups. In doing so, new classes of groups having nice properties are introduced about which little is known.     

Norm bounds for rational matrix functions

Summary If the field of values of a matrixA is contained in the left complex halfplaneH and a functionf mapsH into the unit disc then f(A)₂1 by a theorem of J.v. Neumann. We prove a theorem of this type, only the field of values ofA is used for functions which are absolutely bounded by one in only part ofH. An extension can be used to show norm-stability of single step methods for stiff differential equations. The results are applicable among others to several subdiagonal Padé approximations which are notA-stable.     

Time-optimal controls of the equation of evolution in a separable and reflexive Banach space

Let a variable, closed, bounded, and convex subset ofX, a separable and reflexive Banach space, be denoted byG(t). Suppose thatG(t) varies upper-semicontinuously with respect to inclusion ast varies in [0,T]. We say that the strongly measurable mapu from [0,T] toX is an admissible control if, for almost everyt in [0,T],u(t) is an element ofU, a closed, bounded, and convex subset ofX, and u _p M ^1p, where p>1 andM>0.Ifx ^u is the weak solution todx/dt+A(t)x=u(t), 0tT, whereA(t) is as defined by Tanabe in Ref. 1, we say that the responsex ^u to the controlu hits the target in timeT ^u ifx ^u (0)=0 andx ^u (T ^u ) is an element ofG(T ^u ). If there is a control with this property, then there is a time-optimal control.     

Convex minimization under Lipschitz constraints

We consider the problem of minimizing a convex functionf(x) under Lipschitz constraintsf _i (x)0,i=1,...,m. By transforming a system of Lipschitz constraintsf _i (x)0,i=l,...,m, into a single constraints of the formh(x)-x²0, withh(·) being a closed convex function, we convert the problem into a convex program with an additional reverse convex constraint. Under a regularity assumption, we apply Tuy's method for convex programs with an additional reverse convex constraint to solve the converted problem. By this way, we construct an algorithm which reduces the problem to a sequence of subproblems of minimizing a concave, quadratic, separable function over a polytope. Finally, we show how the algorithm can be used for the decomposition of Lipschitz optimization problems involving relatively few nonconvex variables.     

Constrained minimax approximation and optimal preconditioned for Toeplitz matrices

A good preconditioner is extremely important in order for the conjugate gradients method to converge quickly. In the case of Toeplitz matrices, a number of recent studies were made to relate approximation of functions to good preconditioners. In this paper, we present a new result relating the quality of the Toeplitz preconditionerC for the Toeplitz matrixT to the Chebyshev norm (f– g)/f, wheref and g are the generating functions forT andC, respectively. In particular, the construction of band-Toeplitz preconditioners becomes a linear minimax approximation problem. The case whenf has zeros (but is nonnegative) is especially interesting and the corresponding approximation problem becomes constrained. We show how the Remez algorithm can be modified to handle the constraints. Numerical experiments confirming the theoretical results are presented.     

Isometries of JB-algebras

A bijective linear mapping between two JB-algebrasA andB is an isometry if and only if it commutes with the Jordan triple products ofA andB. Other algebraic characterizations of isometries between JB-algebras are given. Derivations on a JB-algebraA are those bounded linear operators onA with zero numerical range. For JB-algebras of selfadjoint operators we have: IfH andK are left Hilbert spaces of dimension ≥3 over the same fieldF (the real, complex, or quaternion numbers), then every surjective real linear isometryf fromS(H) ontoS(K) is of the formf(x)=UoxoU ⁻¹ forx inS(H), whereτ is a real-linear automorphism ofF andU is a real linear isometry fromH ontoK withU(λh)=τ(λ)U(h) for λ inF andh inH. Supported by Acción Integrada Hispano-Alemana HA 94 066 B     

Testing linear operators—An average case study

Given a specification linear operatorS, we want to test an implementation linear operatorA and determine whether it conforms to the specification operator according to an error criterion. In an earlier paper [3], we studied a worst case error in which we test whether the error is no more than a given bound ε>0 for all elements in a given setF, i.e., sup _{fεf∥Sf—Af∥≤ε}. In this work, we study the average error instead, i. e., ∫ _F ∥Sf-Af∥²μ(df)ɛ≤², where μ is a probability measure onF. We assume that an upper boundK on the norm of the difference ofS andA is given a priori. It turns out that any finite number of tests is in general inconclusive with the average error. Therefore, as in the worst case, we allow a relaxation parameter α>0 and test for weak conformance with an error bound (1+α)ε. Then a finite number of tests from an arbitrary orthogonal complete sequence is conclusive. Furthermore, the eigenvectors of the covariance operatorC _μ of the probability measure μ provide an almost optimal test sequence. This implies that the test set isuniversal; it only depends on the set of valid inputsF and the measure μ, and is independent ofS, A, and the other parameters of the problem. However, the minimal number of tests does depend on all the parameters of the testing problem, i.e., ε, α,K, and the eigenvalues ofC _μ. In contrast to the worst case setting, it also depends on the dimensiond of the range space ofS andA. This work was done while consulting at Bell Laboratories, and is partially supported by the National Science Foundation and the Air Force Office of Scientific Research.     

Galerkin method and optimal error algorithms in hilbert spaces

Summary We consider operator equations of the formLu=f, whereL belongs to the class of linear, bounded (by a constantM) and coercive (with a constantm) operators from a Hilbert spaceV onto its dualV ^* andf belongs to a Hilbert spaceWV ^*. We study optimality of the Galerkin methodP _n ^* Lu _n =P _n ^* f, whereu _n V _n ,V _n is subspace ofV, P _n is the orthogonal projector ontoV _n andP _n ^* is dual toP _n . We show that the Galerkin method is quasi optimal independently of the choice of the subspaceV _n and the spaceW ifM>m. In the caseM=m, optimality of the method depends strongly on the choice ofV _n andW. Therefore we define a new algorithm which is always optimal (independently of the choice ofV _n andW and relations betweenM andm).     

Jordan axioms for C*-algebras

A complex Banach spaceA which is also an associative algebra provided with a conjugate linear vector space involution * satisfying (a ²)^*=(a ^*)², aa ^* a=a³ and ab+ba2ab for alla, b inA is shown to be a C^*-algebra. The assumptions onA can be expressed in terms of the Jordan algebra obtained by symmetrization of the product ofA and are satisfied by any C^*-algebra. Thus we obtain a purely Jordan characterization of C^*-algebras.     

On bending of a convex surface to a convex surface with prescribed spherical image

We prove the following theorem. LetF be a regular convex surface homeomorphic to the disk. Suppose the Gaussian curvature ofF is positive and the geodesic curvature of its boundary is positive as well. LetG be a convex domain on the unit sphere bounded by a smooth curve and strictly contained in a hemisphere. LetP be an arbitrary point on the boundary ofF andP ^* be an arbitrary point on the boundary ofG. If the area ofG is equal to the integral curvature of the surfaceF, then there exists a continuous bending of the surfaceF to a convex surfaceF such that the spherical image ofF coincides withG andP ^* is the image of the point inF corresponding to the pointP F under the isometry.Translated fromMatematicheskie Zametki, Vol. 58, No. 2, pp. 295–300, August, 1995.     

Quadratic spline interpolation on uniform meshes

The interpolation problem at uniform mesh points of a quadratic splines(x _i)=f _i,i=0, 1,...,N ands(x ₀)=f₀ is considered. It is known that s–f=O(h ³) and s–f=O(h ²), whereh is the step size, and that these orders cannot be improved. Contrary to recently published results we prove that superconvergence cannot occur for any particular point independent off other than mesh points wheres=f by assumption. Best error bounds for some compound formulae approximatingf _i andf _i ⁽³⁾ are also derived.     

Solutions of equations involving analytic functions in a Banach algebra

In this paper, we discuss the existence and uniqueness of solution of an equationf(x)=a in a Banach algebra. We have the following fundamental lemma:LetA be a Banach algebra with identity,U be an open subset of complex planeC,f be an univalent function inU, V =f(U), a A. If the spectral set ofa, (a) V, then there exists an uniquex A, such that(x)U, andf (x) = a.Using this lemma, we can get generalizations of corresponding results in [1–8]. Moreover, we also give a generalization of the fundamental theorem on special solution in [3].     

Classification of pairs of subspaces in scalar product spaces

Up to the classification of Hermitian forms a classification has been given of triplesP=(V_F; U₁, U₂), consisting of a finite dimensional vector space V over a field of characteristic 2 with a symmetric, or a skew-symmetric, or Hermitian form F and two subspaces U₁, U₂. Two triplesP andP are identified with each other if there exists an isometry V_f V_f such that (U_i)=U_i, i=1, 2.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 4, pp. 549–554, April, 1990.