2
$\begingroup$

I have a very trivial SVD Example, but I'm not sure what's going wrong.

The typical way to get an SVD for a matrix $A = UDV^T$ is to compute the eigenvectors of $A^TA$ and $AA^T$. The eigenvectors of $A^TA$ make up the columns of $U$ and the eigenvectors of $AA^T$ make up the column of $V$. From what I've read, the singular values in $D$ are square roots of eigenvalues from $AA^T$ or $A^TA$, and must be non-negative.

However, for the simple example $A = \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right]$, $A^TA$ and $AA^T$ are both the identity, and thus have eigenvectors $\bigg\lbrace \left[\begin{matrix} 1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]\bigg\rbrace$. Clearly, the eigenvalues are 1 and 1, so our decomposition ought to be: \begin{align} \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right] = \left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right]\left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right]\left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right] \end{align}

What has gone wrong?

$\endgroup$
5
  • $\begingroup$ @Moo why not $$ \pmatrix{1\\&-1}\pmatrix{1\\&1}\pmatrix{1\\&1}? $$ $\endgroup$ Dec 23 '16 at 0:06
  • $\begingroup$ Why did you choose the eigenvectors of $A^TA$ to be like that instead of [0 1], [1 0]? I could see how it makes sense on this simple example, but how would a computer know to do that, or a human on a more complicated example? $\endgroup$
    – Paradox
    Dec 23 '16 at 0:08
  • $\begingroup$ In $\begin{align} \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right] = \left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right]\left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right]\left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right] \end{align}$, on the LHS, you have $A$, and on the RHS, you have the diagonalization formula of $A^TA$. They cannot be equal ! $\endgroup$
    – Jean Marie
    Dec 23 '16 at 0:55
  • $\begingroup$ @user2520385: What is the context? What book are you reading on? $\endgroup$
    – user9464
    Dec 23 '16 at 1:14
  • $\begingroup$ I was just self-learning from notes such as web.mit.edu/be.400/www/SVD/Singular_Value_Decomposition.htm. But I think I understand what went wrong now. $\endgroup$
    – Paradox
    Dec 23 '16 at 5:17
5
$\begingroup$

You're right that the columns of $U$ and $V$ are the eigenvectors of $AA^T$ and $A^TA$ (repectively). However, that information alone does not completely determine the SVD.

Analogously: in an eigendecomposition $A = PDP^{-1}$, the columns of $P$ are eigenvectors and the entries of $D$ are eigenvalues. Nevertheless, $$ \pmatrix{0&1\\1&0}\pmatrix{1\\&2}\pmatrix{0&1\\1&0}^{-1} \neq \pmatrix{1&0\\0&1}\pmatrix{1\\&2}\pmatrix{1&0\\0&1}^{-1} $$ Once we've found a valid choice of $V$ (with eigenvectors in order corresponding to the eigenvalues of $A^TA$ in descending order), it remains to solve for a satisfactory $U$. If $A$ is invertible, then $$ A = U DV^T \implies U = AVD^{-1} $$ even if $A$ is not invertible, some of the columns of $U$ will be determined by our choice of $V$.

To put it precisely: the $i$th column of $U$ is given by $u_i = \frac 1{\sigma_i}Av_i$ whenever $\sigma_i$ is non-zero. To see that these columns are orthonormal, note that $$ u_i^Tu_j = \frac{1}{\sigma_i\sigma_j} v_i^TA^TAv_j $$

$\endgroup$
3
$\begingroup$

To directly answer your question, the problem is that the "typical way" you describe for getting an SVD is incorrect:

The typical way to get an SVD for a matrix $A = UDV^T$ is to compute the eigenvectors of $A^TA$ $\color{red}{and}$ $AA^T$. The eigenvectors of $A^TA$ make up the columns of $U$ and the eigenvectors of $AA^T$ make up the column of $V$.

One should either give $U$ then solve $V$, or give $V$ then solve $U$ by using the relation $A=UDV^T$.

On the other hand, you wrote that

... and thus have eigenvectors $\bigg\lbrace \left[\begin{matrix} 1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]\bigg\rbrace$

But one could equally have $\bigg\lbrace \left[\begin{matrix} -1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]\bigg\rbrace$, or $\bigg\lbrace \left[\begin{matrix} 1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ -1 \end{matrix}\right]\bigg\rbrace$, or $\bigg\lbrace \left[\begin{matrix} -1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ -1 \end{matrix}\right]\bigg\rbrace$.

Any one of these sets consists of independent eigenvectors (with unit length) of the identity matrix. If one chooses from these sets arbitrarily to form $U$ and $V$, there is no reason to expect that $$ A=UDV^T. $$

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