Let $\mathbf{v}_1,\ldots,\mathbf{v}_n$ vectors in an $m$-dimensional space $V$. Taking these as column vectors of the matrix $M$, let
$$
M = U\Sigma V^\ast
$$
its singular value decomposition. Now, I have a problem where $n>m$ and some of the $\mathbf{v}_i$ are equal*. Is there an easy (meaning, computionally efficient – it is a numerical application) way to calculate $U\Sigma V^\ast$ from $U'\Sigma' V'^\ast$, the SVD of $M$ with duplicate columns removed, or will I just need to brute-force it? Specifically, I only need the left SVD, i.e. $U$ and $\Sigma$. It seems to my like this should be possible, but I have no idea how to approach it.
*In fact, I envision cases where most of them are duplicates, which is why I'm concerned about the performance penalty of calculating the full decomposition of $M$.
Best Answer
I don't think there is any simple relationship between the SVD of $M$ and the SVD of $M'$, but if you keep inserting new columns into $M$ and want to compute $U$ and $\Sigma$ after each insertion, and if the number of columns of $M$ far exceeds $m$, then what you need perhaps is rank-1 update of symmetric eigenvalue decomposition of $MM^\ast$.
You see, if $MM^\ast = U\Lambda U^\ast$ is an eigenvalue decomposition of $MM^\ast$, the columns of $U$ and the diagonal of $\sqrt{\Lambda}$ are respectively the left singular vectors and the singular values of $M$. So, if right singular vectors are not needed, then a SVD problem can be converted into a symmetric eigenvalue decomposition problem. Now, if you add a new column $x$ to $M_{\textrm{old}}$ to get a new matrix $M_{\textrm{new}}$, then $M_{\textrm{new}}M_{\textrm{new}}^\ast = M_{\textrm{old}}M_{\textrm{old}}^\ast + xx^\ast$. So, given an eigenvalue decompositon of $M_{\textrm{old}}M_{\textrm{old}}^\ast$, you are going to find a new eigenvalue decompositon when $M_{\textrm{old}}M_{\textrm{old}}^\ast$ is incremented by a rank-1 matrix $xx^\ast$.
There are lots of papers on rank-1 update of symmetric eigenvalue decomposition. You can find a bunch of them on the internet. On my computer, e.g., the first result returned by Google is this.