9

Let's say I can know the SVD of some matrix $X$: $$X = USV^T$$

If I have an orthogonal matrix $A$ (i.e., $A$ is square and has orthonormal columns), then the SVD of $XA$ is

$$XA = USW^T$$ where $W = A^TV$.

But can anything be said about the SVD of $XB$ if $B$ has orthonormal columns but is not necessarily square? In other words, if the SVD of $XB$ is $XB = DEF^T$, can the matrices $D$, $E$, or $F$ be written in terms of the SVD of $X$ and $B$?

Update: @whuber suggests that I can extend $B$ to be orthogonal by adding in orthonormal columns until $B$ is square. Call this orthogonal matrix $\tilde B$.

$$ \tilde B = [B; B_{\perp}]$$

I know the SVD of $X\tilde B$ is $US(\tilde B^TV)^T$ (see above). But now I'm struggling to see if there's a way that I can write the SVD of $XB$ in terms of the SVD of $X\tilde B$.

amoeba
  • 93,463
  • 28
  • 275
  • 317
mobeets
  • 211
  • 1
  • 9
  • For example, it's not the case that the SVD of $XB = US(B^TV)^T$, which is what we have if we know $B$ is square. This is because $B^TV$ is not a square matrix, which would have to be true of the SVD. $B^TV$ does still have orthonormal columns though. – mobeets Oct 21 '16 at 13:19
  • 3
    $B$ can be prolonged by adjoining additional orthonormal columns into an orthogonal matrix (use the Gram-Schmidt process, for instance), thereby reducing your question to the first case. – whuber Oct 21 '16 at 13:22
  • 1
    Cool, thanks @whuber. So say $B'$ is the orthogonalized version of $B$. Will knowing the SVD of $XB'$ tell me something about the SVD of $XB$? – mobeets Oct 21 '16 at 13:54
  • Write it out and you will see how simple and clear the relationship is. – whuber Oct 21 '16 at 14:07
  • @whuber I can't quite see it...Here's what I've tried: Let $B' = [B; B_{\perp}]$. Then $XB' = [XB; XB_{\perp}] = US(B'^TV)^T = US(\left[\begin{matrix}B^T \\ B_{\perp}^T\end{matrix}\right]V)^T = US\left[\begin{matrix}B^TV \\ B_{\perp}^TV\end{matrix}\right]^T$. – mobeets Oct 21 '16 at 15:17
  • @whuber Okay, I feel like I'm close...$B = B'P$, where $P$ is some matrix like $\left[\begin{matrix}1 & 0 \\ 0 & 1 \\ 0 & 0\end{matrix}\right]$ (if $B$ is $3 \times 2$, for example) So finding the SVD of $XB$ given the SVD of $XB'$ is the same as asking what happens to the SVD of a matrix if you drop some subset of its columns. – mobeets Oct 21 '16 at 18:15

2 Answers2

4

In the SVD $X = USV^\prime$, where $X$ is an $n\times p$ matrix, $V$ is an orthogonal $p\times p$ matrix.

Suppose $B$ is an orthogonal $p\times q$ matrix: that is, $B^\prime B = 1_q$. Let

$$S V^\prime B = TDW^\prime\tag{1}$$

be an SVD of $S V^\prime B$. Thus, by definition, $T$ is a $p\times q$ matrix, $D$ is a diagonal matrix of dimension $q$, and $W$ is an orthogonal $q\times q$ matrix.

Compute

$$XB = (USV^\prime) B = U(SV^\prime B) = U(TDW^\prime) = (UT)D(W^\prime).\tag{2}$$

Because $(UT)^\prime (UT) = T^\prime (U^\prime U) T = T^\prime T = 1_q$, $UT$ has orthonormal columns. Because $D$ and $W^\prime$ are part of an SVD, then by definition $D$ is diagonal with non-negative entries and $W$ is a $q\times q$ orthogonal matrix. Consequently, equation $(2)$ gives an SVD of $XB$. Equation $(1)$ shows how this SVD is related to that of $X$ and $B$.

whuber
  • 281,159
  • 54
  • 637
  • 1,101
  • 1
    Thanks for the answer. Though it seems like this is a way of finding the SVD of $XB$ via computing the SVD of $SV'B$, as opposed to using just the SVD of $X$. I was hoping to know if there's a way to find the SVD of $XB$ without having to compute additional SVDs, as is possible when $B$ is square. – mobeets Oct 23 '16 at 17:29
3

For a matrix $B$ with orthonormal columns (but not square), I would like a way of finding an SVD of $XB$ in terms of the SVD of $X = USV^T$.

As suggested by @whuber, a first step towards finding the SVD of $XB$ is to add columns to $B$ to make it square (and thus orthogonal). Call this matrix $\tilde B = [B; B_{\perp}]$, and let $k$ be the number of columns of $B_{\perp}$. Then because $\tilde B$ is orthogonal, if $X = USV^T$ is an SVD of $X$, then $X\tilde B = US(\tilde B^TV)^T$ is an SVD of $X \tilde B$.

Because $XB$ can be gotten from $X\tilde B$ by dropping the last $k$ columns, my original problem now reduces to the following: Given the SVD of a matrix $Y = DEF^T$, is there a way of finding the SVD of $Y' = D'E'F'^T$, where $Y'$ is the matrix resulting from dropping the last $k$ columns of $Y$? (Here I have $Y = X\tilde B$ and $Y' = XB$.)

This problem is referred to as "downdating the SVD", and in general, there seem to be many approaches for doing this. One relevant approach is found here, and more discussion here.

But in general, given that algorithms for downdating the SVD appear to be an area of active research, I'm concluding that there isn't a simple way of finding the SVD of $XB$ given only the SVD of $X$.

Community
  • 1
mobeets
  • 211
  • 1
  • 9
  • 1
    +1. I think you identify the issue correctly: there is no "simple" way. I find it rather intuitive if you consider a simple toy example: e.g. a 2D data cloud elongated in the diagonal direction. The two original singular vectors are diagonal. Multiplying the data matrix with a square orthogonal matrix simply rotates the whole cloud, so the singular vectors stay the same, up to rotation. But projecting the data cloud to e.g. the horizontal line (1D subspaces) will change its shape entirely; now the only singular vector is horizontal. New singular vectors are unrelated to the old ones. – amoeba Oct 24 '16 at 22:18
  • That's a great intuitive explanation of the difference. At first I was finding it pretty upsetting that there could be such a simple relationship for orthogonal matrices but then no longer once you remove just a single column of that matrix. But it all makes sense now. Thanks! – mobeets Oct 25 '16 at 03:23
  • I agree. When I first read your post, I thought: what a naive question! :-) clearly one simply has to rotate the singular vectors (with a matrix "extended" to be a rotation matrix, as whuber wrote) and then drop some of them (corresponding to the "extended" part). But this is of course wrong. – amoeba Oct 25 '16 at 08:53