2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Michael Hardy
    Commented Aug 8, 2011 at 3:15

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – JCW
    Commented Aug 7, 2011 at 3:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Commented Aug 7, 2011 at 9:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .