28
$\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$
  • 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
21
$\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$
  • $\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
2
$\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$.

One advantage of writing the SVD as in (A) is that it removes the arbitrariness in the order in which the $u_k, v_k$ are arranged as columns of $U, V$. While one could apply an arbitrary permutation to the columns of $U, V$ and $D$ without changing anything, we don't have this redundancy in (A).

Global phase redundancies are always present

Consider now the case in which there is a single $k$ corresponding to a given value of $s_k$. In this case, the only freedom in the choice of vectors $u_k,v_k$ is their global phase: one can replace $u_k\mapsto e^{i\phi}u_k$ and $v_k\mapsto e^{i\phi}v_k$ without changing $A$.

Degenerate singular values bring more freedom

On the other hand, when there are repeated singular values, then there is some additional freedom in the choice of $u_k,v_k$, for similar reasons as there is more freedom in the choice of eigenvectors of 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 three main sources of redundancy:

  1. Any $\tilde U$ that equals $U$ up to permutation of the columns qualifies. This redundancy can be avoided writing the SVD in dyadic notation as in (A).
  2. 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$.
  3. 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)$.
$\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.