One approach for clustering a high dimensional dataset is to use linear transformation, and the most common approaches are PCA and random projection (where random projection arises from the Johnson-Lindenstrauss Lemma). I was wondering why we can't use other random transformation s like when our transformation matrix $R$ was drawn from a uniform distribution?
1
-
1$\begingroup$ Johnson–Lindenstrauss random projections (there are by now several different algorithms) approximately preserve distances. Other random transformations might not. $\endgroup$– Yuval FilmusCommented Apr 30, 2014 at 4:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It is possible that choosing $R$ according to a uniform distribution with zero mean constitutes a Johnson–Lindenstrauss random projection (i.e., it approximately preserves distances). See for example a paper by Achlioptas which suggests three distributions that definitely work: a zero-mean Gaussian, a random $\pm 1$, and a specific distribution on $\{0,\pm 1\}$. It is probable that using the methods in the paper, the case of the uniform distribution can also be analyzed.
answered Apr 30, 2014 at 4:26