We 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).
We 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).
We 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).
