1
$\begingroup$

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

2 Answers 2

2

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.

  • 0
    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?2011-10-29
  • 0
    @user7217: Sorry, the "non-zero" was a mistake -- it's simply the least one, which could be zero. Does that make it clearer?2011-10-29
  • 0
    A bit. :) But i don't understand why it will be the right singular vector that corresponds to that least singular value?2011-10-29
  • 0
    @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.2011-10-29
  • 0
    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.2011-10-29
  • 0
    @user7217: You're trying out values of $x$ with a single non-zero component. Note that in my argument it's $V^*x$ that has a single non-zero component, whereas values of $x$ with a single non-zero component don't play any special role. So I'm not sure what you're trying to show with these values. Since $V^*$ is unitary, multiplying $x$ by $V^*$ yields a single non-zero component (in $V^*x$, not in $x$) if and only if $x$ is the corresponding column of $V$, which is the corresponding right singular vector.2011-10-30
  • 0
    @user7217: As regards your English, it's quite a lot better than that of many others on this site; I wouldn't worry about it and keep up the good work. Two slight corrections: "it's" is spelled with an apostrophe when it means "it is", but not when it's the possessive form of "it". And "Thanks in advance" would be more idiomatic than "Thanks ahead".2011-10-30
  • 0
    Thanks! :) The last question: are the singular values in the $\Sigma$ sorted the same way as singular vectors in the left and right matrices?2011-10-30
  • 0
    @user7217: I don't understand that question. The singular values in $\Sigma$ are sorted in descending order. There's no further choice of sorting anything; the singular vectors in $U$ and $V$ simply correspond to those values -- what would it mean to sort them the same way or not?2011-10-30
  • 0
    So the ith column of V is the corresponding singular vector of the ith singular value in $\Sigma$?2011-10-30
  • 0
    @user7217: Sorry, I still don't understand what you're getting at. This is true by definition; it's simply what we mean by "the corresponding singular vector of the $i$-th singular value in $\Sigma$". What else could we mean by that expression? Your questions seem to indicate that you see some possibility of it being otherwise. I think for me to able to help you with that question you're going to have to explain how you're envisaging a situation where the $i$-th column of $V$ *isn't* the singular vector corresponding to the $i$-th singular value in $\Sigma$.2011-10-30
  • 0
    Sorry, so i misunderstood that. :)2011-10-30
1

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.

  • 0
    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.2011-10-29
  • 0
    @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.2011-10-29
  • 0
    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.2011-10-29
  • 0
    @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.2011-10-29