Random projection below the JL limit
James C. Bezdek, Xiuyi Ye, Mihail Popescu, James M. Keller, Alina Zare · 2016
The Johnson-Lindenstrauss (JL) lemma, with known probability, sets a lower bound q0on the dimension for which a random projection of p-dimensional vector data is guaranteed to be within (1±ε) of being an isometry in a randomly projected downspace. We study several ways to identify a “good” rogue random projection when the target downspace has dimensions below the JL limit. The tools used towards this end are Pearson and Spearman correlation coefficients, and a visual imaging method (a cluster heat map) that usually reveals cluster structure in spaces of any dimension. We use four synthetic data sets and the ubiquitous Iris data to study our procedures for tracking the reliability of RRPs. Unsurprisingly, rogue random projection is quite unpredictable. At its best, it is every bit as good as Principal Components Analysis, but at it's worst, it is awful. Pearson and Spearman correlations do signal good and bad projections, but the visual imaging method seems even more effective in determining the quality of RRPs.