Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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! :)

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.