How unique are $U$ and $V$ in the Singular Value Decomposition?

According to Wikipedia:

A common convention is to list the singular values in descending order. In this case, the diagonal matrix $$\Sigma$$ is uniquely determined by $$M$$ (though the matrices $$U$$ and $$V$$ are not).

My question is, are $$U$$ and $$V$$ uniquely determined up to some equivalence relation (and what equivalence relation)?

• Do you understand why $U$ and $V$ are not uniquely determined? Think about what happens if $\Sigma$ is not regular, which means that some eigenvalues are zero. Or what happens if you have multiple eigenvalues. – Marc Jan 19 '14 at 23:29
• @Marc *singular values. ;-) – Vedran Šego Jan 20 '14 at 0:25
• Oops, of course. Thanks for the correction. – Marc Jan 20 '14 at 0:35
• The two posts address the phase ambiguities explicitly: math.stackexchange.com/questions/2287795/…, math.stackexchange.com/questions/1805191/… – dantopa Jun 10 '17 at 23:07

Let $A = U_1 \Sigma V_1^* = U_2 \Sigma V_2^*$. Let us assume that $\Sigma$ has distinct diagonal elements and that $A$ is tall. Then

$$A^* A = V_1 \Sigma^* \Sigma V_1^* = V_2 \Sigma^* \Sigma V_2^*.$$

From this, we get

$$\Sigma^* \Sigma V_1^* V_2 = V_1^* V_2 \Sigma^* \Sigma.$$

Notice that $\Sigma^* \Sigma$ is diagonal with all different diagonal elements (that's why we needed $A$ to be tall) and $V_1^* V_2$ is unitary. Defining $V := V_1^* V_2$ and $D := \Sigma^* \Sigma$, we have

$$D V = V D.$$

Now, since $V$ and $D$ commute, they have the same eigenvectors. But, $D$ is a diagonal matrix with distinct diagonal elements (i.e., distinct eigenvalues), so it's eigenvectors are the elements of the canon basis. That means that $V$ is diagonal too, which means that

$$V = \operatorname{diag}(e^{{\rm i}\varphi_1}, e^{{\rm i}\varphi_2}, \dots, e^{{\rm i}\varphi_n}),$$

for some $\varphi_i$, $i=1,\dots,n$.

In other words, $V_2 = V_1 V$. Plug that back in the formula for $A$ and you get

$$A = U_1 \Sigma V_1^* = U_2 \Sigma V_2^* = U_2 \Sigma V^* V_1^* = U_2 V^* \Sigma V_1^*.$$

So, $U_2 = U_1 V$ if $\Sigma$ (and, in extension, $A$) is square nonsingular. Other options, somewhat similar to this, are possible if $\Sigma$ has zeroes on the diagonal and/or is rectangular.

If $\Sigma$ has repeating diagonal elements, much more can be done to change $U$ and $V$ (for example, one or both can permute corresponding columns).

If $A$ is not thin, but wide, you can do the same thing by starting with $AA^*$.

So, to answer your question: for a square, nonsingular $A$, there is a nice relation between different pairs of $U$ and $V$ (multiplication by a unitary diagonal matrix, applied in the same way to the both of them). Otherwise, you get quite a bit more freedom, which I believe is hard to formalize.

• I believe that if there are repeated singular values, you just simply use "small" unitary matrices instead of the factors $e^{\mathrm{i}\varphi}$, that is, $V$ is block diagonal instead (of course, assuming that the singular values are properly ordered). – Algebraic Pavel Jan 20 '14 at 10:38
• @AlgebraicPavel Yes, you are right. Such small matrices then correspond to linear combinations that keep the unitarity. These can be random, and completely different between $U$ and $V$. – Vedran Šego Jan 20 '14 at 12:28
• very good answer, thanks! So I meant to think this through on my own, but I haven't gotten around to it, so I will ask: Is it just that any such pairs are related in this way, OR can you multiply any U and V by ANY unitary diagonal matrix and get another valid U1, V1 that would SVD the original matrix A? – capybaralet Jan 25 '14 at 19:56
• If you have an SVD of $A$, you can multiply its $U$ and $V$ by a diagonal unitary matrix (the same one for each!). However, sometimes you can do even more, as discussed in my answer and Pavel's comment. – Vedran Šego Jan 25 '14 at 22:00

SVD in dyadic notation removes "trivial" redundancies

The SVD of an arbitrary matrix $$A$$ can be written in dyadic notation as $$A=\sum_k s_k u_k v_k^*,\tag A$$ where $$s_k\ge0$$ are the singular values, and $$\{u_k\}_k$$ and $$\{v_k\}_k$$ are orthonormal sets of vectors spanning $$\mathrm{im}(A)$$ and $$\ker(A)^\perp$$, respectively. The connection between this and the more standard way of writing the SVD of $$A$$ as $$A=UDV^\dagger$$ is that $$u_k$$ is the $$k$$-th column of $$U$$, and $$v_k$$ is the $$k$$-th column of $$V$$.

Global phase redundancies are always present

If $$A$$ is nondegenerate, the only freedom in the choice of vectors $$u_k,v_k$$ is their global phase: replacing $$u_k\mapsto e^{i\phi}u_k$$ and $$v_k\mapsto e^{i\phi}v_k$$ does not affect $$A$$.

Degeneracy gives more freedom

On the other hand, when there are repeated singular values, there is additional freedom in the choice of $$u_k,v_k$$, similarly to how there is more freedom in the choice of eigenvectors corresponding to degenerate eigenvalues. More precisely, note that (A) implies $$AA^\dagger=\sum_k s_k^2 \underbrace{u_k u_k^*}_{\equiv\mathbb P_{u_k}}, \qquad A^\dagger A=\sum_k s_k^2 \mathbb P_{v_k}.$$ This tells us that, whenever there are degenerate singular values, the corresponding set of principal components is defined up to a unitary rotation in the corresponding degenerate eigenspace. In other words, the set of vectors $$\{u_k\}$$ in (A) can be chosen as any orthonormal basis of the eigenspace $$\ker(AA^\dagger-s_k^2)$$, and similarly $$\{v_k\}_k$$ can be any basis of $$\ker(A^\dagger A-s_k^2)$$.

However, note that a choice of $$\{v_k\}_k$$ determines $$\{u_k\}$$, and vice-versa (otherwise $$A$$ wouldn't be well-defined, or injective outside its kernel).

TL;DR

A choice of $$U$$ uniquely determines $$V$$, so we can restrict ourselves to reason about the freedom in the choice of $$U$$. There are twe main sources of redundancy:

1. The vectors can be always scaled by a phase factor: $$u_k\mapsto e^{i\phi_k}u_k$$ and $$v_k\mapsto e^{i\phi_k}v_k$$. In matrix notation, this corresponds to changing $$U\mapsto U \Lambda$$ and $$V\mapsto V\Lambda$$ for an arbitrary diagonal unitary matrix $$\Lambda$$.
2. When there are "degenerate singular values" $$s_k$$ (that is, singular values corresponding to degenerate eigenvalues of $$A^\dagger A$$), there is additional freedom in the choice of $$U$$, which can be chosen as any matrix whose columns form a basis for the eigenspace $$\ker(AA^\dagger-s_k^2)$$.

Finally, we should note that the former point is included in the latter, which therefore encodes all of the freedom allowed in choosing the vectors $$\{v_k\}$$. This is because multiplying the elements of an orthonormal basis by phases does not affect its being an orthonormal basis.

I will complete the proof of @Vedran for the case when there exist repeating eigenvalues, which would justify what @glS have said. Let $$A = U \Sigma V^T = U^{'} \Sigma {V^{'}}^T$$ be a matrix with real entries - the case with complex entries is similar. Then, $$A^T A = V \Sigma^T \Sigma V^{T} = V^{'} \Sigma^T \Sigma {V^{'}}^T.$$

From this, we get $$\Sigma^T \Sigma V^T V^{'} = V^T V^{'} \Sigma^T \Sigma.$$ Defining the square matrix $$Q$$ as $$Q = V^T V^{'}$$, we have $$Q^T Q = (V^T V^{'})^T V^T V^{'} = I$$, and similarly, $$Q Q^T = I.$$ Hence, $$Q$$ is an orthogonal matrix that satisfies the Sylvester equation $$Q\Sigma^T\Sigma - \Sigma^T \Sigma Q = 0.\tag{1}$$

Aiming to simplify the Sylvester equation (1) a little, counting the multiplicities, we can write $$\Sigma^T \Sigma$$ $$= \sigma_1^2 I_{n_1} \oplus \sigma_2^2 I_{n_2} \oplus \cdots$$ $$\oplus \sigma_{k}^2 I_{n_k}$$ $$= \text{diag}(\sigma_1^2 I_{n_1}, \sigma_2^2 I_{n_2},$$ $$\cdots, \sigma_{k}^2 I_{n_k}),$$ with $$\sigma_i=\sigma_j$$ iff $$i=j$$ and $$n_i$$ the multiplicity of $$\sigma_{i}$$.

Now, writing $$Q$$ in blocks conformally to $$\Sigma^T \Sigma$$, i.e., with $$Q \Sigma^T \Sigma$$ and $$\Sigma^T \Sigma Q$$ making sense, we have a new system of Sylvester equations $$\sigma_i^2 Q_{ij} I_{n_i} - \sigma_j^2 I_{n_j} Q_{ij}=0,$$ for each $$1\leq i,j\leq k$$. This means that, since both matrices $$\sigma_i^2 I_{n_i}$$ and $$\sigma_j^{2}I_{n_j}$$ do not share any of its eigenvalues for $$i\not=j,$$ by the result discussed here, if $$i\not= j$$, we have necessarily that $$Q_{ij} = 0$$. This means that $$V^T V^{'} = \text{diag} (Q_{11}, Q_{22},\cdots, Q_{kk})$$ for orthogonal matrices $$Q_{ii}$$, meaning that $$V' = V \text{diag}(Q_{11}, Q_{22},\cdots, Q_{kk})=V Q.\tag{2}$$

We can repeat the argument above for the matrix $$A A^T$$ and conclude that there exist an orthogonal matrix $$\bar{Q}$$ such that $$\bar{Q} = \text{diag}(\bar{Q}_{11}, \bar{Q}_{22},\cdots, \bar{Q}_{kk})\tag{3}$$ and $$U' = U \bar{Q},$$ with the matrices $$\bar{Q}_{ii}$$ of the same size of $$Q_{ii}$$ whenever $$\sigma_i\not=0$$ - this is possible because the matrices $$A^T A$$ and $$A A^T$$ have the same eigenvalues with the same multiplicity, except possibly the null eigenvalue. Taking into account that $$A = U \Sigma V^T = U^{'} \Sigma {V^{'}}^T$$, we would be able to conclude $$\Sigma = U^T U^{'} \Sigma {V^{'}}^T V = U^T U \bar{Q} \Sigma Q^T V^T V,$$ which simplifies to $$\Sigma = \bar{Q} \Sigma Q^T.$$ Lastly, considering the nonzero blocks of $$\Sigma$$ associated with the matrices $$Q_{ii}$$ and $$\bar{Q}_{ii}$$, we are able to conclude that $$\bar{Q}_{ii} = Q_{ii}$$ in the expression (3), whenever $$\sigma_i\not=0$$.