Difference between revisions of "Open Problems:62"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{Header |title=PCAs |source=bertinoro14 |who=Andrea Montanari }} ???")
 
Line 4: Line 4:
 
|who=Andrea Montanari
 
|who=Andrea Montanari
 
}}
 
}}
???
+
 
 +
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 \]

Revision as of 21:27, 28 May 2014

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 \]