# Random Projections and separability

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?

• Projecting onto a single dimension will not preserve distances well, even for a single point pair. – Aryeh May 8 '18 at 13:48
• 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$ ? – Aryeh May 8 '18 at 13:51
• Off the top of my head, I can only see this happening if the clusters have large separation distance relative to their diameter. – Aryeh May 8 '18 at 13:52
• 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$. – Sasho Nikolov May 8 '18 at 18:21