To improve the localization accuracy of sensor network nodes and reduce the computational workload, a novel algorithm based on low-rank approximation was proposed. Given distance measurements obtained between sensors in the neighborhood, the proposed algorithm first fulfilled the Euclidean distance matrix (EDM) completion. Then, sensors’ positions were obtained by rigid transformation using anchors’ positions. To achieve accurate range information, the EDM completion stage exploited the low-rank essence of the Gram matrix of sensors’ coordinate matrix, resulting in a semidefinite programming (SDP) problem. Furthermore, some regularization term was introduced in our localization model to avoid degenerate solutions in the EDM completion stage. In practice, solving a large-scale SDP problem is still a challenging task. To improve the scalability of the proposed algorithm, an alternating direction method of multipliers (ADMM) was further developed. Compared with traditional algorithms (including multidimensional scaling method and other Euclidean distance-filling algorithms), this algorithm reduces the root mean square error by 28.2%~46.6% and the reconstruction error by 18.4%~64.5% in the case of large noise through simulation experiments, and the computation time is only 7% of that of SDP algorithm.