The objective function of Principal Component Analysis (PCA) is minimizing the reconstruction error in L2 norm (see section 2.12 here. Another view is trying to maximize the variance on projection. We also have an excellent post here: What is the objective function of PCA?).

My question is that is PCA optimization convex? (I found some discussions here, but wish someone could provide a nice proof here on CV).

  • 2
    No. You are maximizing a convex function (under constraints). – user603 Sep 5 '17 at 18:06
  • 4
    I think you need to be specific about what you mean by "PCA optimization." One standard formulation is to maximize $x^\prime\mathbb{A}x$ subject to $x^\prime x=1$. The problem is that convexity doesn't even make sense: the domain $x^\prime x=1$ is a sphere, not a Euclidean space. – whuber Sep 5 '17 at 18:18
  • 1
    @whuber thanks for your comment, I may not able to clarify the question due to limited knowledge. I may wait for some answers can help me to clarify the question at same time. – hxd1011 Sep 5 '17 at 18:38
  • 3
    I would refer you to any definition of "convex" that you are familiar with. Don't they all involve a concept of points in the domain of a function lying "between" other points? That's worth remembering, because it reminds you to consider the geometry of the domain of a function as well as any algebraic or analytic properties of the function values. In that light, it occurs to me that the variance-maximizing formulation can be slightly modified to make the domain convex: simply require $x^\prime x\le1$ rather than $x^\prime x=1$. The solution is the same--and the answer becomes quite clear. – whuber Sep 5 '17 at 18:43
up vote 16 down vote accepted
+100

No, the usual formulations of PCA are not convex problems. But they can be transformed into a convex optimization problem.

The insight and the fun of this is following and visualizing the sequence of transformations rather than just getting the answer: it lies in the journey, not the destination. The chief steps in this journey are

  1. Obtain a simple expression for the objective function.

  2. Enlarge its domain, which is not convex, into one which is.

  3. Modify the objective, which is not convex, into one which is, in a way that obviously does not change the points at which it attains its optimal values.

If you keep close watch, you can see the SVD and Lagrange multipliers lurking--but they're just a sideshow, there for scenic interest, and I won't comment on them further.


The standard variance-maximizing formulation of PCA (or at least its key step) is

$$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x=1\tag{*}$$

where the $n\times n$ matrix $\mathbb A$ is a symmetric, positive-semidefinite matrix constructed from the data (usually its sum of squares and products matrix, its covariance matrix, or its correlation matrix).

(Equivalently, we may try to maximize the unconstrained objective $x^\prime \mathbb{A} x / x^\prime x$. Not only is this a nastier expression--it's no longer a quadratic function--but graphing special cases will quickly show it is not a convex function, either. Usually one observes this function is invariant under rescalings $x\to \lambda x$ and then reduces it to the constrained formulation $(*)$.)

Any optimization problem can be abstractly formulated as

Find at least one $x\in\mathcal{X}$ that makes the function $f:\mathcal{X}\to\mathbb{R}$ as large as possible.

Recall that an optimization problem is convex when it enjoys two separate properties:

  1. The domain $\mathcal{X}\subset\mathbb{R}^n$ is convex. This can be formulated in many ways. One is that whenever $x\in\mathcal{X}$ and $y\in\mathcal{X}$ and $0 \le \lambda \le 1$, $\lambda x + (1-\lambda)y\in\mathcal{X}$ also. Geometrically: whenever two endpoints of a line segment lie in $\mathcal X$, the entire segment lies in $\mathcal X$.

  2. The function $f$ is convex. This also can be formulated in many ways. One is that whenever $x\in\mathcal{X}$ and $y\in\mathcal{X}$ and $0 \le \lambda \le 1$, $$f(\lambda x + (1-\lambda)y) \ge \lambda f(x) + (1-\lambda) f(y).$$ (We needed $\mathcal X$ to be convex in order for this condition to make any sense.) Geometrically: whenever $\bar{xy}$ is any line segment in $\mathcal X$, the graph of $f$ (as restricted to this segment) lies above or on the segment connecting $(x,f(x))$ and $(y,f(y))$ in $\mathbb{R}^{n+1}$.

    The archetype of a convex function is locally everywhere parabolic with non-positive leading coefficient: on any line segment it can be expressed in the form $y\to a y^2 + b y + c$ with $a \le 0.$

A difficulty with $(*)$ is that $\mathcal X$ is the unit sphere $S^{n-1}\subset\mathbb{R}^n$, which is decidedly not convex. However, we can modify this problem by including smaller vectors. That is because when we scale $x$ by a factor $\lambda$, $f$ is multiplied by $\lambda^2$. When $0 \lt x^\prime x \lt 1$, we can scale $x$ up to unit length by multiplying it by $\lambda=1/\sqrt{x^\prime x} \gt 1$, thereby increasing $f$ but staying within the unit ball $D^n = \{x\in\mathbb{R}^n\mid x^\prime x \le 1\}$. Let us therefore reformulate $(*)$ as

$$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x\le1\tag{**}$$

Its domain is $\mathcal{X}=D^n$ which clearly is convex, so we're halfway there. It remains to consider the convexity of the graph of $f$.

A good way to think about the problem $(**)$--even if you don't intend to carry out the corresponding calculations--is in terms of the Spectral Theorem. It says that by means of an orthogonal transformation $\mathbb P$, you can find at least one basis of $\mathbb{R}^n$ in which $\mathbb A$ is diagonal: that is,

$$\mathbb {A = P^\prime \Sigma P}$$

where all the off-diagonal entries of $\Sigma$ are zero. Such a choice of $\mathbb{P}$ can be conceived of as changing nothing at all about $\mathbb A$, but merely changing how you describe it: when you rotate your point of view, the axes of the level hypersurfaces of the function $x\to x^\prime \mathbb{A} x$ (which were always ellipsoids) align with the coordinate axes.

Since $\mathbb A$ is positive-semidefinite, all the diagonal entries of $\Sigma$ must be non-negative. We may further permute the axes (which is just another orthogonal transformation, and therefore can be absorbed into $\mathbb P$) to assure that $$\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0.$$

If we let $x=\mathbb{P}^\prime y$ be the new coordinates $x$ (entailing $y=\mathbb{P}x$), the function $f$ is

$$f(y) = y^\prime \mathbb{A} y = x^\prime \mathbb{P^\prime A P} x = x^\prime \Sigma x = \sigma_1 x_1^2 + \sigma_2 x_2^2 + \cdots + \sigma_n x_n^2.$$

This function is decidedly not convex! Its graph looks like part of a hyperparaboloid: at every point in the interior of $\mathcal X$, the fact that all the $\sigma_i$ are nonnegative makes it curl upward rather than downward.

However, we can turn $(**)$ into a convex problem with one very useful technique. Knowing that the maximum will occur where $x^\prime x = 1$, let's subtract the constant $\sigma_1$ from $f$, at least for points on the boundary of $\mathcal{X}$. That will not change the locations of any points on the boundary at which $f$ is optimized, because it lowers all the values of $f$ on the boundary by the same value $\sigma_1$. This suggests examining the function

$$g(y) = f(y) - \sigma_1 y^\prime y.$$

This indeed subtracts the constant $\sigma_1$ from $f$ at boundary points, and subtracts smaller values at interior points. This will assure that $g$, compared to $f$, has no new global maxima on the interior of $\mathcal X$.

Let's examine what has happened with this sleight-of-hand of replacing $-\sigma_1$ by $-\sigma_1 y^\prime y$. Because $\mathbb P$ is orthogonal, $y^\prime y = x^\prime x$. (That's practically the definition of an orthogonal transformation.) Therefore, in terms of the $x$ coordinates, $g$ can be written

$$g(y) = \sigma_1 x_1 ^2 + \cdots + \sigma_n x_n^2 - \sigma_1(x_1^2 + \cdots + x_n^2) = (\sigma_2-\sigma_1)x_2^2 + \cdots + (\sigma_n - \sigma_1)x_n^2.$$

Because $\sigma_1 \ge \sigma_i$ for all $i$, each of the coefficients is zero or negative. Consequently, (a) $g$ is convex and (b) $g$ is optimized when $x_2=x_3=\cdots=x_n=0$. ($x^\prime x=1$ then implies $x_1=\pm 1$ and the optimum is attained when $y = \mathbb{P} (\pm 1,0,\ldots, 0)^\prime$, which is--up to sign--the first column of $\mathbb P$.)

Let's recapitulate the logic. Because $g$ is optimized on the boundary $\partial D^n=S^{n-1}$ where $y^\prime y = 1$, because $f$ differs from $g$ merely by the constant $\sigma_1$ on that boundary, and because the values of $g$ are even closer to the values of $f$ on the interior of $D^n$, the maxima of $f$ must coincide with the maxima of $g$.

  • 4
    +1 Very nice. I edited to fix one formula to what I think you intended (but please check). Apart from that, I found the sentence "That won't change any boundary values at which f is optimized" to be confusing at first, because the boundary values do change: you are subtracting $\sigma_1$. Maybe it makes sense to reformulate a bit? – amoeba Sep 6 '17 at 7:45
  • @amoeba Right on all counts; thank you. I have amplified the discussion of that point. – whuber Sep 6 '17 at 13:24
  • 1
    (+1) In your answer, you seem to define a convex function to be what most people would consider to be a concave function (perhaps since a convex optimization problem has a convex domain and a concave function over which a maximum is computed (or a convex function over which a minimum is computed)) – user795305 Sep 6 '17 at 13:50
  • 2
    @amoeba It's a subtle argument. Note, however, that the new maxima--those of $g$--are found to occur only on the boundary. That rules out your counterexamples. Another point worth noting is that in the end we don't really care whether new local (or even global) maxima happen to show up in the interior of $\mathcal X$, because we are originally concerned only about local maxima on its boundary. We are therefore free to alter $f$ in any way that will not make any of those local boundary maxima move or disappear. – whuber Sep 7 '17 at 19:34
  • 2
    Yes, I agree. It does not matter how $f$ is modified on the inside, if the resulting $g$ is "convex" and happens to have maxima on the boundary. Your $g$ does happen to have maxima on the boundary, and this makes the whole argument work. Makes sense. – amoeba Sep 7 '17 at 20:00

No.

Rank $k$ PCA of matrix $M$ can be formulated as

$\hat{X} = \underset{rank(X) \leq k}{argmin} \| M - X\|_F^2$

($\|\cdot\|_F$ is Frobenius norm). For derivation see Eckart-Young theorem.

Though the norm is convex, the set over which it is optimized is nonconvex.


A convex relaxation of PCA's problem is called Convex Low Rank Approximation

$\hat{X} = \underset{\|X\|_* \leq c}{argmin} \| M - X\|_F^2$

($\|\cdot\|_*$ is nuclear norm. it's convex relaxation of rank - just like $\|\cdot\|_1$ is convex relaxation of number of nonzero elements for vectors)

You can see Statistical Learning with Sparsity, ch 6 (matrix decompositions) for details.

If you're interested in more general problems and how they relate to convexity, see Generalized Low Rank Models.

Disclaimer: The previous answers do a pretty good job of explaining how PCA in its original formulation is non-convex but can be converted to a convex optimization problem. My answer is only meant for those poor souls (such as me) who are not so familiar with the jargon of Unit Spheres and SVDs - which is, btw, good to know.

My source is this lecture notes by Prof. Tibshirani

For an optimization problem to be solved with convex optimization techniques, there are two prerequisites.

  1. The objective function has to be convex.
  2. The constraint functions should also be convex.

Most formulations of PCA involve a constraint on the rank of a matrix.

In these type of PCA formulations, condition 2 is violated. Because, the constraint that $rank(X) = k, $ is not convex. For example, let $J_{11}$, $J_{22}$ be 2 × 2 zero matrices with a single 1 in the upper left corner and lower right corner respectively. Then, each of these have rank 1, but their average has rank 2.

  • Could you please explain what "$X$" refers to and why there is any constraint on its rank? This doesn't correspond with my understanding of PCA, but perhaps you are thinking of a more specialized version in which only $k$ principal components are sought. – whuber May 28 at 13:03
  • Yeah, $X$ is the transformed (rotated) data matrix. In this formulation, we seek matrices that are at least of rank $k$. You can refer to the link in my answer for a more accurate description. – kasa May 28 at 14:58

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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