Fast stochastic neighbor embedding: a trust-region algorithm

Stochastic neighbor embedding (SNE) is a probabilistic method of embedding objects, described by high-dimensional vectors or by pair wise dissimilarities, into a lower dimensional space in a way that neighbor identities are preserved. Despite of the useful behavior of SNE, it suffers from its slow convergence due to a gradient-based implementation. In this paper we present a fast SNE algorithm which is approximately 4-6 times faster than the gradient-based SNE algorithm. Our fast SNE algorithm, named TR-SNE employs a trust-region (TR) method which finds a direction and a step size in an efficient and reliable manner with the help of a quadratic model of the objective function. We confirm the high performance and the fast convergence of our TR-SNR through numerical experiments.