  Localizing a cloud of points from noisy measurements of a subset of pairwise
distances has applications in various areas, such as sensor network
localization and reconstruction of protein conformations from NMR measurements.
In [1], Drineas et al. proposed a natural two-stage approach, named SVD-MDS,
for this purpose. This approach consists of a low-rank matrix completion
algorithm, named SVD-Reconstruct, to estimate random missing distances, and the
classic multidimensional scaling (MDS) method to estimate the positions of
nodes. In this paper, we present a detailed analysis for this method. More
specifically, we first establish error bounds for Euclidean distance matrix
(EDM) completion in both expectation and tail forms. Utilizing these results,
we then derive the error bound for the recovered positions of nodes. In order
to assess the performance of SVD-Reconstruct, we present the minimax lower
bound of the zero-diagonal, symmetric, low-rank matrix completion problem by
Fano's method. This result reveals that when the noise level is low, the
SVD-Reconstruct approach for Euclidean distance matrix completion is suboptimal
in the minimax sense; when the noise level is high, SVD-Reconstruct can achieve
the optimal rate up to a constant factor.
