efficient rank-two updates of an eigenvalue decomposition (or more genearlly SVD)

Question

Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al. and Bunch, et al. have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed efficiently.

Has anything similar been done for the case where the update is of the form $A+B$, where $B=uv^t+vu^t$ is a rank-two symmetric matrix (note we can't just do two rank-one symmetric updates)?

What if we relaxed the insistence that $B$ be symmetric and asked instead for an efficient computation of the SVD of the update $A+B$?

References or thoughts would be greatly appreciated.

Answer 1

Here are a few relevant references (a precursor to "1." is also cited by Piyush Grover in the comments to the question):

1. Fast low-rank modifications of the thin singular value decomposition by M. Brand, Linear Algebra and its Applications, 415 (2006)

2. Restricted rank modification of the symmetric eigenvalue problem: Theoretical considerations, P. Arbenz, W. Gander, G. H. Golub, Linear Algebra and its Applications, 104, (1988)---this paper covers low-rank semidefinite updates.

3. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices, F. Benaych-Georges, R. R. Nadakuditi, arXiv, 2010 --- though on random matrices, still might be quite interesting for your case in case you deal with large matrices.

4. Low rank update of singular values, D. Chu and M. Chu, Mathematics of Computation, 75(255), 2006 --- this paper deals with the inverse problem of updating a matrix by a low-rank matrix so as to obtain a desired set of singular values (the authors mention similarity to the so-called "pole reassignment problem")

5. A new approach for solving perturbed symmetric eigenvalue problems, C. Carey, H.-C. Chen, G. H. Golub, and A. Sameh. 1992---this paper also cites older work on updating eigendecompositions.

The first paper cited up there is one of the most cited and perhaps the one of the greatest relevance to your question. However, the other papers provide a wider context.

Answer 2

Just wanted to note that if one knows that the rank two update is of the form $uv^t + vu^t$ and one knows $v$ and $u$ then it is easy to find $x,y$ such that $uv^t + vu^t = xx^t - yy^t$. $x,y = \sqrt{\frac{|v|}{2|u|}} (u \pm \frac{|u|}{|v|}v)$. Once we know $x,y$ then the problem reduces to two symmetric rank one updates and we can use the symmetric rank one update methods cited in the question.

proof : $ xx^t - yy^t = \frac{|v|}{2|u|}( u + \frac{|u|}{|v|}v)(u + \frac{|u|}{|v|}v)^t - \frac{|v|}{2|u|}( u - \frac{|u|}{|v|}v)(u - \frac{|u|}{|v|}v)^t = \frac{|v|}{2|u|}(\frac{|u|}{|v|} (2uv^t + 2vu^t)) = uv^t + vu^t$

I haven't checked if doing so would be more efficient than the more general method of Brand but I suspect that it would be.