Problem 62: Principal Component Analysis with Nonnegativity Constraints

Suggested by	Andrea Montanari
Source	Bertinoro 2014
Short link	https://sublinear.info/62

Given a symmetric matrix $A$, we can think of PCA as maximizing $x^\top A x$ subject to $\|x\|=1$. If we also add the condition $x \ge 0$, this problem becomes NP-hard. We can define a convex relaxation:

\[ \max Tr(WA) \text{\ s.t\ } Tr(W) = 1, W \ge 0, W \succceq 0 \]