Abstract
We introduce Non-Euclidean-MDS (Neuc-MDS), an extension of classicalMultidimensional Scaling (MDS) that accommodates non-Euclidean and non-metricinputs. The main idea is to generalize the standard inner product to symmetricbilinear forms to utilize the negative eigenvalues of dissimilarity Grammatrices. Neuc-MDS efficiently optimizes the choice of (both positive andnegative) eigenvalues of the dissimilarity Gram matrix to reduce STRESS, thesum of squared pairwise error. We provide an in-depth error analysis and proofsof the optimality in minimizing lower bounds of STRESS. We demonstrateNeuc-MDS's ability to address limitations of classical MDS raised by priorresearch, and test it on various synthetic and real-world datasets incomparison with both linear and non-linear dimension reduction methods.