  In this paper we make a novel use of the Johnson-Lindenstrauss Lemma. The
Lemma has an existential form saying that there exists a JL transformation $f$
of the data points into lower dimensional space such that all of them fall into
predefined error range $\delta$.
  We formulate in this paper a theorem stating that we can choose the target
dimensionality in a random projection type JL linear transformation in such a
way that with probability $1-\epsilon$ all of them fall into predefined error
range $\delta$ for any user-predefined failure probability $\epsilon$.
  This result is important for applications such a data clustering where we
want to have a priori dimensionality reducing transformation instead of trying
out a (large) number of them, as with traditional Johnson-Lindenstrauss Lemma.
In particular, we take a closer look at the $k$-means algorithm and prove that
a good solution in the projected space is also a good solution in the original
space. Furthermore, under proper assumptions local optima in the original space
are also ones in the projected space. We define also conditions for which
clusterability property of the original space is transmitted to the projected
space, so that special case algorithms for the original space are also
applicable in the projected space.

Data Structures and Algorithms;Machine Learning