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?
Thanks in advance! :)
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?
Thanks in advance! :)
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.
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.