Open Problems:62 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Andrea Montanari to Open Problems:62

2014-06-13T22:56:04Z

2014-06-13T22:55:48Z

2014-06-04T04:13:54Z

2014-05-29T08:41:49Z

2014-05-29T08:31:29Z

2014-05-28T21:30:51Z

2014-05-28T21:30:08Z

2014-05-28T21:29:17Z

2014-05-28T21:27:29Z

2014-05-28T15:46:52Z

Created page with "{{Header |title=PCAs |source=bertinoro14 |who=Andrea Montanari }} ???"

New page

{{Header
|title=PCAs
|source=bertinoro14
|who=Andrea Montanari
}}
???

@@ Line 8: / Line 8: @@
 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. \]
+\[ \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})$.

@@ Line 1: / Line 1: @@
 {{Header
-|title=PCAs with Nonnegativity Constraints
+|title=Principal Component Analysis with Nonnegativity Constraints
 |source=bertinoro14
 |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:
-\[ \max Tr(WA) \ \text{s.t}\  Tr(W) = 1, W \ge 0, W \succeq 0 \]
+\[ \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.
+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 + $ small amounts of noise.
+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})$.

@@ Line 8: / Line 8: @@
 We can define a convex relaxation:
-\[ \max Tr(WA) \text{\ s.t\ } Tr(W) = 1, W \ge 0, W \succeq 0 \]
+\[ \max Tr(WA) \ \text{s.t}\  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.
+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 + $ small amounts of noise.

← Older revision		Revision as of 21:29, 28 May 2014
Line 8:		Line 8:
	We can define a convex relaxation:		We can define a convex relaxation:

−	\[ \max Tr(WA) \text{\ s.t\ } Tr(W) = 1, W \ge 0, W \~~succceq~~ 0 \]	+	\[ \max Tr(WA) \text{\ s.t\ } 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 + $ small amounts of noise.

← Older revision	Revision as of 22:56, 13 June 2014
(No difference)