# Proof that the unit-vector $x$ that minimizes the $2$-norm of $Ax$ is one of the right singular vectors

I would like to know why the solution of $\min\limits_{\|x\|_{2}=1} \|Ax\|_{2}$ is the right singular vector of $A$ that corresponds to the smallest singular value?

-

With $A=U\Sigma V^*$, we have $Ax=U\Sigma V^*x$. Now since $U$ and $V$ are unitary, $\lVert U\Sigma V^*x\rVert=\lVert \Sigma V^*x\rVert$ and $\lVert x\rVert=\lVert V^*x\rVert$. Thus minimizing $\lVert Ax\rVert$ for $\lVert x\rVert=1$ amounts to minimizing $\lVert \Sigma V^*x\rVert$ for $\lVert V^*x\rVert=1$. This later minimum occurs when $V^*x$ has only a single component that gets multiplied by the least diagonal element of $\Sigma$, which is the least singular value. Since $V^*$ is unitary, the corresponding $x$ is the right singular vector corresponding to that singular value.

-
But, i dont understand why the minimum occurs only when only one component gets multiplied by the least non-zero diagonal element? Could that component be - for example - near zero? Then the minimum would be zero, right? –  user7217 Oct 29 '11 at 20:52
@user7217: Sorry, the "non-zero" was a mistake -- it's simply the least one, which could be zero. Does that make it clearer? –  joriki Oct 29 '11 at 21:00
A bit. :) But i don't understand why it will be the right singular vector that corresponds to that least singular value? –  user7217 Oct 29 '11 at 22:02
@ser7217: $x=V(V^*x)$, so if $V^*x$ has a single component, $x$ is the corresponding column of $V$, which is the corresponding right singular vector. –  joriki Oct 29 '11 at 22:21
But V* has the right singular vectors in its rows. So if x was $[0,1]^{T}$, it would select not it's one right singular vector, but one of it's columns, right? Let $\Sigma_{22}$ be the least one and then $V^{*}x$ would be $[\Sigma_{11}v_{21},\Sigma_{22}v_{22}]^{T}$ after multiplied by $\Sigma$, but it might be lesser if x was $[1,0]^{T}$ right? Sorry for my english, it's not my native, so it's hard to express myself in this language. –  user7217 Oct 29 '11 at 23:34

You can show that for a symmetric matrix $M$

$$\lambda_{min}x^Tx\leq x^TMx \leq \lambda_{max}x^Tx \tag{1}$$ where $\lambda$'s are the eigenvalues of largest and smallest eigenvalue of $M$. The relation to your question is simply $M=A^TA$ because $\|Ax\|_{2} = x^TA^TAx$ and the eigenvalues of $M$ are linked to the singular values of $A$.

Also, $A^TA$ is always positive (semi)definite.

EDIT: Thanks to joriki's comment, I think I need to put in more info.

First of all, all eigenvalues of a symmetric matrix are real. Suppose $A\in\mathbb{R}^{m\times n}$ and full rank. If $n>m$, then the minimum is attained as zero since the matrix would then have a nullspace spanned by nonzero vectors and you can take a nonzero vector $x$ with unity norm. That would correspond to the zero eigenvalues of $M$ and it should have zero eigenvalues since it is always a rank deficient matrix. You can see it from the pictorial multiplication of $A^TA$: $$M = \begin{bmatrix} | &|\\\cdot &\cdot\\|&| \end{bmatrix}\begin{bmatrix} - &\cdot &-\\- &\cdot&- \end{bmatrix} = A^TA$$ Thus, the rank of $M$ cannot be larger than its factors. $(1)$ holds with $\lambda_{min}=0$

If $m\geq n$, then $A$ has a trivial nullspace i.e. $0$ vector, hence $A^TA$ would be positive definite matrix. And $(1)$ holds with $x$ being the right eigenvector of the smallest eigenvalue of $M$.

Hope it is clearer.

-
This connection is good to know, but for the present question, using the fact that symmetric matrices are diagonalizable seems like a bit of a detour. Also, you've glossed over the possibility of zero eigenvalues. –  joriki Oct 29 '11 at 19:26
@joriki : I think you are right what I should have said is the nonzero eigenvalues of $M$ are related to nonzero singular values of $A$. But I don't think that I used the diagonalization argument. I only used the realness property of the eigenvalues hence the ordering. Maybe I should rephrase better. –  user13838 Oct 29 '11 at 19:31
OK, you're not literally using diagonalizability, but you're using facts about symmetric matrices that aren't really relevant here, and I don't see any gain from it, since the displayed inequality requires a similar argument to the one that you could make for the singular value decomposition directly instead. –  joriki Oct 29 '11 at 19:56
@joriki Probably I am used to symmetric matrices and find them more comfortable. I just wanted to show that it is a quadratic form that is being minimized. But admittedly, I might be biased. –  user13838 Oct 29 '11 at 20:34