Metric embeddings are key algorithmic and mathematical techniques in applied mathematics and approximation algorithms, and their adaptations are ubiquitous in machine learning. They are used to embed one metric space into another with the hope of revealing hidden structure or reducing the dimension of a data set. Examples include the random projection of a set of points in high dimensions to a lower dimension and the embedding of a graph into a tree-like structure. The fundamental limitation with the application of metric embeddings to machine learning is that their use in data analysis is predicated upon the input data coming from a metric space. Real data, however, do not necessarily conform to a metric; they are messy. The fundamental problem in our research program is metric repair: given a set of input distances, adjust them so that they conform to a metric.