45
$\begingroup$

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)?

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – Marc Jan 19 '14 at 23:29
  • 1
    $\begingroup$ @Marc *singular values. ;-) $\endgroup$ – Vedran Šego Jan 20 '14 at 0:25
  • $\begingroup$ Oops, of course. Thanks for the correction. $\endgroup$ – Marc Jan 20 '14 at 0:35
  • $\begingroup$ The two posts address the phase ambiguities explicitly: math.stackexchange.com/questions/2287795/…, math.stackexchange.com/questions/1805191/… $\endgroup$ – dantopa Jun 10 '17 at 23:07
30
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$ – Algebraic Pavel Jan 20 '14 at 10:38
  • $\begingroup$ @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$. $\endgroup$ – Vedran Šego Jan 20 '14 at 12:28
  • $\begingroup$ 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? $\endgroup$ – capybaralet Jan 25 '14 at 19:56
  • $\begingroup$ 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. $\endgroup$ – Vedran Šego Jan 25 '14 at 22:00
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.