63
$\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
  • 2
    $\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, 2014 at 23:29
  • 1
    $\begingroup$ @Marc *singular values. ;-) $\endgroup$ Jan 20, 2014 at 0:25
  • $\begingroup$ Oops, of course. Thanks for the correction. $\endgroup$
    – Marc
    Jan 20, 2014 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, 2017 at 23:07

4 Answers 4

40
$\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
  • 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$ Jan 20, 2014 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$ Jan 20, 2014 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$ Jan 25, 2014 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$ Jan 25, 2014 at 22:00
16
$\begingroup$

I'm going to provide a full characterisation of the set of SVDs for a given matrix $A$, using two different (but of course ultimately equivalent) kinds of formalisms. First a standard matrix formalism, and then using dyadic notation.

The TL;DR of the whole thing is that if $A=UDV^\dagger=\tilde U \tilde D\tilde V^\dagger$ for $U,\tilde U,V,\tilde V$ isometries and $D,\tilde D>0$ squared strictly positive diagonal matrices, then we can safely assume $D=\tilde D$ by trivially rearranging the basis for the underlying space, and furthermore that $\tilde V=V W$ with $W$ a unitary block-diagonal matrix that leaves invariant certain subspaces directly determined by $A$ (further details below). This characterises all and only the possible SVDs. So given any SVD, the freedom in the choice of other SVDs corresponds to the freedom in choosing these unitaries $W$ (how much freedom is that, depends in turn on the degeneracy of the singular values of $A$).

Regular notation

Consider the SVD of a given matrix $A$, in the form $A=UDV^\dagger$ with $D>0$ a diagonal squared matrix with strictly positive entries, and $U,V$ isometries (note that this is general: the SVD is often written in a way that makes $U,V$ unitaries and $D\ge0$ not necessarily squared, but you can have instead $D>0$ squared if you allow $U,V$ to be isometries).

The question is, if you have $$A = UDV^\dagger = \tilde U \tilde D \tilde V^\dagger,$$ with $U,\tilde U,V,\tilde V$ isometries, and $D,\tilde D>0$ diagonal squared matrices, what does this imply for $\tilde U,\tilde D,\tilde V$? And more specifically, can we somehow find an explicit relation between them?

  1. The first easy observation is that you must have $D=\tilde D$, allowing for a trivial rearranging of the basis elements. This follows from $AA^\dagger=UD^2 U^\dagger = \tilde U \tilde D^2 \tilde U^\dagger$, which means that $D^2$ and $\tilde D^2$ both contain the eigenvalues of $AA^\dagger$. Because the spectrum is determined algebraically from $AA^\dagger$, the set of eigenvalues must be identical, hence $D=\tilde D$.

    Technically, you can have $D\neq \tilde D$, but that's only because of trivial reordering of the basis elements. Formally, you fix this saying that there must be a permutation matrix $P$ such that $\tilde D=PDP$, and thus $UDV^\dagger = \tilde U P DP \tilde V^\dagger$. You then redefine $\tilde U'\equiv \tilde UP$ and $\tilde V'\equiv \tilde VP$, observe that these $\tilde U',\tilde V'$ are still isometries, and thus recover the original statement $A=UDV^\dagger=\tilde U' D \tilde V'^\dagger$.

  2. The above reduces the question to: if $UDV^\dagger=\tilde U D\tilde V^\dagger$, with $U,\tilde U,V,\tilde V$ isometries, what can we say about $\tilde U,\tilde V$? We now observe that any SVD defines a partition of the support of $A$, call it $\mathcal V$, into sectors $\mathcal V=\bigoplus_i \mathcal V^{(i)}$ such that for any $v_i\in\mathcal V^{(i)}$ you have $\|A v_i\|=d_i$, where $D=\bigoplus_j d_j I_j$ is the block decomposition of $D$ into its eigenspaces, and we assumed for notational conciseness that the eigenvalues of $D$ are arranged in non-increasing (or non-decreasing, it doesn't matter) order.

    This decomposition is directly determined by $A$, rather than by any specific SVD of $A$, but at the same time it constrains the possible structure of the isometries. More specifically, this decomposition connects with the isometries via the observation that each sector $\mathcal V^{(i)}$ must be spanned by the same set of columns of both $V$ and $\tilde V$. And this is all the freedom you can have. In other words, any SVD of $A$ must involve an isometry $V$ whose columns (taken in suitable order) span each $\mathcal V^{(i)}$ sector, and furthermore any such isometry gives an SVD for $A$.

In conclusion, if $A=UDV^\dagger$ with $U,V$ isometries and $D>0$ squared diagonal, then $D$ is uniquely determined up to permutations. Choosing a basis for the underlying space such that the elements of $D$ are in non-increasing order, then $V$ must be such that its columns span each eigenspace of $A^\dagger A$, and any such $V$ works. This freedom can be written concisely saying that if $A=UDV^\dagger=\tilde UD\tilde V^\dagger$, then $$\tilde V = V \bigoplus W_i$$ for some set of unitaries $W_i$, where each $W_i$ is a unitary in the subspace $\mathcal V^{(i)}$. Finally, notice that $U$ is directly determined by $V$, thus the above characterisation of $V$ is sufficient.

Toy example #1

Let's work out a simple toy example to illustrate the above results.

Let $$H \equiv \begin{pmatrix}1&1\\1&-1\end{pmatrix}.$$ This is a somewhat trivial example because $H$ is Hermitian, but still illustrates some aspects. A standard SVD reads $$ H = \underbrace{\frac{1}{\sqrt2}\begin{pmatrix}1&1\\-1&1\end{pmatrix} }_{\equiv U} \underbrace{\begin{pmatrix}\sqrt2 & 0\\0&\sqrt2\end{pmatrix}}_{\equiv D} \underbrace{\begin{pmatrix}0&1\\1&0\end{pmatrix}}_{\equiv V^\dagger}.$$ In this case we have two identical singular values. According to our discussion above, that means that we can apply a(ny) unitary transformation to the columns of $V$ and still obtain another SVD. That is, given any unitary $W$, $\tilde V\equiv V W$ gives another SVD for $H$. In this simple case, you can also observe this directly, as $D=\sqrt2 I$, and therefore $$H = UDV^\dagger= UD W \tilde V^\dagger = (UW) D V^\dagger,$$ hence $\tilde\equiv UW$ gives the alternative SVD $H=\tilde U D\tilde V^\dagger$, and all SVDs have this form.

Toy example #2

Consider a simple non-squared case. Let $$A \equiv \begin{pmatrix}1&1\\1 & \omega \\ 1 & \omega^2\end{pmatrix}, \qquad \omega\equiv e^{2\pi i/3}.$$ This is again almost trivial because $A$ is an isometry, up to a constant. Still, we can write its SVD as $$A = \underbrace{\frac{1}{\sqrt3}\begin{pmatrix}1&1\\1&\omega\\1&\omega^2\end{pmatrix}}_{\equiv U} \underbrace{\begin{pmatrix}\sqrt3 & 0 \\0&\sqrt3\end{pmatrix}}_{\equiv D} \underbrace{\begin{pmatrix}0&1\\1&0\end{pmatrix}}_{\equiv V^\dagger}. $$ Notice that now $U,V$ are isometries, but not unitaries, and that $D>0$ is squared. Are per our results above, any SVD will have the form $A=\tilde U D \tilde V^\dagger$ with $\tilde V=V W$ for some unitary $W$.

for example, taking $W=V$ (we can do this, because here $V$ is also unitary), we get the alternative SVD $A=\tilde U D \tilde V^\dagger$ with $\tilde V=VW=VV=I$ and $\tilde U= U W^\dagger=UV=\frac1{\sqrt3}\begin{pmatrix}1&\omega&\omega^2\\1&1&1\end{pmatrix}^T$, that is, $$A = \underbrace{\frac{1}{\sqrt3}\begin{pmatrix}1&1\\\omega&1\\\omega^2&1\end{pmatrix}}_{\equiv \tilde U} \underbrace{\begin{pmatrix}\sqrt3 & 0 \\0&\sqrt3\end{pmatrix}}_{\equiv D} \underbrace{\begin{pmatrix}1&0\\0&1\end{pmatrix}}_{\equiv \tilde V^\dagger}.$$

Toy example #3

Let's do an example with non-degenerate singular values. Let $$A = \begin{pmatrix}1& 2 \\ 1 & 2\omega \\ 1 & 2\omega^2\end{pmatrix}, \qquad \omega\equiv e^{2\pi i/3}.$$ This time the singular values are $\sqrt3$ and $2\sqrt3$. One SVD is easily derived as $$A = \underbrace{\frac{1}{\sqrt3}\begin{pmatrix}1&1\\1&\omega\\1&\omega^2\end{pmatrix}}_{\equiv U} \underbrace{\begin{pmatrix}\sqrt3 & 0 \\0&2\sqrt3\end{pmatrix}}_{\equiv D} \underbrace{\begin{pmatrix}1&0\\0&1\end{pmatrix}}_{\equiv V^\dagger}.$$ However, in this case there is much less freedom in choosing other SVDs, because these must correspond to $\tilde V=VW$ where $W$ only mixes columns of $V$ corresponding to the same values of $D$. In this case $D$ is non-degenerate, thus $W$ must be diagonal, and therefore the full set of SVDs must correspond to $W=\begin{pmatrix}e^{i\alpha}&0\\0&e^{i\beta}\end{pmatrix}$, that is, $$A = \underbrace{\frac{1}{\sqrt3}\begin{pmatrix}e^{-i\alpha}&e^{-i\beta}\\e^{-i\alpha}&\omega e^{-i\beta}\\e^{-i\alpha}&\omega^2 e^{-i\beta}\end{pmatrix}}_{\equiv \tilde U} \underbrace{\begin{pmatrix}\sqrt3 & 0 \\0&2\sqrt3\end{pmatrix}}_{\equiv D} \underbrace{\begin{pmatrix}e^{i\alpha}&0\\0&e^{i\beta}\end{pmatrix}}_{\equiv \tilde V^\dagger}.$$ All SVDs will look like this, for some $\alpha,\beta\in\mathbb{R}$. Although note that by permuting the elements of $D$, we obtain SVDs which look different, although are ultimately equivalent to the above.

In dyadic notation

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

Summary

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$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

$\newcommand\R{\mathbb{R}}$I see that this question has been asked a few times. I'd like to provide a simple answer to this.

The singular values $s_1, \dots, s_k$ of an $n$-by-$m$ matrix $M$ are the square roots of the positive eigenvalues of $M^*M$. Let $d_1, \dots, d_k$ be the respective dimensions of the eigenspaces, and $d_{k+1}$ be the dimension of the kernel. Observe that $r = d_1+\cdots + d_k$ is the rank of $M$.

If $$ M = U\Sigma V^* $$ is a singular decomposition, then $M^*M = V\Sigma^2V^*$, and therefore the columns of $V$ form a unitary basis of eigenvectors $(v_1, \dots, v_m)$. $V$ is clearly unique up to unitary transformations of each eigenspace.

Now, for each $1 \le j \le k$, let $w_j = Mv_j$ and observe that for any $1 \le i,j \le r$, $$ \langle w_i,w_j\rangle = \langle Mv_i,Mv_j\rangle = \langle v_i,M^*Mv_j\rangle = \lambda_j\langle v_i,v_j\rangle = \lambda_j\delta_{ij}, $$ where the $\lambda_j$ are the singular values listed with the appropriate multiplicities. Therefore, $$ u_j = \frac{w_j}{\lambda_j},\ 1 \le j \le r $$ are a unitary basis of the image of $M$. They can be extended to a unitary basis $(u_1, \dots, u_n)$ of $\R^n$. It is now easy to show that the matrix $U$ whose columns are $u_1, \dots, u_n$ satisfies the equation $$ M = U\Sigma V^*.$$ It is also easy to show that conversely, if $$ M = U\Sigma V^*, $$ then, for each $1 \le j \le r$, then $$ \lambda_j u_j = Mv_j,$$ and $u_{r+1}, \dots, u_n$ are a unitary basis of the orthogonal complement of the image of $M$. It follows that given any $V$ satisfying the conditions above, the first $r$ columns of $U$ are uniquely determined and the last $n-r$ columns can be any unitary basis of $(\operatorname{image} M)^\perp$.

From all this, we see that $U$ and $V$ are unique up to unitary transformations of the eigenspaces of $M^*M$ and unitary transformations of $(\operatorname{image} M)^\perp$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .