How can classical multidimensional scaling go wrong?

Multidimensional scaling (MDS) originated in the mid-20th century as a technique to embed high-dimensional data into low-dimensional Euclidean space based on pairwise dissimilarities. Classical MDS (cMDS), introduced by Torgerson, leverages spectral decomposition of the centered squared distance matrix, enabling fast computation and wide applicability. Over time, variants like non-metric MDS and multi-way MDS expanded its scope. However, many real-world data, such as graphs, social networks, or incomplete measurements, involve non-Euclidean distances, challenging the assumptions underlying cMDS. Existing methods often ignore the eigenstructure of the distance matrix, leading to suboptimal embeddings and degraded downstream task performance. Despite empirical observations of embedding errors increasing with dimension in non-Euclidean settings, a rigorous theoretical understanding was lacking, motivating this study.

The core issue is that cMDS, designed under Euclidean assumptions, performs poorly on non-Euclidean metrics. Specifically, when the distance matrix contains many negative eigenvalues, increasing the embedding dimension can paradoxically worsen the approximation error, undermining the embedding's utility for tasks like classification. This problem is exacerbated in noisy, incomplete, or graph-structured data, where the eigenstructure is complex. The challenge lies in quantifying this degradation and developing computationally feasible methods to improve robustness, especially for large-scale datasets.

The paper's key innovations include: 1) deriving an explicit eigenvalue-based error formula that links negative eigenvalues to embedding degradation; 2) revealing that the number of negative eigenvalues predicts the error increase with dimension; 3) proposing an efficient algorithm to construct a matrix Dl that approximates D more closely than the Euclidean closest Dt, without requiring metric properties; 4) empirically demonstrating that Dl improves embedding stability and classification accuracy in non-Euclidean settings. This approach bridges theoretical insights with practical algorithms, addressing a critical gap in high-dimensional, non-Euclidean data analysis.

• �� Derive the Frobenius norm error formula for D − D_cmds based on the eigenvalues of a matrix obtained from D, emphasizing the role of negative eigenvalues. • Use spectral decomposition of the matrix ˆD, obtained via conjugation with the Householder matrix Q, to analyze the eigenstructure. • Decompose the error into three components: one related to discarded eigenvalues (C1), trace differences (C2), and a term involving the eigenvectors (C3). • Show that C1 decreases with increasing dimension, but C2 and C3 can cause the total error to increase when negative eigenvalues are present. • Develop an algorithm to compute Dl by projecting D onto a space of matrices with controlled eigenvalues, ensuring the Frobenius error does not grow with dimension. • Validate the approach through theoretical bounds and extensive experiments on synthetic and real datasets.

The experimental setup includes synthetic datasets with controlled eigenvalue spectra, graph-based datasets (e.g., C. elegans, Portugal), and real-world noisy or incomplete data (e.g., MNIST with missing pixels). The methods compared are standard cMDS, the proposed Dl-based approach, and the true SSTRESS solution where feasible. Metrics include Frobenius error, classification accuracy using neural networks and nearest neighbors, and robustness to noise. The experiments vary embedding dimensions from low to high, observing error trends and downstream task performance. Results confirm that errors increase with dimension for cMDS on non-Euclidean data, while Dl maintains stable errors and improves classification accuracy, validating the theoretical predictions.

Empirical data shows that Frobenius error and classification accuracy degrade as embedding dimension increases in non-Euclidean settings for cMDS. The eigenvalue analysis accurately predicts the error increase point. The Dl matrix consistently outperforms standard cMDS, with error reductions of up to 30% and accuracy gains of 5-10%. The approach remains computationally feasible, with eigen-decomposition as the main bottleneck, and effectively handles noisy and incomplete data, demonstrating robustness and practical utility.

The methods are applicable in network embedding, bioinformatics, social network analysis, and any scenario involving complex or noisy dissimilarity data. They enable more reliable visualization, clustering, and classification, especially when data do not conform to Euclidean assumptions. The approach can be integrated into existing pipelines to improve robustness and interpretability, facilitating advanced data exploration and decision-making in diverse fields.

The eigenvalue-based approach relies on symmetry and hollowness of the distance matrix, limiting applicability to certain data types. Computational costs remain high for very large datasets due to eigen-decomposition. The non-metric Dl matrix, while effective, restricts geometric interpretability. Future work should focus on scalable approximations, extending to asymmetric or non-hollow matrices, and exploring metric-preserving variants.