On the expected distortion bound of direct random projection and its applications

By Johnson and Lindenstrauss lemma, n points in d-dimensional Euclidean space can be projected down to k=O(epsiv^-2logn) dimensions while incurring at most 1+- bi-Lipschitz distortion in pairwise distance. However, most current projection methods requires a k-by-d matrix; and mapping n point takes O(kdn) time. In this paper, a O(dn) complexity random projection method, directly random projection (DRP), is proposed. The performance of DRP is investigated in terms of expected distortion analysis. We prove: 1) an expected distortion bound of DRP; and 2) given moderate conditions, the DRP with appropriate expected distortion can be found in O(1) random time. Furthermore, we propose a simple heuristic to facilitate finding an appropriate DRP. Experimental results on both simulated and real-life data demonstrate DRP can perform quite well and be consistent with our theoretical analysis.