1
$\begingroup$

In Principal Component Analysis, we start with $m$ observations $x_1,\dots,x_m$, each of which is an $n$-dimensional vector. Assume we have centered the data; that is, we have subtracted the variable means from each observation. To project each observation into a $1$-dimensional subspace while maximizing sample variance, we want to compute a unit length basis vector, call it $v$. So we get the constrained problem

$$ \mathop{\arg\,\max}\limits_{v}\,\frac{1}{m}\sum_{i=1}^{m}\left\lVert\langle x_i,v\rangle v\right\rVert $$

$$ \text{subject to }v^Tv=1 $$

After some computations, this becomes

$$ \mathop{\arg\,\max}\limits_{v}\,\frac{1}{m}\sum_{i=1}^{m}v^TCv $$

$$ \text{subject to }v^Tv=1 $$

where $C$ is the covariance matrix of the data. Then the Lagrangian objective function is

$$ \mathcal{L}(v,\lambda)=v^TCv-\lambda(v^Tv-1) $$

If we start taking partial derivatives of $\mathcal{L}$, setting these to zero, etc, how do we know that we are maximizing $\mathcal{L}$? Do we need to check that the Hessian is negative definite? Even then, I think that only guarantees a local maximum?

Improve this question
$\endgroup$
5
  • $\begingroup$ Because the constraint $v^\prime v=1$ defines a compact domain and the objective function is continuously differentiable, you are guaranteed that at least one critical point is a global maximum. $\endgroup$
    – whuber ♦
    Commented Dec 4, 2018 at 19:01
  • $\begingroup$ @whuber And not a global minimum? $\endgroup$
    – waynemystir
    Commented Dec 4, 2018 at 19:17
  • $\begingroup$ It seems the relevant answers on this site don't attempt to check all the critical points of $\mathcal{L}$ (for example, stats.stackexchange.com/questions/10251/… stats.stackexchange.com/questions/301532/…) $\endgroup$
    – Frank
    Commented Dec 4, 2018 at 19:51
  • $\begingroup$ Thanks Frank, good point and very helpful links. I'll also add this stats.stackexchange.com/questions/217995/… where @amoeba 's first proof uses Lagrange multipliers. Aside from checking critical points, I would think a negative definite Hessian would suffice. $\endgroup$
    – waynemystir
    Commented Dec 4, 2018 at 20:38
  • $\begingroup$ Whether you need to check for a global minimum versus a global maximum depends on the algorithm. Many of them simply iteratively apply the matrix, relying on the fact that the result has probability $1$ of converging exponentially to the maximum rather than the minimum. $\endgroup$
    – whuber ♦
    Commented Dec 5, 2018 at 19:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.