Random projections for the distance geometry problem

International audienceRandom projections decrease the dimensionality of a finite set of vectors while ensuring approximate congruence, up to a multiplicative constant. Based on the theory of random projections in conic programming we derive an application of random projections to a nonconvex mathematical programming problem in distance geometry, namely that of finding the positions of the vertices of a graph in a vector space of given dimension, while ensuring that every pair of adjacent vertices is placed at a Euclidean distance equal to the corresponding edge weight