# Update to SVD by changing 2 row vectors

Suppose I have a matrix in the form

$\begin{bmatrix} a_1 \\ B \\ c_1 \end{bmatrix}$

(The blocks of this matrix should be vertically stacked...don't know why the latex is wrong)

and its SVD is X. Is there an efficient way of computing the SVD of

$\begin{bmatrix} a_2 \\ B \\ c_2 \end{bmatrix}$

Where I replace the first row vector and the last row vector with new values, but keep B?

-
An oddity of the software on this site is that sometimes TeX formatting doesn't work unless you enclose TeX in backwards apostrophes or whatever they're called. I also changed "array" to "bmatrix" and took away the delimiters because "bmatrix" provides those. – Michael Hardy Aug 8 '11 at 3:15

From Golub and Van Loan, Matrix Computations 3rd Edition, Section 12.5 ("updating the ULV decomposition":

...$O(n^3)$ flops are required to recompute the SVD of a matrix that has undergone a unit rank perturbation.

If you just need the nullspace, you can get away with the ULV decomposition (L=lower triangular, U and V as in SVD), otherwise I am afraid you are out of luck.

But, as usual, the next question is: what do you need the SVD for? Do you need only the larger/smaller singular triples, or the whole decomposition?

-
I am trying to compute a series of regressions. regress Y on X1 regress Y on X2 regress Y on X3 ... I know that real regression algorithms use matrix factorizations to solve $(X^TX)^{-1}X^TY$. And in my case, X2 only differs by X1 in 2 row vectors, and X3 differs by X2 in 2 row vectors, etc. – JCW Aug 7 '11 at 3:20
Then you only need to update a pseudoinverse --- the SVD is overkill. You may compute the pseudoinverse using the QR factorization and update that. Check Golub and Van Loan, Section 12.5.1 for the updates, and en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse for computing the pseudoinverse with a QR factorization. – Federico Poloni Aug 7 '11 at 9:56