as far as I can tell, if the columns of a matrix are shuffled, an SVD would still give the same left singular vectors and eigenvalues, and a permutation (based on which column is now in which place) of the right singular vectors. I only made several trials on R, and I'm not sure if this is theoretically valid.
Moreover, and more importantly, I want to find out what happens or if there is any relationship between the SVDs of a certain matrix, and when some of its columns are removed.
Basically, here is what I'm trying to find out.
For the first part of my question, let's say I have a matrix $\mathbf{X}$.
$\mathbf{X} = UDV^\top$. If $\mathbf{X} = [x_1 | x_2 | x_3 | x_4 | \dots | x_{2n-1} | x_{2n}]$, when I move every "even" column to the end, I get $\mathbf{Y} = [x_1 | x_3 | x_5 | \dots | x_{2n-1} \mathbf{|} x_2 | x_4 | x_6 | \dots | x_{2n}]$. SVD of it leads to $\mathbf{Y} = UDQ^\top$. Moreover, it seems that the rows of $Q$ are the (respectively) reshuffled rows of $V$. I assume these are also theoretically correct.
For the second part of my question, let's say, again, I have a matrix $\mathbf{X}$. Let's also say I want to remove every second column, and perform an SVD.
So, if $\mathbf{X} = [x_1 | x_2 | x_3 | x_4 | \dots | x_{2n-1} | x_{2n}]$, and I remove every "even" column, I end up with $\mathbf{Y} = [x_1 | x_3 | x_5 | \dots | x_{2n-1}]$. If, originally, $\mathbf{X} = UDV^\top$, I want to know now what is the SVD of $\mathbf{Y}$, if it's possible to relate it to the original?
To be concise, I am trying to infer something about the components of the SVD of $\mathbf{X}$ without actually calculating its SVD, but rather only concern myself with the SVD of $\mathbf{Y}$, because in my problem, it's extremely easier to get the SVD of $\mathbf{Y}$, but I still kind of need information on the SVD of $\mathbf{X}$. In short, I want to know what can be inferred from the SVD of $\mathbf{Y}$ regarding the SVD of $\mathbf{X}$.
Best Answer
First part: if you "shuffle" the columns of $A=UDV^T$, the resulting matrix can be written $A\Pi=UDV^T\Pi$ for some permutation matrix $\Pi$. Since permutation matrices are orthogonal and the product of orthogonal matrices is orthogonal $A\Pi=UDV^T\Pi$ is the singular value decomposition of $A\Pi$.
Second part: if you remove columns from $A$, the resulting matrix can be written $AS=UDV^TS$ for some column sampling matrix $S$. Since $V^TS$ is no longer orthogonal (you can easily check this yourself), then this is not a singular value decomposition, and you need to recompute it.
If you remove one column at a time, you can look at literature on rank-$1$ updates of the eigendecomposition to see how you can avoid recomputing the decomposition from scratch.