One-step Spectral Estimation for Euclidean Distance Matrix Approximation

This paper proposes and analyzes a new spectral estimator for Euclidean Distance Matrix Completion (EDMC) problem under Bernoulli sample model. This new estimator can be viewed as a simplified version of the well-known SVD (Singular Value Decomposition)-MDS (Multidimensional Scaling) approach by Drineas et al. as it reduces the computational cost while maintaining almost the same performance. Its approximation accuracy, when measured by the spectral norm, is analyzed under the presence of zero-mean, entry-wise independent, sub-Gaussian additive noise. Theoretical results show that the approximation error is well-controlled up to the noise amplification term as soon as the sample complexity reaches the order of ${\mathcal{O}}\left({{{\log }^2}n/n}\right)$. Numerical simulations verify the above assertions.