4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ The singular vectors satisfy $A v_i = \sigma_i u_i$. What if you find the vectors $v_i$ first and then compute $u_i$ and $\sigma_i$ using this equation? $\endgroup$ – littleO Jul 15 '17 at 22:41
  • 2
    $\begingroup$ @littleO That is awesome! I was unaware of that relationship, but if you already believe the SVD Theorem, then it seems kind of obvious in retrospect. If you want to post this as an answer and include an explanation of why it resolves the ambiguity issue then I'd be happy to accept it. I have already understood the answer from your hint, but I think it would be valuable to have an actual explanation as well. $\endgroup$ – Geoffrey Jul 15 '17 at 23:04
  • $\begingroup$ @littleO That doesn’t work when any of the singular values is zero. $\endgroup$ – amd Jun 27 '19 at 7:33
  • $\begingroup$ @amd Good point. But I think in that case we can just take $\sigma_{r+1} = \cdots = \sigma_n = 0$, and choose $u_{r+1},\ldots, u_n$ so that $\{u_1, \ldots, u_n\}$ is orthonormal. So I don't think it's a serious roadblock if some of the singular values are zero. (Here $r$ is the rank of $A$.) $\endgroup$ – littleO Jun 27 '19 at 7:54
  • $\begingroup$ @littleO Agreed. In fact, one of the answers says just that and suggests G-S to generate the “missing” singular vectors. $\endgroup$ – amd Jun 27 '19 at 8:00
5
$\begingroup$

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" either $V$ or $U$.

$\endgroup$
1
$\begingroup$

The formally correct answer to this question is that the singular vectors (which may or may not be quite the same as the eigenvectors, but you get singular vectors from the SVD, not eigenvectors) are inherently ambiguous. Indeed, it is not difficult to produce examples where two SVD algorithms return different sets of singular vectors. See this post for a discussion on making singular vectors unique, which turns out to be important when you are studying the SVD as a transformation (so you can find things like its Jacobian determinant).

$\endgroup$
0
$\begingroup$

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

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