6
$\begingroup$

Here's an attempt to motivate the SVD. Let $A \in \mathbb R^{m \times n}$. It's natural to ask, in what direction does $A$ have the most "impact". In other words, for which unit vector $v$ is $\| A v \|_2$ the largest? Denote this unit vector as $v_1$. Let $\sigma_1 = \| A v_1 \|_2$, and define $u_1$ by $A v_1 = \sigma_1 u_1$.

Next, we would like to know in what direction orthogonal to $v_1$ does $A$ have the most "impact"? In other words, for which unit vector $v \perp v_1$ is $\| A v \|_2$ the largest? Denote this unit vector as $v_2$. Let $\sigma_2 = \| A v_2 \|_2$, and define $u_2$ by $A v_2 = \sigma_2 u_2$.

Question: Are the vectors $u_1$ and $u_2$ guaranteed to be orthogonal? If so, is there an easy proof for this fact, or a viewpoint that makes this obvious?

$\endgroup$
4
$\begingroup$

if $$\max_{\|v\|=1} \|A v\|$$ has $v_1$ as solution, then for every $v \perp v_1$ : $Av \perp A v_1$.

suppose by contradiction that it exists $v_2 \perp v_1$ such that $Av_2 = c A v_1 + u_2$ where $c\ne 0$ and $u_2 \perp A v_1$. then $v_1$ can't be a maximiser of $\max_{\|v\|=1} \|A v\|$ :

let $w(\epsilon) = \sqrt{1-\epsilon^2} v_1 + \epsilon v_2$, hence $\|w(\epsilon)\| = 1$, and $$A w(\epsilon) = \sqrt{1-\epsilon^2} A v_1 + \epsilon A v_2 = (\sqrt{1-\epsilon^2} + \epsilon c) A v_1 + \epsilon u_2$$

i.e. : $$\|A w(\epsilon)\|^2 = \underbrace{|\sqrt{1-\epsilon^2} + \epsilon c|^2}_{>\ 1 \ \text{if } \ \epsilon \ \text{ is small enough }} \|A v_1\|^2+ \epsilon^2 \|u_2\|^2 $$

this is enough to prove the SVD of matrices, since we can repeatedly compute $\max_{\|v\|=1} \|A_k v\|$ on $A_1 = A$ and then on $A_{k+1} = A_{k} - A_{k}v_{k} v_{k}^T$ where $v_{k}$ is the maximiser of the previous maximisation, and hence this is enough to prove the spectral theorem too.

$\endgroup$
  • $\begingroup$ Great answer! I was going to post something along these lines as well, but you said it much better. $\endgroup$ – Nick Alger Apr 11 '16 at 17:51
  • $\begingroup$ @NickAlger : there was a mistake, no ? I replaced $A_k = A_{k-1} - v_{k-1} (A_{k-1}v_{k-1})^T$ by $A_k = A_{k-1} - A_{k-1}v_{k-1} v_{k-1}^T$ $\endgroup$ – reuns Apr 11 '16 at 18:23
  • $\begingroup$ I didn't read that part in detail. It seems to me the core idea is everything before the last paragraph. Ie, if two vectors are not orthogonal, then you can always form a linear combination of them with weights that have sum-of-squares=1, such that the combination is larger than either one independently. Then you can apply the result recursively as you have done, or after presuming inductively that the first k singular vectors are orthogonal, use the result k times to show that the next vector is orthogonal to all of the previous ones, one at a time. $\endgroup$ – Nick Alger Apr 11 '16 at 18:34
  • 1
    $\begingroup$ Thanks, this is interesting. Can you explain how you and @NickAlger were able to recognize the "core idea" so easily? In other words: is it a standard fact that if two vectors are not orthogonal then you can always find a linear combination of them, with weights that have sum-of-squares=1, such that the combination is larger than either one independently? Is there a way to visualize that fact that makes it expected? Is it a trick that you've seen used before in other proofs or problems? $\endgroup$ – eternalGoldenBraid Apr 12 '16 at 12:03
  • $\begingroup$ @eternalGoldenBraid If you are familiar with the law of cosines in geometry, it can be seen as a special case of that, en.wikipedia.org/wiki/Law_of_cosines $\endgroup$ – Nick Alger Apr 12 '16 at 14:22
3
$\begingroup$

The shortcut that you might be inclined to take would be to try to prove that if $x,y$ are orthogonal then $Ax,Ay$ are orthogonal. But this is not the case, and in fact it is very far from being the case. It is not even the case when $A$ is symmetric positive definite, or even just diagonal with positive entries.

To proceed correctly you have to bring in the adjoint somehow. A way to do this is to note that $\| Ax \|^2_2 = \langle Ax,Ax \rangle = \langle x,A^T A x \rangle$ (the transpose is the adjoint for the Euclidean inner product). So the norm is maximized when you maximize this inner product. Cauchy-Schwarz tells us that it is maximized by the eigenvector of $A^T A$ with largest eigenvalue. This is your $v_1$, and its image is your $u_1$.

Now you take the orthogonal complement of $v_1$ when you go to define $v_2$. I don't see a way to conveniently work with this orthogonal complement without proving that it is invariant under $A^T A$, because otherwise $A^T A$ might not have any eigenvectors in there. (For example, with $B=\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$, this construction works to find the eigenvector $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, but then the orthogonal complement of that is not invariant under $B$, and indeed $B$ doesn't have any other eigenvectors.) But once you've proven that, you've almost proven the spectral theorem, so you've gotten pretty far from the simple picture that you started with.

$\endgroup$
  • $\begingroup$ Just to check, do you agree with the proof (in the other answer) that if $x$ maximizes $\| A z \|$ subject to the constraint that $\| z \| = 1$, and $y$ is orthogonal to $x$, then $Ay$ is orthogonal to $Ax$? $\endgroup$ – eternalGoldenBraid Apr 13 '16 at 12:10
  • 1
    $\begingroup$ @eternalGoldenBraid Yes, that's correct. This is ultimately because the span of $x$ is invariant under $A^T A$, which is why (as I said above) the maximization assumption is essential. The other answer uses a pretty clever geometric trick, rather than using the algebraic way of thinking about it that I had in mind. $\endgroup$ – Ian Apr 13 '16 at 12:22
3
$\begingroup$

Here's my attempt at an intuitive explanation of the fact that $u_1$ and $u_2$ are guaranteed to be orthogonal, based on the answer given by @user1952009. Throughout this answer, $\| \cdot \|$ will denote the $\ell_2$-norm.

Assume that $v_1$ is a maximizer of $\|Av\|$ subject to the constraint that $\|v\| = 1$. Assume also that $v_2 \perp v_1$.

Claim: Under these assumptions, $A v_2 \perp A v_1$.

Explanation: It's possible to look at this in a way that makes it intuitive or even "obvious". If $Av_2$ were not orthogonal to $A v_1$, then it seems like we could improve $v_1$ by adding $\epsilon v_2$ to it, for a sufficiently tiny value of $\epsilon$. When we perturb $v_1$ a tiny bit in the direction of $v_2$, then the norm of $v_1$ does not change (to first order, at least). [A satellite in circular orbit moves locally in a straight line, and its distance from the center of the Earth is constant.] However, we cannot say the same for the norm of $Av_1$, because $A v_1$ is perturbed in the direction of $A v_2$, and $A v_1$ and $A v_2$ are not orthogonal. The growth in $\| A v_1 \|$ is non-negligible.

Again: when $v_1$ is perturbed in the direction $v_2$, the change in norm is negligible (so the norm is still $1$). But, $A v_1$ is perturbed in the direction $A v_2$, and the change in norm is non-negligible (so the norm can increase).

Suppose you're standing 1 kilometer from the origin and you want to take a step in order to increase the magnitude of your displacement vector from the origin. In which direction should you move? Is it better to move in a direction orthogonal to your displacement vector, or parallel to it? If you step in a direction orthogonal to your displacement vector, then the change in the magnitude of your displacement vector is negligible. However, if you step in a direction parallel to your displacement vector, then the change in magnitude of your displacement vector is significant.

Finally, let's convert this intuition into a rigorous proof. To get a rigorous proof, we have to face the fact that $v_1 + \epsilon v_2$ does not actually have norm $1$ when $\epsilon \neq 0$, even if $\epsilon$ is tiny. We can fix this by taking our perturbed version of $v_1$ to be \begin{equation} \tag{$\spadesuit$} \tilde v(\epsilon) = \sqrt{1 - \epsilon^2} \, v_1 + \epsilon v_2. \end{equation} The vector $\tilde v(\epsilon)$ really does have norm $1$.

We are assuming (for a contradiction) that $A v_2$ is not orthogonal to $A v_1$. This implies that $A v_2 = c A v_1 + w$, for some $c \neq 0$ and $w \perp A v_1$. It follows that \begin{align} \| A \tilde v(\epsilon) \|_2^2 &= \| (\sqrt{1 - \epsilon^2} + c \epsilon) A v_1 + \epsilon w \|^2 \\ &= (\underbrace{\sqrt{1 - \epsilon^2} + c \epsilon}_{>1 \text{ if }\epsilon \text{ is small enough}})^2 \| A v_1 \|^2 + \epsilon^2 \| w \|^2. \end{align} This shows that $v_1$ is not a true maximizer of $\| A v \|$ subject to the constraint $\| v\|_1$. We have arrived at a contradiction.

The point of the intuitive discussion was to explain how we might think of perturbing $v_1$ as in equation ($\spadesuit$), and why we would expect this perturbation of $v_1$ to be an improvement on $v_1$.

$\endgroup$
  • 1
    $\begingroup$ Interesting, this actually bears a significant algebraic resemblance to the proof of Cauchy-Schwarz based on finding extrema of $f(t)=\langle x+ty,x+ty \rangle$. You are essentially saying that if $x$ is the maximizer and $y$ is orthogonal to $x$, then $f(t)=\| x \|^2+\Theta(t^2)$, but if $Ax$ were not orthogonal to $Ay$ then $g(t)=\| A(x+ty) \|^2$ would be $\| Ax \|^2 + \Theta(t)$. So $g$ would change so much faster than $f$ at $t=0$ that $g$ could still be made to grow even after you renormalize everything (because renormalization rescales everything by the growth rate of $f$, essentially). $\endgroup$ – Ian Apr 13 '16 at 12:53

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.