Parallel non-linear dimension reduction algorithm on GPU. (27th October 2011)

• Record Type: Journal Article
• Authors: Yeh, Tsung Tai; Chen, Tseng Yi; Chen, Yen Chiu; Wei, Hsin Wen
• Is Part Of: International journal of granular computing, rough sets and intelligent systems. Volume 2:Number 2(2011)
• Page Start: 149
• Page End: 165
• Publication Date: 2011-10-27
• Subjects: non-linear -- dimensionality reduction -- GPU; Intelligent agents (Computer science) -- Periodicals; 006.3
• Languages: English
• ISSNs: 1757-2703

Abstract

Advances in non-linear dimensionality reduction provide a way to understand and visualise the underlying structure of complex datasets. The performance of large-scale non-linear dimensionality reduction is of key importance in data mining, machine learning, and data analysis. In this paper, we concentrate on improving the performance of non-linear dimensionality reduction using large-scale datasets on the GPU. In particular, we focus on solving problems including k -nearest neighbour (KNN) search and sparse spectral decomposition for large-scale data, and propose an efficient framework for local linear embedding (LLE). We implement a k-d tree-based KNN algorithm and Krylov subspace method on the GPU to accelerate non-linear dimensionality reduction for large-scale data. Our results enable GPU-based k-d tree LLE processes of up to about 30–60´ faster compared to the brute force KNN (Hernandez et al., 2007) LLE model on the CPU. Overall, our methods save O ( n 2 – 6 n – 2 k – 3) memory space.