[Math] 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).