Determining the number of clusters using property testing algorithm

Question

We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of the above problem. The algorithm samples $O(\frac{kd}{\epsilon}\log \frac{kd}{\epsilon})$ many points from the set, and distinguish between following two cases with probability at least $\frac{2}{3}$:

-algorithm ACCEPTS, if all the points are $k$-clusterable.

-algorithm REJECTS, if points are $\epsilon$-far from $k$-clusterable, i.e. any $k$ unit balls covers at most $(1-\epsilon)n$ points.

Now, using the above algorithm as a subroutine can we approximate the value of $k$ (number of clusters), i.e., if we can ignore at most $\epsilon n$ points (because now we don't have the promised version of the input) from the input, then we need to determine the number of clusters in the input.

(I was thinking to do some kind of binary search over $k$, start with k=2, if algorithm ACCEPTS then k=2, if REJECTS then try for k=4 and so on.)

Pls let me know if there is any confusion in the problem.

Answer 1

First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations http://sarielhp.org/p/06/relative/ and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - its well known, but i dont know a ref for that). Secondly, relative approximation sample in this case, guarantees that if the sample fails, then $k$ is too small. So, do exponential search for the right value of $k$, specifically, start with $k_i = 2^i$, and let $R_i$ be the the $i$th sample of size $n_i = O( \frac{kd \log k}{\epsilon} \log \frac{i}{\epsilon} )$ (the $i$ is not a typo).

Let $\alpha$ be the minimum $i$ for which the sample succeeds using the black box. Now, use brute force (on the sample) to find the minimum $k\leq k_\alpha$ for which the sample works. And this is your desired $k$. You need to carefully account for the probability of success, but thats why the $i$ is there - its one of these standard geometric summation stuff.

The $i$ can be avoided -- indeed, the probability that $\alpha$ is bigger by $\Delta$ than its correct value is smaller than $2^{-\Delta}$. If you do that, then the sample you are going to use is of the right size with good probability. That is, if the minimum $k$ for which you can cover more than $(1-\epsilon)n$ of the points is $\kappa$, then the sample the algorithm uses is $O\left( \frac{\kappa d \log \kappa}{\epsilon} \log \frac{1}{\epsilon} \right)$.

There is some added fuzzyness in the answer of this algorithm. The returned answer $\kappa$ is the minimum such that any value of $k < \kappa$, is say $(1-\epsilon/2)$-far from from being k-clustered. I assume this is OK.

In practice you would do something different. Hmm. Something to think about....