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
    $\begingroup$ Johnson–Lindenstrauss random projections (there are by now several different algorithms) approximately preserve distances. Other random transformations might not. $\endgroup$ – Yuval Filmus Apr 30 '14 at 4:04

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.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.