A GPU-Oriented Algorithm Design for Secant-Based Dimensionality Reduction
This work addresses a computational bottleneck in dimensionality reduction for data analysis, though it appears incremental as it focuses on GPU optimization of an existing mathematical framework.
The authors tackled the computational expense of secant-based dimensionality reduction by designing a polynomial-time algorithm that leverages GPU architecture to minimize computation time for calculating secant lines, resulting in a meaningful low-dimensional representation of data sets.
Dimensionality-reduction techniques are a fundamental tool for extracting useful information from high-dimensional data sets. Because secant sets encode manifold geometry, they are a useful tool for designing meaningful data-reduction algorithms. In one such approach, the goal is to construct a projection that maximally avoids secant directions and hence ensures that distinct data points are not mapped too close together in the reduced space. This type of algorithm is based on a mathematical framework inspired by the constructive proof of Whitney's embedding theorem from differential topology. Computing all (unit) secants for a set of points is by nature computationally expensive, thus opening the door for exploitation of GPU architecture for achieving fast versions of these algorithms. We present a polynomial-time data-reduction algorithm that produces a meaningful low-dimensional representation of a data set by iteratively constructing improved projections within the framework described above. Key to our algorithm design and implementation is the use of GPUs which, among other things, minimizes the computational time required for the calculation of all secant lines. One goal of this report is to share ideas with GPU experts and to discuss a class of mathematical algorithms that may be of interest to the broader GPU community.