Modifying the generalized singular value decomposition with application with application in direction-of-arrival finding

We consider updating and downdating problems for the generalized singular value decomposition (GSVD) of matrix pairs when new rows are added to one of the matrices or old rows are deleted. Two classes of algorithms are developed, one based on the CS decomposition formulation of the GSVD and the other based on the generalized eigenvalue decomposition formulation. In both cases we show that the updating and downdating problems can be reduced to a rank-one SVD updating problem. We also provide perturbation analysis for the cases when the added or deleted rows are subject to errors. Numerical experiments on direction-of-arrival (DOA) finding with colored noises are carried out to demonstrate the tracking ability of the algorithms. The work of the first author was supported in part by NSF grants CCR-9308399 and CCR-9619452. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

Spectral conditioning and pseudospectral growth

Using the language of pseudospectra, we study the behavior of matrix eigenvalues under two scales of matrix perturbation. First, we relate Lidskii’s analysis of small perturbations to a recent result of Karow on the growth rate of pseudospectra. Then, considering larger perturbations, we follow recent work of Alam and Bora in characterizing the distance from a given matrix to the set of matrices with multiple eigenvalues in terms of the number of connected components of pseudospectra. J. V. Burke’s research was supported in part by National Science Foundation Grant DMS-0505712. A. S. Lewis’s research was supported in part by National Science Foundation Grant DMS-0504032. M. L. Overton’s research was supported in part by National Science Foundation Grant DMS-0412049.     

Analysis of the generalized total least squares problemAX≈B when some columns ofA are free of error

Summary This paper studies the algebraic properties and perturbation theory of the generalized total least squares problem (GTLS)AXB in whichA =(A ₁,A ₂),A ₁ is free of error, and the error contained in (A ₂,B) is of the formEC withC a given nonsingular matrix. The problem was proposed by Van Huffel and Vandewalle in [15]. The solvability conditions, formulas for the GTLS solutions, their residuals, and the minimum norm correction matrices are obtained, and a perturbation theory for the GTLS problem is given.This author was supported by NSERC of Canada Grant No. A9236This author was supported by the National Natural Sciences Foundation, P.R. China. This work was carried out when this author was visiting the School of Computer Science. McGill University, Montreal, Quebec, Canada     

On perturbation bounds of generalized eigenvalues for diagonalizable pairs

The purpose of this paper is to study the perturbation of generalized eigenvalues. Two perturbation bounds of the diagonalizable pairs are given. These results extend the corresponding ones given by Sun (Math Numer Sinica 4:23–29, 1982). This work is supported by the Natural Science Foundation of Guangdong Province (No. 06025061) and by the National Natural Science Foundations of China (No. 10671077 and 10626021).     

On computingINV block preconditionings for the conjugate gradient method

The INV(k) and MINV(k) block preconditionings for the conjugate gradient method require generation of selected elements of the inverses of symmetric matrices of bandwidth 2k+1. Generalizing the previously describedk=1 (tridiagonal) case tok=2, explicit expressions for the inverse elements of a symmetric pentadiagonal matrix in terms of Green's matrix of rank two are given. These expressions are found to be seriously ill-conditioned; hence alternative computational algorithms for the inverse elements must be used. Behavior of thek=1 andk=2 preconditionings are compared for some discretized elliptic partial differential equation test problems in two dimensions.Presented by the first author at the Joint U.S.-Scandinavian Symposium on Scientific Computing and Mathematical Modeling, January 1985, in honor of Germund Dahlquist on the occasion of his 60th birthday. This work was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE AC03-76SF00098.     

Polar decompositions and related classes of operators in spaces ∏κ

Polar decompositions with respect to an indefinite inner product are studied for bounded linear operators acting on a space. Criteria are given for existence of various forms of the polar decompositions, under the conditions that the range of a given operatorX is closed and that zero is not an irregular critical point of the selfadjoint operatorX ^[*]X. Both real and complex spaces are considered. Relevant classes of operators having a selfadjoint (in the sense of the indefinite inner product) square root, or a selfadjoint logarithm, are characterized.The work of this author was partially supported by INdAM-GNCS and MURSTThe work of this author was partially supported by NSF grant DMS-9988579.     

Weighted least squares solutions to general coupled Sylvester matrix equations

This paper is concerned with weighted least squares solutions to general coupled Sylvester matrix equations. Gradient based iterative algorithms are proposed to solve this problem. This type of iterative algorithm includes a wide class of iterative algorithms, and two special cases of them are studied in detail in this paper. Necessary and sufficient conditions guaranteeing the convergence of the proposed algorithms are presented. Sufficient conditions that are easy to compute are also given. The optimal step sizes such that the convergence rates of the algorithms, which are properly defined in this paper, are maximized and established. Several special cases of the weighted least squares problem, such as a least squares solution to the coupled Sylvester matrix equations problem, solutions to the general coupled Sylvester matrix equations problem, and a weighted least squares solution to the linear matrix equation problem are simultaneously solved. Several numerical examples are given to illustrate the effectiveness of the proposed algorithms.     

Perturbation and error analyses for block downdating of a Cholesky decomposition

A new perturbation result is presented for the problem of block downdating a Cholesky decompositionX ^T X = R ^T R. Then, a condition number for block downdating is proposed and compared to other downdating condition numbers presented in literature recently. This new condition number is shown to give a tighter bound in many cases. Using the perturbation theory, an error analysis is presented for the block downdating algorithms based on the LINPACK downdating algorithm and stabilized hyperbolic transformations. An error analysis is also given for block downdating using Corrected Seminormal Equations (CSNE), and it is shown that for ill-conditioned downdates this method gives more accurate results than the algorithms based on the LINPACK downdating algorithm or hyperbolic transformations. We classify the problems for which the CSNE downdating method produces a downdated upper triangular matrix which is comparable in accuracy to the upper triangular factor obtained from the QR decomposition by Householder transformations on the data matrix with the row block deleted.Dedicated to Ji-guang Sun in honour of his 60th birthdayThe work of the second author was supported in part by the National Science Foundation grant CCR-9209726.     

Continuation of Singular Value Decompositions

In this work we consider computing a smooth path for a (block) singular value decomposition of a full rank matrix valued function. We give new theoretical results and then introduce and implement several algorithms to compute a smooth path. We illustrate performance of the algorithms with a few numerical examples.This work was supported in part under NSF Grant DMS-0139895, and INDAM-GNCS and MIUR Rome-Italy.     

Theory and method for updating least-squares finite element model of symmetric generalized centro-symmetric matrices

Let X,F$X,F$ be a displacement matrix and load matrix, respectively. C (obtained by calculations or measurements) is an estimate matrix of the analytical model. A method is presented for correction of the model C, based on the theory of inverse problem of matrices. The corrected model is symmetric generalized centro-symmetric with specified displacements and loads, satisfying the mechanics characters of finite-element model. The application of the method is illustrated. It is more important that a perturbation analysis is given, which is not given in the earlier papers. Numerical results show that the method is feasible and effective.     

Random Points in the Unit Ball of ℓ n p

We show that two limit results from random matrix theory, due to Marčenko–Pastur and Bai–Yin, are also valid for matrices with independent rows (as opposed to independent entries in the classical theory), when rows are uniformly distributed on the unit ball of ℓⁿ_p, under proper normalization. Research was supported in part by the European Network PHD, FP6 Marie Curie Actions, MCRN-511953 and was done in part while the author was visiting the University of Athens.     

A look-ahead algorithm for the solution of general Hankel systems

Summary The solution of systems of linear equations with Hankel coefficient matrices can be computed with onlyO(n ²) arithmetic operations, as compared toO(n ³) operations for the general cases. However, the classical Hankel solvers require the nonsingularity of all leading principal submatrices of the Hankel matrix. The known extensions of these algorithms to general Hankel systems can handle only exactly singular submatrices, but not ill-conditioned ones, and hence they are numerically unstable. In this paper, a stable procedure for solving general nonsingular Hankel systems is presented, using a look-ahead technique to skip over singular or ill-conditioned submatrices. The proposed approach is based on a look-ahead variant of the nonsymmetric Lanczos process that was recently developed by Freund, Gutknecht, and Nachtigal. We first derive a somewhat more general formulation of this look-ahead Lanczos algorithm in terms of formally orthogonal polynomials, which then yields the look-ahead Hankel solver as a special case. We prove some general properties of the resulting look-ahead algorithm for formally orthogonal polynomials. These results are then utilized in the implementation of the Hankel solver. We report some numerical experiments for Hankel systems with ill-conditioned submatrices.The research of the first author was supported by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).The research of the second author was supported in part by NSF grant DRC-8412314 and Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).     

Note on structured indefinite perturbations to Hermitian matrices

In a recent paper, Overton and Van Dooren have considered structured indefinite perturbations to a given Hermitian matrix. We extend their results to skew-Hermitian, Hamiltonian and skew-Hamiltonian matrices. As an application, we give a formula for computation of the smallest perturbation with a special structure, which makes a given Hamiltonian matrix own a purely imaginary eigenvalue.     

Eigenvalues of symmetrizable matrices

New perturbation theorems for matrices similar to Hermitian matrices are proved for a class of unitarily invariant norms calledQ-norms. These theorems improve known results in certain circumstances and extend Lu's theorems for the spectral norm, see [Numerical Mathematics: a Journal of Chinese Universities, 16 (1994), pp. 177–185] toQ-norms. This material is based in part upon the third author's work supported from August 1995 to December 1997 by a Householder Fellowship in Scientific Computing at Oak Ridge National Laboratory, supported by the Applied Mathematical Sciences Research Program, Office of Energy Research, United States Department of Energy contract DE-AC05-96OR22464 with Lockheed Martin Energy Research Corp.     

Consistency of infinitesimal perturbation analysis estimators with rates

We study a class of infinitesimal perturbation analysis (IPA) algorithms for queueing systems with load-dependent service and/or arrival rates. Such IPA algorithms were originally motivated by applications to large queueing systems in conjunction with aggregation algorithms. We prove strong consistency of these estimators through a type of birth and death queue. This work was supported in part by the NSF under Grants Nos. ECS85-15449 and CDR-8803012, by ONR under Contracts Nos. N00014-89-J-0075 and N00014-90-K-1093, and by the US Army under Contract No. DAAL-03-83-K-0171. This paper was written while the author was with the Division of Applied Sciences at Harvard University.     

Local minimal factorizations of rational matrix functions in terms of null and pole data: Formulas for factors

It is known that local minimal factorizations of a rational matrix function can be described in terms of local null and pole data (expressed in the form of left null-pole triples and their corestrictions) of this function. In this paper we give formulas for the factors in a local minimal factorization that corresponds to a given corestriction of the left null-pole triple.The first version of this paper was written while the second author visited the College of William and Mary.Partially supported by the NSF grant DMS-8802836 and by the Binational United States-Israel Foundation grant.     

Instability indices for matrix polynomials

There is a well-established instability index theory for linear and quadratic matrix polynomials for which the coefficient matrices are Hermitian and skew-Hermitian. This theory relates the number of negative directions for the matrix coefficients which are Hermitian to the total number of unstable eigenvalues for the polynomial. Herein we extend the theory to ?-even matrix polynomials of any finite degree. In particular, unlike previously known cases we show that the instability index depends upon the size of the matrices when the degree of the polynomial is greater than two. We also consider Hermitian matrix polynomials, and derive an index which counts the number of eigenvalues with nonpositive imaginary part. The results are refined if we consider the Hermitian matrix polynomial to be a perturbation of a ?-even polynomials; however, this refinement requires additional assumptions on the matrix coefficients.     

Entrywise relative perturbation bounds for exponentials of essentially non-negative matrices

A real square matrix is said to be essentially non-negative if all of its off-diagonal entries are non-negative. We establish entrywise relative perturbation bounds for the exponential of an essentially non-negative matrix. Our bounds are sharp and contain a condition number that is intrinsic to the exponential function. As an application, we study sensitivity of continuous-time Markov chains. J. Xue was supported by the National Science Foundation of China under grant number 10571031, the Program for New Century Excellent Talents in Universities of China and Shanghai Pujiang Program. Q. Ye was supported in part by NSF under Grant DMS-0411502.