ECCC-Report TR13-031https://eccc.weizmann.ac.il/report/2013/031Comments and Revisions published for TR13-031en-usMon, 29 Apr 2013 16:49:35 +0300
Revision 2
| Clustering in the Boolean Hypercube in a List Decoding Regime |
Irit Dinur,
Elazar Goldenberg
https://eccc.weizmann.ac.il/report/2013/031#revision2We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.
In this work we give lower and upper bounds for the task of finding a $(\delta,\epsilon)$-center. Our main upper bound shows that for values of $\epsilon$ and $\delta$ that are larger than 1/polylog(n), there exists a polynomial time algorithm that finds a $(\delta - o(1),\epsilon - o(1))$-center. Moreover, it outputs a list of centers explaining all of the clusters in the input. Our main lower bound shows that given a set for which there exists a $(\delta,\epsilon)$-center, it is hard to find even a $(\delta/n^c, \epsilon)$-center for some constant c and $\epsilon=1/poly(n), \delta=1/poly(n)$.
Mon, 29 Apr 2013 16:49:35 +0300https://eccc.weizmann.ac.il/report/2013/031#revision2
Revision 1
| Clustering in the Boolean Hypercube in a List Decoding Regime |
Irit Dinur,
Elazar Goldenberg
https://eccc.weizmann.ac.il/report/2013/031#revision1We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.
In this work we give lower and upper bounds for the task of finding a $(\delta,\epsilon)$-center. We first show that for
$\delta=1-\nu$ close to $1$, i.e. in the "unique decoding
regime", given a $(1-\nu,\epsilon)$-centered set our algorithm can
find a $(1-(1+o(1))\nu,(1-o(1))\epsilon)$-center. More
interestingly, we study the "list decoding regime", i.e. when
$\delta$ is close to $0$. Our main upper bound shows that for values of $\epsilon$ and $\delta$ that are larger than 1/polylog(n), there exists a polynomial time algorithm that finds a $(\delta - o(1),\epsilon - o(1))$-center. Moreover, it outputs a list of centers explaining all of the clusters in the input. Our main lower bound shows that given a set for which there exists a $(\delta,\epsilon)$-center, it is hard to find even a $(\delta/n^c, \epsilon)$-center for some constant c and $\epsilon=1/poly(n), \delta=1/poly(n)$. Sat, 02 Mar 2013 13:00:21 +0200https://eccc.weizmann.ac.il/report/2013/031#revision1
Paper TR13-031
| Clustering in the Boolean Hypercube in a List Decoding Regime |
Irit Dinur,
Elazar Goldenberg
https://eccc.weizmann.ac.il/report/2013/031We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.
In this work we give lower and upper bounds for the task of finding a $(\delta,\epsilon)$-center. Our main upper bound shows that for values of $\epsilon$ and $\delta$ that are larger than 1/polylog(n), there exists a polynomial time algorithm that finds a $(\delta - o(1),\epsilon - o(1))$-center. Moreover, it outputs a list of centers explaining all of the clusters in the input. Our main lower bound shows that given a set for which there exists a $(\delta,\epsilon)$-center, it is hard to find even a $(\delta/n^c, \epsilon)$-center for some constant c and $\epsilon=1/poly(n), \delta=1/poly(n)$.
Fri, 22 Feb 2013 16:01:07 +0200https://eccc.weizmann.ac.il/report/2013/031