Update to SVD by changing 2 row vectors

Question

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
– Michael Hardy, Commented Aug 8, 2011 at 3:15

Federico Poloni · Accepted Answer · 2011-08-06 17:37:06Z

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
– JCW, Commented Aug 7, 2011 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
– Federico Poloni, Commented Aug 7, 2011 at 9:56

Stack Exchange Network

Update to SVD by changing 2 row vectors

1 Answer 1

You must log in to answer this question.

Update to SVD by changing 2 row vectors

1 Answer 1

You must log in to answer this question.

Related