<p>I am new to machine learning and I am considering the following problem:</p>

<p>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?</p>

CC BY-SA 4.0
2018-05-08T13:48:49.673Z
Projecting onto a single dimension will not preserve distances well, even for a single point pair.
Aryeh
CC BY-SA 4.0
2018-05-08T13:51:06.937Z
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
CC BY-SA 4.0
2018-05-08T13:52:17.090Z
Off the top of my head, I can only see this happening if the clusters have large separation distance relative to their diameter.
Aryeh
CC BY-SA 4.0
2018-05-08T18:21:24.483Z
This paper shows how to achieve dimension reduction for k-means and dimension that only depends on $k$ and the approximation: https://arxiv.org/abs/1410.6801. One of the results shows what @Aryeh suggests works with approximation factor $9+\epsilon$.
Sasho Nikolov
<high-dimensional-geometry>
Random Projections and separability
Cesare
# Random Projections and separability

(Asked by: username_0 on 2018-05-08)

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?

**Tags:** high-dimensional-geometry
> **Comments:**
> **username_1**: Projecting onto a single dimension will not preserve distances well, even for a single point pair.  
> **username_1**: 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 $ ?  
> **username_1**: Off the top of my head, I can only see this happening if the clusters have large separation distance relative to their diameter.  
> **username_2**: This paper shows how to achieve dimension reduction for k-means and dimension that only depends on $k$ and the approximation: https://arxiv.org/abs/1410.6801. One of the results shows what @Aryeh suggests works with approximation factor $9+\epsilon$.  

---

## 0 answers

