From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: Matrix Analysis (SVD) Question
Date: 13 Jul 2001 10:43:12 GMT
Newsgroups: sci.math.research,sci.math.num-analysis
Summary: Updating the SVD decomposition of a symmetric matrix

In article <3B4DEB3F.82613CDC@utstat.toronto.edu>,
 andrey <andrey@utstat.toronto.edu> writes:
|> Hello!
|> 
|> Can anyone point me in the direction of solutions to the following
|> matrix analysis problem.  For a certain symmetric matrix  A = A',  I
|> have its singular value decomposition  A = PDP'  where  P  is orthogonal
|> and  D  is diagonal.  This matrix is very large, and considerable
|> numerical effort was involved in obtaining the decomposition to adequate
|> accuracy.  Unfortunately an error was made in the  (i,j)-th  element of
|> A  and in the corresponding  (j,i)-th  element.  Thus we can say that
|> the matrix really should have been  A + uv' + vu'  where  u  and  v  are
|> column vectors consisting of zeros everywhere except that  u  is nonzero
|> in its  i-th  position while  v  is nonzero in its  j-th  position.  Is
|> there a formula that will allow us to salvage the calculations that were
|> carried out for the incorrect matrix  A,  and give us the singular value
|> decomposition of the corrected matrix?
|> 

I would name this decomposition the spectral decomposition of A, since A is
symmetric. It is identical to the SVD only if A is positive definite. 
What you have is a rank two modified matrix eigenvalue problem. There are indeed
specialized algorithms for computing the decomposition of the modified matrix,
but there is no closed solution corresponding to hte sherman-morrison-formula.
some literature:

Arbenz, Peter; Gander, Walter; Golub, Gene H.
Restricted rank modification of the symmetric eigenvalue problem: 
Theoretical considerations. (English)
[J] Linear Algebra Appl. 104, 75-95 (1988).
Let A be a symmetric matrix with known spectral decomposition. 
Two modified eigenvalue problems are treated: \par a) Perturbation by 
a matrix of low rank, i.e $\tilde
A=A+VV\sp T$ where V has rank r. It is shown by establishing relations 
between the inertias of $\lambda-A$, $\lambda-\tilde A$ and $I\sb r-V\sp
T(\lambda-A)\sp{-1}V$, that the eigenvalues of $\tilde A$ can be 
located to any desired accuracy by means of the last one. \par b) 
Restricted eigenvalue problem
$PAPx=\lambda x$, $Px=x$, where P is an orthogonal projection on a 
$n-r$-dimensional subspace. Very similar inclusions are possible. \par 
The proof apply ideas
from  the Weinstein-Aronszajn methods for selfadjoit operators to the 
finite-dimensional case. The numerical implementation of a bisection method 
based on the results
given here will be discussed later.



Arbenz, Peter; Golub, Gene H.
On the spectral decomposition of Hermitian matrices modified by 
low rank perturbations with applications. (English)
[J] SIAM J. Matrix Anal. Appl. 9, No.1, 40-58 (1988).
The authors consider the problem of computing the eigenvalues and 
eigenvectors of a matrix $\hat H=H+D$ which is obtained from an 
indefinite Hermitian low rank
modification D of a Hermitian matrix $\hat H$ with known spectral 
decomposition. It is shown that the eigenvalues of H can be easily 
located to any desired accuracy by
means of the inertia of a Hermitian matrix of small order whose 
elements depend nonlinearly on the eigenvalue parameter. The results 
are applied to the singular value
decomposition of arbitrary modified matrices and to the spectral 
decomposition of modified unitary and of Hermitian Toeplitz matrices. 
For both the singular value
decomposition and the unitary eigenvalue problem, divide and conquer 
algorithms based on rank one modifications are also presented.




Zhang, T.; Law, K.H.; Golub, G.H.
On the homotopy method for perturbed symmetric generalized eigenvalue problems. 
(English)
[J] SIAM J. Sci. Comput. 19, No.5, 1625-1645 (1998). [ISSN 1064-8275; 
ISSN 1095-7197] http://epubs.siam.org/sam-bin/dbq/article/29975
Eigenvalues and eigenvectors of a definite symmetric matrix pencil are 
computed by following homotopy paths from a problem with known solution. 
It is studied how
multiple eigenvalues along the path can be handled. A Rayleigh quotient 
iteration is used in each homotopy step, and the choice of step length is 
discussed. Numerical
tests are reported, two coming from simple mechanics applications, 
and one using homotopy through the levels in a multigrid scheme.


hope that helps
peter