I am new to machine learning and I am considering the following problem:

Suppose you have clusters of points in $\mathbb{R}^N$ with $N$ large. The Johnson-Lindenstrauss lemma specifies how distances between points are preserved when reducing dimensionality. But what if I don't care about distances and I am only interested in keeping the clusters separate when projecting to one single dimension. Which condition should hold on the clusters for a random projections from $\mathbb{R}^N$ to $\mathbb{R}$ to be able to avoid the points in the cluster to overlap? Is there a result defining these conditions?

  • $\begingroup$ Projecting onto a single dimension will not preserve distances well, even for a single point pair. $\endgroup$ – Aryeh May 8 '18 at 13:48
  • 1
    $\begingroup$ Here's a better question though: let $n$ be the number of points and $k$ be the number of clusters. J-L says take dim $=O(\log(n)/\epsilon^2)$ to approximately preserve interpoint distances. What if you only care about keeping the clusters separated -- can $\log n$ be replaced by $\log k $ ? $\endgroup$ – Aryeh May 8 '18 at 13:51
  • $\begingroup$ Off the top of my head, I can only see this happening if the clusters have large separation distance relative to their diameter. $\endgroup$ – Aryeh May 8 '18 at 13:52
  • 1
    $\begingroup$ This paper shows how to achieve dimension reduction for k-means and dimension that only depends on $k$ and the approximation: arxiv.org/abs/1410.6801. One of the results shows what @Aryeh suggests works with approximation factor $9+\epsilon$. $\endgroup$ – Sasho Nikolov May 8 '18 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.