0
$\begingroup$

I've got trouble with matrix optimization problem..

Proving the Principal Component Analysis (PCA) algorithm, we want to maximize the objective function $u^TSu$ subject to $u^Tu=1$, where $u$ is a principal component vector, $S$ is a scatter matrix (or covariance matrix).

In my textbook, they used the technique of Lagrange multipliers and just differentiated the equation with respect to u and set the result to zero.

Is it always guaranteed for that objective function to get maximized at extrema? If I differentiate $u^TSu$ twice, only $S$ remains, which is a semi-positive definite matrix. That result reminds me of a convex function, which is minimized at extrema.

Does anyone have any insight or experience with such a problem?

Thanks,

Lee

$\endgroup$
  • $\begingroup$ Lagrange multipliers method is for finding extrema. Both maxima and minima are included in extremes. So, you need to evaluate $u^T Su$ on extremes, the max value of $u^TSu$ on extremes correponds to the maximum, and the min to the minimum. $\endgroup$ – Sungjin Kim Sep 7 '16 at 6:01
0
$\begingroup$

It is not quite a convex problem because of the constraint. Any critical point of the objective function $f(u)=u^T S u$ under the constraint corresponds to an eigenvector of $S$ (when symmetric) and the value $f(u)$ at that point is the corresponding eigenvalue (which also pops out of the Lagrange multiplier formalism).

Geometric explanation regarding a critical point (better make a drawing): Write $S=\{u: u^T u=1\}$ for the constraint. Let $v\in S$ and consider $u: t\in (-1,1)\rightarrow S$, a $C^1$ curve with $u(0)=v$ and $u'(0)=w$. We have $u(t)^T \dot{u}(t)=v^T w=0$ because of the constraint. The tangent space to $S$ at $v$ is precisely the orthogonal complement to $v$. If $v$ is a critical point for $f_{|S}$ then $t=0$ should be a critical point for $f(u(t))$: $$ v^T S w = f'(u(0)).u'(0)=0$$ which should then hold for any $w$ tangent to $S$ at $v$. So $Sv$ should be orthogonal to the orthogonal complement to $v$, i.e. $Sv$ and $v$ are parallel: $Sv=\lambda v$.

The same type of argument leads to the Lagrange formulation of critical points under regular constraints.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your comment!! Could you give me more explanation why any critical point corresponds to an eigenvector and the eigenvalue?? Almost every proofs for PCA (or LDA) use Langrange multiplier and set the derivative to zero without any mention of critical point. I cannot find the connection between them $\endgroup$ – 이영로 Sep 7 '16 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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