Sparsity-Exploiting Robust Multidimensional Scaling

Multidimensional scaling (MDS) seeks an embedding of N objects in a p <; N dimensional space such that inter-vector distances approximate pairwise object dissimilarities. Despite their popularity, MDS algorithms are sensitive to outliers, yielding grossly erroneous embeddings even if few outliers contaminate the available dissimilarities. This work introduces robust MDS approaches exploiting the degree of sparsity in the outliers present. Links with compressive sampling lead to robust MDS solvers capable of coping with unstructured and structured outliers. The novel algorithms rely on a majorization-minimization approach to minimize a regularized stress function, whereby iterative MDS solvers involving Lasso and sparse group-Lasso operators are obtained. The resulting schemes identify outliers and obtain the desired embedding at computational cost comparable to that of their nonrobust MDS alternatives. The robust structured MDS algorithm considers outliers introduced by a sparse set of objects. In this case, two types of sparsity are exploited: i) sparsity of outliers in the dissimilarities; and ii) sparsity of the objects introducing outliers. Numerical tests on synthetic and real datasets illustrate the merits of the proposed algorithms.