ROBUST MULTIDIMENSIONAL SCALING EMPLOYING M-ESTIMATORS AND NUCLEAR NORM REGULARIZATION

Multidimensional Scaling (MDS) is applied to pairwise dissimilarities between entities, aiming to map each entity to a point in a geometric space so that the inter-point distances preserve the pairwise dissimilarities. The well-known algorithms for solving the MDS problem are vulnerable to gross errors (outliers), inducing highly corrupted embeddings. To cope with such gross errors, two algorithms are proposed, which resort to half-quadratic optimization, employing M-estimators and nuclear norm regularization. It is demonstrated by experiments that the proposed algorithms outperform the state-of-the-art MDS ones.