0
$\begingroup$

I am trying to prove the sentence "A short calculation shows the above leads to M u = λ u (symmetry of M is needed here). Therefore λ is the largest eigenvalue of M." from this wikipedia site about Singular Value Decomposition. Shortly, show $$\nabla \bar{x}^{T} M \bar{x} = \lambda ( \nabla \bar{x}^{T} \bar{x} )$$

satisfying $M \bar{u} = \lambda \bar{u}$ where $\bar{u}$ is the maximum eigen vector, $\bar{M}$ is a symmetric matrix and $\lambda$ is eigen value, corresponding to the maximum eigen vector.

[Update]

Maximize $\bar{x}^{T} M \bar{x}$ over all $\bar{x}$ such that $||\bar{x}||=1$. Lagrange function is $$f(x) = \bar{x}^{T} M \bar{x} + \mu (||\bar{x}||- 1)$$

Now I need to calculate $$\nabla f(x)$$

calculating, and trying to show that the largest eigen value occur with the constraint...calculating and thinking.

Nabla operations here.

  • 2
    Is is not $(\lambda\cdot \nabla)x^Tx$, but $\lambda(\nabla x^Tx)$ -- just a scalar multiple of the gradient.2011-09-08
  • 0
    Henning Makholm: thank you, yes that changes the equation totally, have to reconsider it now, fixed it.2011-09-08
  • 0
    Also, the correct terminology for $Mu=\lambda u$ is that $u$ is an eigen_vector_, whereas $\lambda$ is its eigen_value_.2011-09-08
  • 0
    Henning Makholm: you mean Wikipedia has a mistake with the dot-product [here](http://en.wikipedia.org/wiki/Singular_value_decomposition#Existence), the point existence there.2011-09-08
  • 0
    Using a centered dot for scalar multiples (or even for multiplication of two numbers) is not wrong, so I wouldn't say that...2011-09-08
  • 0
    $\nabla\|\bar{x}\|^2 = 2\bar{x}$ not $2\|\bar{x}\|$2011-09-08
  • 0
    $\nabla\bar{x}^TM\bar{x}=\lambda\left(\nabla\bar{x}^T\bar{x}\right)$ is true at the extremal points of $\bar{x}^TM\bar{x}$ for $x$ on the unit sphere. It is also true if $\lambda$ is the smallest eigenvalue.2011-09-08
  • 0
    No offense but this is one of those moments in which I have no idea what is being asserted. Do we really need the overbar notation? Besides, $\nabla(x^TMx) = x^T(M+M^T)$ and as it is written there, symmetricity of $M$ leads to $2x^TM$. Similarly, $\nabla(x^Tx) = 2x^T$. Hence, $2x^TM= \lambda 2x^T$. My two cents of advice is that Wikipedia is for quick reminders not to learn stuff from.2011-09-08
  • 0
    @percusse: sorry, notice the word "largest eigen value". The problem is an optimization problem, just wrote down the Lagrange equation.2011-09-08
  • 0
    @hhh : Regarding your second edit, the del operator kills the constant term $\mu$, and the rest is in my previous comment. And $\mu$ becomes $\lambda$ on Wikipedia2011-09-08

1 Answers 1

1

I'm not sure we agree on the interpretation of the Wikipedia paragraph. What it's stated there (as I see it) is that, starting from the equation

$$\nabla \bar{x}^{T} M \bar{x} = \lambda ( \nabla \bar{x}^{T} \bar{x} )$$

we obtaing that (if M is symmetric) $\lambda$ must be an eigenvalue - and hence $x$ and eigenvector. This is true, and it's rather easy from these two (useful) gradients:

$$\nabla (x^T x) = 2 x $$ $$\nabla (x^T M x) = 2 M x $$

These are the vectorial generalization of $\frac{\partial (x^2)}{\partial x} = 2x $ and $\frac{\partial ( m x^2) }{\partial x} = 2 m x $, and can be proved by definition.

Now, the first equation was obtained by applying Lagrange multipliers to the problem of maximizing $x^T M x$ subject to $x^T x = 1$. Specifically: we write

$$\nabla [x^T M x + \mu(x^Tx - 1)]=0 \Rightarrow \nabla( {x}^{T} M {x}) = \lambda \nabla ({x}^{T} {x} ) \hspace{40px} (\lambda = -\mu)$$

We get then that $\lambda$ (the Lagrange multiplier) must be $some$ eigenvalue, and $x$ some eigenvector. But we want to maximize $x^T M x $, so we must choose the eigenvector with largest eigenvalue, because $x^T M x = x^T \lambda x = \lambda$

  • 0
    is there one minus missing in the point of implication? $\nabla x^{T} Mx = -\lambda (\nabla x^{T} x)$.2011-09-08
  • 0
    In which points, you are using the formulas $\nabla(x^{T} x) = 2x$ and $\nabla(x^{T}Mx) = 2Mx$? Is it correct below? $$\nabla(x^{T}Mx) = 2Mx = 2x M = \nabla (x^{T} x) M$$2011-09-08
  • 0
    @hhh fixed, thanks2011-09-08
  • 0
    $\nabla [x^{T}Mx +\lambda(x^{T}x-1)]=\nabla (x^{T}Mx) + \nabla (\lambda(x^{T}x-1)) = 0$ so $\nabla (x^{T}Mx) = -\nabla (\lambda(x^{T}x-1))$?2011-09-08
  • 0
    @hhh : you use the two gradient formulas two replace the corresping terms in my first equation, and you get $ 2 M x= 2 \lambda x$ . Simplifying the 2, you get the eigenvalue equation.2011-09-08
  • 0
    Could you explain $x^{T}Mx = x^{T} \lambda x$? I cannot see at once why $x^{T}Mx$ would be a scalar. Look $\sum$ is a matrix in singular value decomposition [here](http://en.wikipedia.org/wiki/Singular_value_decomposition).2011-09-08
  • 2
    @hhh : Multiply like this $\begin{pmatrix}-&-\end{pmatrix} \begin{pmatrix}\cdot&-&\cdot\\| &\ddots &|\\\cdot&-&\cdot\end{pmatrix}\begin{pmatrix}|\\|\end{pmatrix}$. Can you see it? Btw, I love ASCII art :)2011-09-08
  • 1
    now I see it, of course. And the $Q^{T}\sum Q$ is just a general case, returning matrix with scalars. $Q$ has vectors such as the $x$. Thanks. @percusse2011-09-09