2
$\begingroup$

I am reading about PCA and I came up with a some contradictions. PCA based on this post, PCA optimization problem is given by:

$$\begin{aligned} \max_{w} \quad & w^T\Sigma w\\ \textrm{s.t.} \quad & w^Tw=1\\ \end{aligned}\quad(\text{P1})$$ where $\Sigma$ is the covariance matrix of data. My questions are:

  1. In this post, it was stated by @whuber that $w^T\Sigma w$ is not Convex. How is that possible as $\nabla w^T\Sigma w=\Sigma \succeq 0$ (link)?
  2. Also, in the same post it is stated that the unit sphere $S^{n-1}\subset\mathbb{R}^n$ is decidedly not convex. How it is that possible as it is proven that $w^Tw=1$ is convex?
  3. Also, if $w^T\Sigma w$ is convex what is the intuition of maximizing it?

Could you please some one shade some light?

EDIT: I removed the second question. I just realized that we are dealing with a non-convex domain which cause as a non-convex problem, that is why we maximize (P1). Please, correct me If I am wrong.

$\endgroup$
3
$\begingroup$
  1. $w^T\Sigma w$ is convex function, you're right. As far as I see, whuber's answer defines concave functions as what we usually know as convex functions. It's also pointed out in the comments.

  2. Take two points on the unit sphere, and connect them with a line. Is the line (all of it) inside the domain? No, then the domain is not convex.

  3. Because, you maximize the convex function considering some constraints. Otherwise it wouldn't make much sense.

And it's worth noting that even if the objective is convex, the problem is not a convex optimization problem because the equality constraint should have been affine.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The function is convex. But maximization of a convex function is not a convex optimization problem (minimization of a convex function is what we call a convex optimization problem) $\endgroup$ – user603 Jan 18 at 23:29
  • $\begingroup$ @user603 yes, that is another reason (to be listed) why this problem is not a convex opt. problem. $\endgroup$ – gunes Jan 18 at 23:30

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.