How to resolve the sign issue in a SVD problem?

Question

Question: When performing a simple Singular Value Decomposition, how can I know that my sign choice for the eigenvectors of the left- and right-singular matrices will result in the correct matrix without just guessing and checking?

If it makes things easier, feel free to restrict your answers to just real-valued or real-valued, square matrices.

Context

Consider the matrix $$A=\begin{pmatrix}2&-4\\4&4\end{pmatrix}$$ which has the left-singular matrix $$AA^T=\begin{pmatrix}20&-8\\-8&32\end{pmatrix}$$ and the right-singular matrix $$A^TA=\begin{pmatrix}20&8\\8&32\end{pmatrix}$$ The eigenvalues for both matrices are $36$ and $16$ (meaning the singular values of $A$ are $6$ and $4$, respectively). The normalized left-singular eigenvectors are $$\textbf{u}_{36}=\frac{1}{\sqrt{5}}\begin{pmatrix}1\\-2\end{pmatrix}\ \ \ \textbf{u}_{16}=\frac{1}{\sqrt{5}}\begin{pmatrix}2\\1\end{pmatrix}$$ and the normalized right-singular eigenvectors are $$\textbf{v}_{36}=\frac{1}{\sqrt{5}}\begin{pmatrix}1\\2\end{pmatrix}\ \ \ \textbf{v}_{16}=\frac{1}{\sqrt{5}}\begin{pmatrix}-2\\1\end{pmatrix}$$

With these in hand, we can construct the SVD which should look like this: $$A=U\Sigma V^T=\frac{1}{5}\begin{pmatrix}1&2\\-2&1\end{pmatrix}\begin{pmatrix}6&0\\0&4\end{pmatrix}\begin{pmatrix}1&2\\-2&1\end{pmatrix}$$

However, if you actually perform the matrix multiplication, the result is $$U\Sigma V^T=\begin{pmatrix}-2&4\\-4&-4\end{pmatrix}= -A \neq A$$

Since the normalized eigenvectors are unique only up to a sign, one resolution to this problem is to choose $$\textbf{u}_{36}=\frac{1}{\sqrt{5}}\begin{pmatrix}-1\\2\end{pmatrix} \ \ \ \ \textbf{v}_{16}=\frac{1}{\sqrt{5}}\begin{pmatrix}2\\-1\end{pmatrix}$$

which produces the correct SVD $$U\Sigma V^T=\frac{1}{5}\begin{pmatrix}-1&2\\2&1\end{pmatrix}\begin{pmatrix}6&0\\0&4\end{pmatrix}\begin{pmatrix}1&2\\2&-1\end{pmatrix}=\begin{pmatrix}2&-4\\4&4\end{pmatrix}=A$$

This begs the question: How was I supposed to know that I had chosen the wrong sign convention for my eigenvectors without checking it by hand?

I have a suspicion that the correct sign convention corresponds to the sum of the components of the eigenvectors being positive (and if they sum to zero then the topmost component should be made positive), but this seems like a pretty arbitrary condition despite it holding for several examples that I have checked.

Answer 1

One does not need to separately compute the eigenvectors of $A A^T$ and also $A^T A$ in order to get an SVD (even in hand calculations). Given an orthonormal eigenbasis for $A^T A$ (resp. $A A^T$), this gives you the right (resp. left) singular vectors. The eigenvalues give you the singular values upon taking square roots. The defining equation for the SVD tells you

$$Av_i=\sigma_i u_i \\ A^T u_i=\sigma_i v_i.$$

This just follows by matrix multiplication:

$$A v_i=U \Sigma V^T v_i = U \Sigma e_i = U \sigma_i e_i = \sigma_i u_i.$$

As an aside, the above pair of equations characterize the SVD through a symmetric eigenproblem not involving $A A^T$ or $A^T A$, which is a crucial step toward developing a numerically stable algorithm for the SVD.

Anyway, if $\sigma_i \neq 0$, to get $u_i$ (resp. $v_i$) it is enough to apply $A$ (resp. $A^T$) to $v_i$ (resp. $u_i$) and divide by $\sigma_i$. If $\sigma_i$ is zero and you want a full SVD then you have some arbitrary choices to make in order to "fill out" $V$ and/or $U$ (specifically you must select any orthonormal basis for the null space of $A$ and/or $A^T$ and add it to the bona fide singular vectors).

Answer 2

To expand on Ian's answer on the final case where singular values are zero; the correct procedure would be to first find all $u_i$ that correspond to non-zero singular values (from the above procedure), and then to construct the remaining vectors to be orthonormal to the already found vectors using the Gram-Schmidt procedure.

This is so because the $u_i$ that correspond to zero singular values are non-trivial solutions to $AA^T u_i = u_i \sigma_i^2 = 0$. Left multiplying by $u_i^T$ gives $\|A^T u_i\|=0$, thus $u_i$ is in the left null space of $A$. We already know that the earlier $u_i$ (the ones corresponding to non-zero singular values) live in the column space of $A$ and we also know that the column and left null space of a matrix are orthogonal sub-spaces. So, Gram-Schmidt allows us to construct the remaining $u_i$.

Answer 3

The SVD transformation has an inherit ambiguity on the signs of the eigenvectors.

It is not possible to solve this problem using just math.

This paper, from the Sandia National Laboratores, proposes a solution to this problem by analysing the directions of the original vectors and selecting the sign of the eigenvector to be the same sign that most of the vectors has.

This is the Python implementation of the SignFlip function (not tested).