19
$\begingroup$

In lecture 29 of MIT 18.06, Professor Gilbert Strang "proves" the singular value decomposition (SVD) by assuming that we can write $A = U\Sigma V^T$ and then deriving what $U$, $\Sigma$, and $V$ must be based on the eigendecomposition of $$ AA^T = U\Sigma ^2 U^T$$ and $$ A^TA = V\Sigma ^2 V^T$$

My intuition tells me there's something wrong with first assuming that we can write $A$ in this form. As in, we are finding $U$, $\Sigma$ and $V$ for those matrices that have this form, but what if some matrices couldn't be written in this form in the first place?

Also, is there some intuition to be found about $U$ and $V$ by only thinking about them as eigenvectors of $AA^T$ and $A^TA$? In the sense that we should be able to know why $V$ will have its properties (be mapped orthogonally by $A$) by just looking at it as an eigenvector of $A^TA$ (which somehow implicitly "encodes" the basis $U$). Not sure if this intuition makes sense either.

$\endgroup$
3
  • $\begingroup$ Didn't he spend the first 10 or so minutes to explain geometrically why we can write $A$ in this way? $\endgroup$ – Dirk May 11 '17 at 13:39
  • 1
    $\begingroup$ It is a known fact that any symmetric matrix can be diagonalized by an orthogonal matrix, hence the two identities are always possible. $\endgroup$ – user65203 May 11 '17 at 13:42
  • $\begingroup$ In the case of an invertible $A$, he only thing that you would need to prove is that if $U$ and $\Sigma$ are chosen in the manner described, then $V = U^T \Sigma^{-1}A$ is orthogonal. $\endgroup$ – Ben Grossmann May 11 '17 at 13:44
21
$\begingroup$

Apologies that this turned out a little long.

I haven't seen the lectures but I've just taught through the book. So I understand what you're feeling. Strang is going for a more intuitive than axiomatic style in his exposition. So you're right; he assumes that the SVD exists and then derives what the data have to be.

But if you read the section backwards you can get a more deductive version. First, $A^TA$ is symmetric and positive semi-definite (previous two sections of the book). Therefore $A^TA$ is diagonalizable by an orthonormal matrix, and its nonzero eigenvalues are all positive. This is the key fact that allows the SVD to happen. Order them as $\sigma_1^2 \geq \sigma_2^2 \geq \dotsm \geq \sigma_r^2 > 0$. Notice $r = \operatorname{rank}(A^TA)$, which is equal to $\operatorname{rank}(A)$ (this is proven in Chapter 3 somewhere). Let $v_1, \dots, v_r$ be an orthonormal set of eigenvectors for these positive eigenvalues, and $v_{r+1}, \dots, v_{n}$ an orthonormal basis for the zero-eigenspace, i.e., the nullspace of $A^TA$.

Then he shows that if $v$ is a unit eigenvector of $A^TA$ with eigenvalue $\sigma^2$, then $u = \frac{1}{\sigma}Av$ is a unit eigenvector of $AA^T$ with eigenvalue $\sigma^2$. This is the key relation in the SVD. So if $V$ is the $n \times n$ matrix whose $i$th column is $v_i$, $V_r$ the first $r$ columns of $V$, $\Sigma_r$ the $r \times r$ diagonal matrix whose $i$th entry is $\sigma_i$, and $U_r$ the $m\times r$ matrix whose $i$th column is $u_i = \frac{1}{\sigma_i} A V_i$, we have $$ U_r = AV_r \Sigma_r^{-1} \implies U_r \Sigma_r = AV_r $$ Multiplying both sides by the transpose of $V_r$ and noting its columns are orthonormal, we have $$ U_r \Sigma_r V_r^T = A V_r V_r^T = A I_r = A $$

But wait, there's more! as Strang might say. The vectors $v_{r+1},\dots,v_n$ span the nullspace of $A^TA$. But the nullspace of $A^TA$ is the same as the nullspace of $A$. The vectors $u_1, \dots, u_r$ are $r$ (remember, this is the rank of $A$) orthonormal vectors in the column space of $A$, so they span the column space (a subspace of $\mathbb{R}^m$). We can complete the set $u_1, \dots, u_r$ with orthonormal vectors $u_{r+1},\dots,u_{m}$ to create a full orthonormal basis of $\mathbb{R}^m$.

We now have $r$ triples $(v_i,u_i,\sigma_i)$, where $Av_i = \sigma_i u_i$, and $n-r$ vectors $v_{r+1},\dots v_{n}$, where $A v_i = 0$. So if we let $\Sigma$ be the diagonal matrix $\Sigma_r$ augmented by $n-r$ columns of zeros and $m-r$ rows of zeros, and $U$ be the full $m\times m$ matrix whose $i$th column is $u_i$, it's still true that $AV = U\Sigma$. So again, $$ A = U \Sigma V^T $$ but now $U$ is an orthogonal $m\times m$ matrix, $V$ is an orthogonal $n\times n$ matrix, and $\Sigma$ is the sparse $m\times n$ matrix whose $(i,i)$-th entry is $\sigma_i$, with all other entries zero.

The final beautiful fact comes from taking orthogonal complements. We have an orthonormal basis $u_1, \dots, u_m$ of $\mathbb{R}^m$, the first $r$ of which span the column space of $A$. Therefore the remaining $m-r$ vectors $u_{r+1},\dots,u_m$ span the $C(A)^\perp = N(A^T)$. Likewise, $v_1,\dots,v_n$ is an orthonormal basis of $\mathbb{R}^n$, the last $n-r$ of which span the nullspace of $A$. Therefore the first $r$ of them span $N(A)^\perp = C(A^T)$. Thus the SVD produces not just the singular values and this nice factorization, but simultaneously a set of orthonormal bases for the four subspaces.

$\endgroup$
5
  • 5
    $\begingroup$ Yes yes yes thank you! The point in the reverse process is then that you can't define both $U$ and $V$ only based on the eigendecomposition of $AA^T$ and $A^TA$, because then you lose the relationship between them. You rather start by defining only $V$ and $\Sigma$ (by $A^TA = V\Sigma ^2V^T$), and then define $U$ using the relationship $A=U\Sigma V$. You can then prove that $U$ will be an eigenvector for $AA^T$, hence orthogonal. I knew that $AA^T$ and $A^TA$ had to have the same eigenvalues, but didn't realize that the same proof also finds the eigenvectors (in our case, the $u_i$'s)! $\endgroup$ – samlaf May 11 '17 at 16:13
  • $\begingroup$ @samlaf you got it! $\endgroup$ – Matthew Leingang May 11 '17 at 16:30
  • 2
    $\begingroup$ Very nice! Despite having taught linear algebra a couple of dozen times in my life, I'd never worked through these particular details. (The SVD wasn't so much in fashion in the early 1980s ...) $\endgroup$ – John Hughes May 12 '17 at 1:07
  • $\begingroup$ @MatthewLeingang Why does $$ V_r V_r^T = I_r? $$ also why $$ A I_r = A $$? The fact the V columns are orthonormal would imply $$ V_r^T V_r = I $$ but not the other way around wouldn't it? $\endgroup$ – Elad Maimoni Sep 5 '20 at 9:10
  • $\begingroup$ @NinaKaprez take the transpose of both sides. $\endgroup$ – rubikscube09 Nov 5 '20 at 18:23
9
$\begingroup$

You're right that there's something wrong with assuming that we can do that. But there's nothing wrong with saying "If we could do that, what would it tell us?"

For instance, you might think, "I bet every square matrix is the sum of a symmetric and skew-symmetric matrix. Let's see what that tells us. If I write $$ M = S + A $$ where $S$ is symmetric, etc., then taking transposes I find that $$ M^T = S^T + A^T = S - A $$ and that tells me that $$ M + M^T = 2S $$ so $$ S = \frac{1}{2}(M + M^T) $$ and (similarly) $$ A = \frac{1}{2} ( M - M^T)." $$

OK, so having discovered that, you can ask yourself, "Suppose I define $S$ and $A$ by those last two formulas...will $S$ always be symmetric? Will $A$ always be skew-symmetric? Will their sum always be $M$?"

The answer to all three is "yes".

Now in writing up your proof that every matrix decomposes like this, you have two choices.

  1. You can admit to the reader that you arrived at this idea by doing the "what if" exercise, or

  2. You can pretend that the formulas were handed to you from heaven, or pure brilliance, or whatever.

I believe that Strang is taking the former approach: showing how, if you suspected that there might always be a singular value decomposition, you could arrive at what the matrices HAVE to be; then you work through a proof that those matrices actually DO have the properties that you want.

If you start from a false conjecture, like "5 is the sum of two adjacent even numbers", you can do the same thing. But when you find formulas for the even numbers, you'll discover...that they're not even. So assuming something false in order to conjecture a formula is no sin...but failing to check that the resulting formula is valid? That's bad.

I haven't answered the second part of your question ("Is there some intuition...") because one person's intuition can be another's bafflement. I don't see any immediate intuition in this case, but I don't have a great intuition for the meaning of the transformation represented by $A^t$ (except if we think about dual spaces, and I'm not certain that's useful here).

$\endgroup$
4
  • $\begingroup$ Thanks this has helped me straighten out my thoughts! Now, whereas in your case, we can easily "reverse" the deduction, and find that by defining $S$ and $A$ as so, then naturally $S+A=M$, it doesn't seem like this reverse process is possible for SVD. If we define $U$, $\Sigma$, and $V$ as those matrices found by the eigendecomposition of $AA^T$ and $A^TA$, then there seems to be no (easy?) way to show that $Av_i = \sigma_i u_i$. $\endgroup$ – samlaf May 11 '17 at 14:42
  • $\begingroup$ I grant you that there's still a need to show that, and I don't know how tough that would be to actually do. (I've never actually worked through a complete proof of the SVD, I have to admit). But I thought your question --- about how to discover/prove things --- was an interesting one, and worth addressing. Perhaps someone who's a hot shot in linear algebra can show a quick-and-easy way to prove the $Av_i = \sigma_i u_i$ claim. $\endgroup$ – John Hughes May 11 '17 at 15:27
  • $\begingroup$ Thank you for your time and honesty (instead of claiming geometric triviality like the first commenter), professor Hughes. Matthew Leingang has filled in the details, but your insight was invaluable to my understanding of these very details. $\endgroup$ – samlaf May 11 '17 at 16:20
  • $\begingroup$ The constructive proof of the SVD is takes a lot more work and adds not much more insight. If you are faced with a roomful of mathematics consumers, Strang's approach is very effective. $\endgroup$ – dantopa May 13 '17 at 1:06
0
$\begingroup$

(More of a comment but too long to format. )

It's wrong to prove something by assuming it's true and showing no contradiction.

But if you can reverse every step, then it can be counted as a proof. I.e. assuming some non-contradictory facts, show that the proposition is true.

In that line of thought:

Let $v_{i}$ be the orthonormal eigenvectors of $A^TA$, which always exists.

Let $\sigma_{i}^2$ be the corresponding eigenvalues, which always exists and is positive.

Above definitions imply: $$A^TAv_{i}=\sigma_{i}^2v_{i}$$

Let $$u_{i} = \frac{Av_{i}}{\sigma_{i}} $$ which always exists, and can be proved orthonormal.

Now, the following is always true:

$$AA^Tu_i=AA^T \frac{Av_i}{\sigma_i} = \frac{A}{\sigma_i}A^TAv_i = \frac{A}{\sigma_i}\sigma_{i}^2v_i = \sigma_{i}^2\frac{Av_{i}}{\sigma_{i}} = \sigma_{i}^2u_i$$

Which means $u_i$ is a eigenvector of $AA^T$ and $\sigma_{i}^2$ is the eigenvalue.

As defined, for any $A$ we have, $$Av_i=\sigma_{i}u_i$$ And it can be proved there're $r$ such triplets ($v_i, \sigma_{i}, u_i$). Then it becomes $$A_{m \times n}V_{n \times r}=U_{m \times r} \Sigma_{r \times r}$$ Which is the reduced SVD form.

It can be further shown that $v_i$ span the row space of $A$. ($v_i$ is in the row space of $A$ since $A^TAv_{i}=\sigma_{i}^2v_{i}$, and there're $r$ number of orthogonal $v_i$ due to $r$ non-zero eigenvalues of $A^TA$ due to $rank(A^TA)=rank(A)=r$) Use the orthogonal complement subspaces to complete the $V, U$ to a square shape then it's the full SVD form.

These steps constructs the SVD for any A and didn't assume SVD exists.

$\endgroup$
0
$\begingroup$

I guess, intuitively, the existence of SVD can be proofed by contradiction. Assume that SVD doesn't exists for some matrix $$X \neq USV^T$$ for $U$ and $V$ being orthogonal and $D$ is diagonal. Using the fact that $XX^T$ forms a symmetric matrix $A$; and the eigendecomposition $A = WDW^T$ exists; then $$A = WDW^T = WD^{1/2}I (WD^{1/2}I)^T $$ and that implies there exists such matrix $X = WD^{1/2}I$. Since the 3-tuple $(W,D^{1/2},I)$ satisfies the conditions of the SVD 3-tuple $(U,S, V)$, this leads to a contradiction on $X \neq USV^T$.

Am I correct...?

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