ON THE EXPECTED DISTORTION BOUND OF DIRECT RANDOM PROJECTION AND ITS APPLICATIONS

摘要：

By Johnson and Lindcnstrauss lemma, n points in d-dimensional Euclidean space can be projected down to k=O(ε-2 logn) 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 (DKP), is proposed. The performance of DRP is investigated in terms of expected distortion analysis. We prove: 1) an expected distortion bound of DKP; 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 DKP can perform quite well and be consistent with our theoretical analysis.

关键词： Dimensionality Reduction Random Projection Ezpected Distortion Analysis

作者: YUE-XIAN HOU PENG ZHANG

作者单位: Shool of Computer Science and Technology, Tianjin University, Tianjin 300072, China

会议类型: 国际会议

会议名称: 2008 International Conference on Machine Learning and Cybernetics(2008机器学习与控制论国际会议)

会议地点: 昆明

会议语种:英文

页码: 2331-2336

在线出版日期: 2008-07-12（万方平台首次上网日期，不代表论文的发表时间）