Difference between revisions of "Open Problems:62"
(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 \]
