Nonlinearity inH ∞-control theory,causality in the commutant lifting theorem,and extension of intertwining operators

The problems studied in this note have been motivated by our work in generalizing linearH control theory to nonlinear systems. These ideas have led to a design procedure applicable to analytic nonlinear plants. Our technique is a generalization of the linearH theory. In contrast to previous work on this topic ([9], [10]), we now are able to explicitly incorporate a causality constraint into the theory. In fact, we show that it is possible to reduce a causal optimal design problem (for nonlinear systems) to a classical interpolation problem solvable by the commutant lifting theorem [8]. Here we present the complete operator theoretical background of our research together with a short control theoretical motivation.This work was supported in part by grants from the Research Fund of Indiana University, the National Science Foundation DMS-8811084 and ECS-9122106, by the Air Force Office of Scientific Research F49620-94-1-0098DEF, and by the Army Research Office DAAL03-91-G-0019 and DAAH04-93-G-0332     

Continuity of the spectrum on closed similarity orbits

We present a useful case when the spectral radius of a norm limit of operator similar to a fixed operatorT still equals that ofT.This work was supported in part by grants from the National Science Foundation DMS-8811084, ECS-9001371, ECS-9122106, by the Air Force Office of Scientific Research AFOSR-90-0024 and AFOSR-90-0053, and by the Army Research Office DAAL03-91-G-0019.     

A Naimark Dilation Perspective of Nevanlinna-Pick Interpolation

In this paper a positive real tangential Nevanlinna-Pick interpolation problem with interpolation at operator points is solved. The Naimark dilation theorem together with the state space method from systems theory are used to obtain a parameterization for the set of all solutions. Explicit state space formulas are given for both the singular and non-ingular case. In the proofs the solution of an intermediate isometric extension problem plays an important role.     

On completeness of the spectral domain of harmonizable processes

Summary The spectral domain of harmonizable processes is studied and a criterion for its completeness is obtained. It is shown that even for periodically correlated processes the spectral domain need not be complete.This work was funded in part by Office of Naval Research grant N00014-89-J-1824 and in part by US Army Research Office grant DAAL 03-91-G-0238. Part of these results has been presented at the May 1993 AMS meeting in DeKalb; ref. nr. 882-28-69     

A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes

We give several additive Schwarz domain decomposition methods for solving finite element problems which arise from the discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Our theory requires no assumption (for the main results) on the substructures which constitute the whole domain, so each substructure can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved and both the coarse meshes and the fine meshes need not be quasi-uniform. In this general setting, our algorithms have the same optimal convergence rate of the usual domain decomposition methods on structured meshes. The condition numbers of the preconditioned systems depend only on the (possibly small) overlap of the substructures and the size of the coares grid, but is independent of the sizes of the subdomains.Revised version on Sept. 20, 1994. Original version: CAM Report 93-40, Dec. 1993, Dept. of Math., UCLA.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and ONR under contract ONR-N00014-92-J-1890.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and subcontract DAAL03-91-C-0047.     

Eigenvalue perturbation theory of classes of structured matrices under generic structured rank one perturbations

udy the perturbation theory of structured matrices under structured rank one perturbations, and then focus on several classes of complex matrices. Generic Jordan structures of perturbed matrices are identified. It is shown that the perturbation behavior of the Jordan structures in the case of singular J-Hamiltonian matrices is substantially different from the corresponding theory for unstructured generic rank one perturbation as it has been studied in [18, 28, 30, 31]. Thus a generic structured perturbation would not be generic if considered as an unstructured perturbation. In other settings of structured matrices, the generic perturbation behavior of the Jordan structures, within the confines imposed by the structure, follows the pattern of that of unstructured perturbations.     

On an intertwining lifting theorem for certain reproducing kernel Hilbert spaces

We provide an alternate approach to an intertwining lifting theorem obtained by Ball, Trent and Vinnikov. The results are an exact analogue of the classical Sz-Nagy-Foias theorem in the case of multipliers on a class of reproducing kernel spaces, which satisfy the Nevanlinna-Pick property.     

Tangential Nevanlinna-Pick Interpolation and Its Connection with Hamburger Matrix Moment Problem

This paper is concerned with the solution of a certain tangential Nevanlinna-Pick interpolation for Nevanlinna functions. We use the so-called block Hankel vector method to establish two intrinsic connections between the tangential Nevanlinna-Pick interpolation in the Nevanlinna class and the truncated Hamburger matrix moment problem associated with the block Hankel vector under consideration: one is a congruent relationship between their information matrices, and the other is a divisor-remainder connection between their solutions. These investigations generalize our previous work on the Nevanlinna-Pick interpolation and power matrix moment problem.     

The Schur algorithm and its applications

The Schur algorithm and its time-domain counterpart, the fast Cholseky recursions, are some efficient signal processing algorithms which are well adapted to the study of inverse scattering problems. These algorithms use a layer stripping approach to reconstruct a lossless scattering medium described by symmetric two-component wave equations which model the interaction of right and left propagating waves. In this paper, the Schur and fast Chokesky recursions are presented and are used to study several inverse problems such as the reconstruction of nonuniform lossless transmission lines, the inverse problem for a layered acoustic medium, and the linear least-squares estimation of stationary stochastic processes. The inverse scattering problem for asymmetric two-component wave equations corresponding to lossy media is also examined and solved by using two coupled sets of Schur recursions. This procedure is then applied to the inverse problem for lossy transmission lines.The work of this author was supported by the Exxon Education FoundationThe work of this author was supported by the Air Force Office of Scientific Research under Grant AFOSR-82-0135A.     

Multidimensional constant linear systems

A continuous resp. discrete r-dimensional (r1) system is the solution space of a system of linear partial differential resp. difference equations with constant coefficients for a vector of functions or distributions in r variables resp. of r-fold indexed sequences. Although such linear systems, both multidimensional and multivariable, have been used and studied in analysis and algebra for a long time, for instance by Ehrenpreis et al. thirty years ago, these systems have only recently been recognized as objects of special significance for system theory and for technical applications. Their introduction in this context in the discrete one-dimensional (r=1) case is due to J. C. Willems. The main duality theorem of this paper establishes a categorical duality between these multidimensional systems and finitely generated modules over the polynomial algebra in r indeterminates by making use of deep results in the areas of partial differential equations, several complex variables and algebra. This duality theorem makes many notions and theorems from algebra available for system theoretic considerations. This strategy is pursued here in several directions and is similar to the use of polynomial algebra in the standard one-dimensional theory, but mathematically more difficult. The following subjects are treated: input-output structures of systems and their transfer matrix, signal flow spaces and graphs of systems and block diagrams, transfer equivalence and (minimal) realizations, controllability and observability, rank singularities and their connection with the integral respresentation theorem, invertible systems, the constructive solution of the Cauchy problem and convolutional transfer operators for discrete systems. Several constructions on the basis of the Gröbner basis algorithms are executed. The connections with other approaches to multidimensional systems are established as far as possible (to the author).Partially supported by US Air Force Grant AFOSR-87-0249 and by Office of Naval Research Grant N 00014-86-K-0538 through the Center for Mathematical System Theory, University of Florida, Gainesville, Florida, U.S.A.     

Some mathematical problems in computer vision

Several interesting mathematical problems arising in computer vision are discussed. Computer vision deals with image understanding at various levels. At the low level, it addresses issues like segmentation, edge detection, planar shape recognition and analysis. Classical results on differential invariants associated to planar curves are relevant to planar object recognition under partial occlusion, and recent results concerning the evolution of closed planar shapes under curvature controlled diffusion have found applications in shape decomposition and analysis. At higher levels, computer vision problems deal with attempts to invert imaging projections and shading processes toward depth recovery, spatial shape recognition and motion analysis. In this context, the recovery of depth from shaded images of objects with smooth, diffuse surfaces require the solution of nonlinear partial differential equations. Here results on differential equations, as well as interesting results from low-dimensional topology and differential geometry are the necessary tools of the trade. We are still far from being able to equip our computers with brains capable to analyze and understand the images that can easily be acquired with camera-eyes; however the research effort in this area often calls for both classical and recent mathematical results.This work was supported in part by NSF grant DMS-8811084, Air Force Office of Scientific Research Grant AFOSR-90-0024, and the Army Research Office DAAL03-91-G-0019, and by the Technion Fund for Promotion of Research.     

Newton's method for a class of nonsmooth functions

This paper presents and justifies a Newton iterative process for finding zeros of functions admitting a certain type of approximation. This class includes smooth functions as well as nonsmooth reformulations of variational inequalities. We prove for this method an analogue of the fundamental local convergence theorem of Kantorovich including optimal error bounds.The research reported here was sponsored by the National Science Foundation under Grants CCR-8801489 and CCR-9109345, by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and F49620-93-1-0068, by the U. S. Army Research Office under Grant No. DAAL03-92-G-0408, and by the U. S. Army Space and Strategic Defense Command under Contract No. DASG60-91-C-0144. The U. S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

A composite step bi-conjugate gradient algorithm for nonsymmetric linear systems

The Bi-Conjugate Gradient (BCG) algorithm is the simplest and most natural generalization of the classical conjugate gradient method for solving nonsymmetric linear systems. It is well-known that the method suffers from two kinds of breakdowns. The first is due to the breakdown of the underlying Lanczos process and the second is due to the fact that some iterates are not well-defined by the Galerkin condition on the associated Krylov subspaces. In this paper, we derive a simple modification of the BCG algorithm, the Composite Step BCG (CSBCG) algorithm, which is able to compute all the well-defined BCG iterates stably, assuming that the underlying Lanczos process does not break down. The main idea is to skip over a step for which the BCG iterate is not defined.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contracts N00014-90J-1695 and N00014-92J-1890, the Department of Energy under contract DE-FG03-87ER25307, the National Science Foundation under contracts ASC 90-03002 and 92-01266, and the Army Research Office under contract DAAL03-91-G-0150. Part of this work was completed during a visit to the Computer Science Dept., The Chinese University of Hong Kong.     

Multiparametric dissipative linear stationary dynamical scattering systems: Discrete case, II: Existence of conservative dilations

In the present paper we introduce the notion of dilation of a multiparametric linear stationary dynamical system (systems of this type, in particular dissipative, and conservative scattering ones were first introduced in [6]). We establish the criterion for existence of a conservative dilation of a multiparametric dissipative scattering system. This allows to distinguish the class of so-calledN-dissipative systems preserving the most important properties of one-parametric dissipative scattering systems.Research supported in part by the Ukrainian-Israeli project of scientific co-operation (contract no. 2M/1516-97).     

Estimating the largest singular values of large sparse matrices via modified moments

We describe a procedure for determining a few of the largest singular values of a large sparse matrix. The method by Golub and Kent which uses the method of modified moments for estimating the eigenvalues of operators used in iterative methods for the solution of linear systems of equations is appropriately modified in order to generate a sequence of bidiagonal matrices whose singular values approximate those of the original sparse matrix. A simple Lanczos recursion is proposed for determining the corresponding left and right singular vectors. The potential asynchronous computation of the bidiagonal matrices using modified moments with the iterations of an adapted Chebyshev semi-iterative (CSI) method is an attractive feature for parallel computers. Comparisons in efficiency and accuracy with an appropriate Lanczos algorithm (with selective re-orthogonalization) are presented on large sparse (rectangular) matrices arising from applications such as information retrieval and seismic reflection tomography. This procedure is essentially motivated by the theory of moments and Gauss quadrature.This author's work was supported by the National Science Foundation under grants NSF CCR-8717492 and CCR-910000N (NCSA), the U.S. Department of Energy under grant DOE DE-FG02-85ER25001, and the Air Force Office of Scientific Research under grant AFOSR-90-0044 while at the University of Illinois at Urbana-Champaign Center for Supercomputing Research and Development.This author's work was supported by the U.S. Army Research Office under grant DAAL03-90-G-0105, and the National Science Foundation under grant NSF DCR-8412314.     

A note on the existence, uniqueness and symmetry of par-balanced realizations

We give a proof of the realization theorem of N.J. Young which states that analytic functions which are symbols of bounded Hankel operators admit par-balanced realizations. The main tool used in this proof is the induced Hilbert spaces and a lifting lemma of Kreîn-Reid-Lax-Dieudonné. Alternatively one can use the Loewner inequality. A short proof of the uniqueness of par-balanced realizations is included. As an application, it is proved that par-balanced realizations of real symmetric transfer functions areJ-self-adjoint.Research supported in part by the Romanian Academy grant GAR-6645/1996.This research was supported in part by NSF grant DMS-9501223.     

The weighted commutant lifting theorem in the coupling approach

A simple coupling argument is seen to provide an alternate proof of the weighted commutant lifting theorem of Biswas, Foias and Frazho (which includes, as a particular case, the abstract Nehari theorem of Treil and Volberg).