  Classical multidimensional scaling only works well when the noisy distances
observed in a high dimensional space can be faithfully represented by Euclidean
distances in a low dimensional space. Advanced models such as Maximum Variance
Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite
Programming (SDP) to reconstruct such faithful representations. While those SDP
models are capable of producing high quality configuration numerically, they
suffer two major drawbacks. One is that there exist no theoretically guaranteed
bounds on the quality of the configuration. The other is that they are slow in
computation when the data points are beyond moderate size. In this paper, we
propose a convex optimization model of Euclidean distance matrices. We
establish a non-asymptotic error bound for the random graph model with
sub-Gaussian noise, and prove that our model produces a matrix estimator of
high accuracy when the order of the uniform sample size is roughly the degree
of freedom of a low-rank matrix up to a logarithmic factor. Our results
partially explain why MVU and MVE often work well. Moreover, we develop a fast
inexact accelerated proximal gradient method. Numerical experiments show that
the model can produce configurations of high quality on large data points that
the SDP approach would struggle to cope with.
