Stochastic Proximity Embedding: A Simple, Fast and Scalable Algorithm for Solving the Distance Geometry Problem

Stochastic proximity embedding (SPE) is a simple, fast, and scalable algorithm for generating low-dimensional Euclidean coordinates for a set of data points so that they satisfy a prescribed set of geometric constraints. Like other related methods, SPE starts with a random initial configuration and iteratively refines it by updating the positions of the data points so as to minimize the violation of the input constraints. However, instead of minimizing all violations at once using a standard gradient minimization technique, SPE stochastically optimizes one constraint at a time, in a manner reminiscent of back-propagation in artificial neural networks. Here, we review the underlying theory that gives rise to the SPE formulation and show how it can be successfully applied to a wide range of problems in data analysis, with particular emphasis on computational chemistry and biology.