Machine Learning Friendly Set Version of Johnson-Lindenstrauss Lemma
This work is incremental, offering a more practical formulation for data clustering and other ML tasks by enabling a priori dimensionality reduction instead of trial-and-error approaches.
The paper tackles the problem of dimensionality reduction for machine learning applications by providing a set version of the Johnson-Lindenstrauss Lemma that allows users to choose target dimensionality with a guaranteed probability of success, specifically applied to k-means clustering to ensure good solutions in the projected space.
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 $δ$. 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-ε$ all of them fall into predefined error range $δ$ for any user-predefined failure probability $ε$. 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.