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.     

Accuracy of TSVD solutions computed from rank-revealing decompositions

Summary. Rank-revealing decompositions are favorable alternatives to the singular value decomposition (SVD) because they are faster to compute and easier to update. Although they do not yield all the information that the SVD does, they yield enough information to solve various problems because they provide accurate bases for the relevant subspaces. In this paper we consider rank-revealing decompositions in computing estimates of the truncated SVD (TSVD) solution to an overdetermined system of linear equations , where is numerically rank deficient. We derive analytical bounds which show how the accuracy of the solution is intimately connected to the quality of the subspaces. Received July 12, 1993 / Revised version received November 14, 1994     

Perturbation analysis for block downdating of a Cholesky decomposition

Summary. Let the Cholesky decomposition of be , where is upper triangular. The Cholesky block downdating problem is to determine such that , where is a block of rows from the data matrix . We analyze the sensitivity of this block downdating problem of the Cholesky factorization. A measure of conditioning for the Cholesky block downdating is presented and compared to the single row downdating case. Received September 15, 1993     

A generalized inverse eigenvalue problem in structural dynamic model updating

This paper is concerned with the problem of the best approximation for a given matrix pencil under a given spectral constraint and a submatrix pencil constraint. Such a problem arises in structural dynamic model updating. By using the Moore–Penrose generalized inverse and the singular value decomposition (SVD) matrices, the solvability condition and the expression for the solution of the problem are presented. A numerical algorithm for solving the problem is developed.     

A modification to the linpack downdating algorithm

Alinpack downdating algorithm is being modified by interleaving its two different phases, the forward solving a triangular system and the backward sweep of Givens rotations, to yield a new forward method for finding the Cholesky decomposition ofR ^T R –zz ^T . By showing that the new algorithm saves forty percent purely redundant operations of the original, better stability properties are expected. In addition, various other downdating algorithms are rederived and analyzed under a uniform framework.     

The truncatedSVD as a method for regularization

The truncated singular value decomposition (SVD) is considered as a method for regularization of ill-posed linear least squares problems. In particular, the truncated SVD solution is compared with the usual regularized solution. Necessary conditions are defined in which the two methods will yield similar results. This investigation suggests the truncated SVD as a favorable alternative to standard-form regularization in cases of ill-conditioned matrices with well-determined numerical rank.This work was carried out while the author visited the Dept. of Computer Science, Stanford University, California, U.S.A., and was supported in part by National Science Foundation Grant Number DCR 8412314, by a Fulbright Supplementary Grant, and by the Danish Space Board.     

UTV Tools: Matlab templates for rank-revealing UTV decompositions

We describe a Matlab 5.2 package for computing and modifying certain rank-revealing decompositions that have found widespread use in signal processing and other applications. The package focuses on algorithms for URV and ULV decompositions, collectively known as UTV decompositions. We include algorithms for the ULLV decomposition, which generalizes the ULV decomposition to a pair of matrices. For completeness a few algorithms for computation of the RRQR decomposition are also included. The software in this package can be used as is, or can be considered as templates for specialized implementations on signal processors and similar dedicated hardware platforms. This revised version was published online in June 2006 with corrections to the Cover Date.     

A block algorithm for computing rank-revealing QR factorizations

We present a block algorithm for computing rank-revealing QR factorizations (RRQR factorizations) of rank-deficient matrices. The algorithm is a block generalization of the RRQR-algorithm of Foster and Chan. While the unblocked algorithm reveals the rank by peeling off small singular values one by one, our algorithm identifies groups of small singular values. In our block algorithm, we use incremental condition estimation to compute approximations to the nullvectors of the matrix. By applying another (in essence also rank-revealing) orthogonal factorization to the nullspace matrix thus created, we can then generate triangular blocks with small norm in the lower right part ofR. This scheme is applied in an iterative fashion until the rank has been revealed in the (updated) QR factorization. We show that the algorithm produces the correct solution, under very weak assumptions for the orthogonal factorization used for the nullspace matrix. We then discuss issues concerning an efficient implementation of the algorithm and present some numerical experiments. Our experiments show that the block algorithm is reliable and successfully captures several small singular values, in particular in the initial block steps. Our experiments confirm the reliability of our algorithm and show that the block algorithm greatly reduces the number of triangular solves and increases the computational granularity of the RRQR computation.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38. The second author was also sponsored by a travel grant from the Knud Højgaards Fond.This work was partially completed while the author was visiting the IBM Scientific Center in Heidelberg, Germany.     

Numerical computation of an analytic singular value decomposition of a matrix valued function

Summary This paper extends the singular value decomposition to a path of matricesE(t). An analytic singular value decomposition of a path of matricesE(t) is an analytic path of factorizationsE(t)=X(t)S(t)Y(t) ^T whereX(t) andY(t) are orthogonal andS(t) is diagonal. To maintain differentiability the diagonal entries ofS(t) are allowed to be either positive or negative and to appear in any order. This paper investigates existence and uniqueness of analytic SVD's and develops an algorithm for computing them. We show that a real analytic pathE(t) always admits a real analytic SVD, a full-rank, smooth pathE(t) with distinct singular values admits a smooth SVD. We derive a differential equation for the left factor, develop Euler-like and extrapolated Euler-like numerical methods for approximating an analytic SVD and prove that the Euler-like method converges.Partial support received from SFB 343, Diskrete Strukturen in der Mathematik, Universität BielefeldPartial support received from FSP Mathematisierung, Universität BielefeldPartial support received from FSP Mathematisierung, Universität BielefeldPartial support received from National Science Foundation grant CCR-8820882. Some support was also received from the University of Kansas through International Travel Fund 560478 and General Research Allocations # 3758-20-0038 and #3692-20-0038.     

Rank-deficient prewhitening with quotientSVD andULV decompositions

This paper deals with certain theoretical and numerical aspects of prewhitening, which is a technique frequently used in signal processing when dealing with signals degraded by colored noise. In particular, we demonstrate how to prewhiten a signal contaminated by an interfering noisy signal whose covariance matrix is rank deficient. The formulation of our technique is based on the quotient (or generalized) singular value decomposition, and we also show that a quotient-version of theULV decomposition can be used to provide an efficient updatable implementation.     

UPDATING AND DOWNDATING FOR PARAMETER ESTIMATION WITH BOUNDED UNCERTAIN DATA

The bounded parameter estimation problem and its solution lead to more meaningful results. Its superior performance is due to the fact that the new method guarantees that the effect of the uncertainties will never be unnecessarily overestimated. We then consider how to update and downdate the bounded parameter estimation problem. When updating and downdating of SVD are used to the new problem, special technologies are taken to avoid forming U and V explicitly, then increase the algorithm performance. Because of the link between the bounded parameter estimation and Tikhonov regularization procedure, we point out that our algorithms can also be used to modify regularization problem.     

Matrix computations and polynomial root-finding with preprocessing

Solution of homogeneous linear systems of equations is a basic operation of matrix computations. The customary algorithms rely on pivoting, orthogonalization and SVD, but we employ randomized preprocessing instead. This enables us to accelerate the solution dramatically, both in terms of the estimated arithmetic cost and the observed CPU time. The approach is effective in the cases of both general and structured input matrices and we extend it and its computational advantages to the solution of nonhomogeneous linear systems of equations, matrix eigen-solving, the solution of polynomial and secular equations, and approximation of a matrix by a nearby matrix that has a smaller rank or a fixed structure (e.g., of the Toeplitz or Hankel type). Our analysis and extensive experiments show the power of the presented algorithms.     

Stability analysis and fast algorithms for triangularization of Toeplitz matrices

Summary. A new algorithm for triangularizing an Toeplitz matrix is presented. The algorithm is based on the previously developed recursive algorithms that exploit the Toeplitz structure and compute each row of the triangular factor via updating and downdating steps. A forward error analysis for this existing recursive algorithm is presented, which allows us to monitor the conditioning of the problem, and use the method of corrected semi-normal equations to obtain higher accuracy for certain ill-conditioned matrices. Numerical experiments show that the new algorithm improves the accuracy significantly while the computational complexity stays in . Received April 30, 1995 / Revised version received February 12, 1996     

Regularization,GSVD and truncatedGSVD

The purpose of this paper is to analyze Tikhonov regularization in general form by means of generalized SVD (GSVD) in the same spirit as SVD is used to analyze standard-form regularization. We also define a truncated GSVD solution which is of interest in its own right and which sheds light on regularization as well. In addition, our analysis gives insight into a particular numerical method for solving the general-form problem via a transformation to standard form.Part of this work was carried out while visiting the Mathematical Sciences Section, Oak Ridge National Laboratory, Tennessee, during the Numerical Linear Algebra Year 1987–88, and was supported by the Danish Natural Science Foundation.     

An efficient Total Least Squares algorithm based on a rank-revealing two-sided orthogonal decomposition

Solving Total Least Squares (TLS) problemsAXB requires the computation of the noise subspace of the data matrix [A;B]. The widely used tool for doing this is the Singular Value Decomposition (SVD). However, the SVD has the drawback that it is computationally expensive. Therefore, we consider here a different so-called rank-revealing two-sided orthogonal decomposition which decomposes the matrix into a product of a unitary matrix, a triangular matrix and another unitary matrix in such a way that the effective rank of the matrix is obvious and at the same time the noise subspace is exhibited explicity. We show how this decompsition leads to an efficient and reliable TLS algorithm that can be parallelized in an efficient way.     

Truncated VSV Solutions to Symmetric Rank-Deficient Problems

Symmetric VSV decompositions are new rank-revealing decompositions that exploit and preserve symmetry. Truncated VSV solutions are stabilized solutions computed by neglecting blocks in the VSV decomposition with small norm. We compare the truncated VSV solutions with truncated SVD solutions and give perturbation bounds for the VSV solutions. Numerical examples illustrate our results.     

Exponential dichotomy on the real line: SVD and QR methods

In this work we show when and how techniques based on the singular value decomposition (SVD) and the QR decomposition of a fundamental matrix solution can be used to infer if a system enjoys—or not—exponential dichotomy on the whole real line.     

Fast low-rank modifications of the thin singular value decomposition

This paper develops an identity for additive modifications of a singular value decomposition (SVD) to reflect updates, downdates, shifts, and edits of the data matrix. This sets the stage for fast and memory-efficient sequential algorithms for tracking singular values and subspaces. In conjunction with a fast solution for the pseudo-inverse of a submatrix of an orthogonal matrix, we develop a scheme for computing a thin SVD of streaming data in a single pass with linear time complexity: A rank-r thin SVD of a p × q matrix can be computed in O(pqr) time for .     

Accurate downdating of a modified Gram-Schmidt QR decomposition

A new algorithm for downdating a QR decomposition is presented. We show that, when the columns in the Q factor from the Modified Gram-Schmidt QR decomposition of a matrixX are exactly orthonormal, the Gram-Schmidt downdating algorithm for the QR decomposition ofX is equivalent to downdating the full Householder QR decomposition of the matrixX augmented by ann ×n zero matrix on top. Using this relation, we derive an algorithm that improves the Gram-Schmidt downdating algorithm when the columns in the Q factor are not orthonormal. Numerical test results show that the new algorithm produces far more accurate results than the Gram-Schmidt downdating algorithm for certain ill-conditioned problems.This work was partially supported in part by the National Science Foundation grants CCR-9209726 and CCR-9509085.     

The singular value decomposition to approximate spectra of dynamical systems. Theoretical aspects

In this paper we consider the singular value decomposition (SVD) of a fundamental matrix solution in order to approximate the Lyapunov and exponential dichotomy spectra of a given system. One of our main results is to prove that SVD techniques are sound approaches for systems with stable and distinct Lyapunov exponents. We also show how the information which emerges with the SVD techniques can be used to obtain information on the growth directions associated to given spectral intervals.