Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

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?

share|improve this answer
    
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.