Analysis of approaches to feature space partitioning for nonlinear dimensionality reduction

One of the most effective ways to reduce the computational complexity of nonlinear dimensionality reduction is hierarchical partitioning of the space with the subsequent approximation of calculations. In this paper, the efficiency of two approaches to space partitioning, the partitioning of input and output spaces, is analyzed. In addition, a method for nonlinear dimensionality reduction is proposed. It is based on construction of a partitioning tree of the input multidimensional space and an iterative procedure of the gradient descent with the approximation carried out on the nodes of the constructed space partitioning tree. In the method proposed, the relative position of the corrected objects and partitioning tree nodes in both input and output spaces is taken into account in the approximation. The method developed was analyzed based on publicly available datasets.