Difference between revisions of "Open Problems:62"
m (Krzysztof Onak moved page Waiting:Andrea Montanari to Open Problems:62) |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=bertinoro14 | |source=bertinoro14 | ||
|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. | + | Given a symmetric matrix $A$, we can think of Principal Component Analysis (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: | We can define a convex relaxation: | ||
| − | \[ \max Tr(WA) \ \text{s.t}\ | + | \[ \max \operatorname{Tr}(WA) \quad \text{s.t.} \quad \operatorname{Tr}(W) = 1,\ \ W \ge 0,\ \ W \succeq 0. \] |
| − | Suppose that $A$ is a random matrix | + | Suppose that $A$ is a random matrix. In particular, set $A_{ij}$ to be i.i.d $N(0,1)$. Then empirical results show that the resulting $W$ is a rank-1 matrix, which means that we recover the optimal $x$ exactly. |
| − | Is this true in general ? Note that we can prove that the solution is rank 1 if $A = v v^T + | + | Is this true in general? Note that we can prove that the solution is rank 1 if $A = v v^T + (\text{small amount of noise})$. |
Latest revision as of 22:56, 13 June 2014
| Suggested by | Andrea Montanari |
|---|---|
| Source | Bertinoro 2014 |
| Short link | https://sublinear.info/62 |
Given a symmetric matrix $A$, we can think of Principal Component Analysis (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 \operatorname{Tr}(WA) \quad \text{s.t.} \quad \operatorname{Tr}(W) = 1,\ \ W \ge 0,\ \ W \succeq 0. \]
Suppose that $A$ is a random matrix. In particular, set $A_{ij}$ to be i.i.d $N(0,1)$. Then empirical results show that the resulting $W$ is a rank-1 matrix, which means that we recover the optimal $x$ exactly.
Is this true in general? Note that we can prove that the solution is rank 1 if $A = v v^T + (\text{small amount of noise})$.
