Classical Multidimensional Scaling (CMDS) is a cornerstone of data science, providing a robust method for embedding high-dimensional data into low-dimensional Euclidean spaces based on pairwise distances. While the standard formulation of CMDS is well-established, a more recent "dual basis" framework has emerged to address complex challenges such as missing distance data in Euclidean Distance Geometry. This paper provides the first rigorous theoretical foundation for this approach, solving long-standing puzzles regarding the spectral properties of the underlying operators.
The Dual Basis Framework
The dual basis approach relies on a set of basis matrices and their corresponding duals to reconstruct the Gram matrix of a point set. Central to this method is the inner product matrix $H$, which characterizes the relationship between these basis elements. Historically, the spectrum of $H$ was only understood through empirical bounds rather than exact values, and the dual basis vectors themselves were defined through cumbersome, multi-case formulas.
This research simplifies the framework by demonstrating that the dual basis vectors $v_\alpha$ possess a specific, low-rank "dyadic" structure. Specifically, they can be represented as the symmetric outer product of two vectors derived from the standard centering matrix. This rank-2 representation makes the dual basis significantly easier to compute and analyze than previous piecewise definitions suggested.
Spectral Graph Theory and the Triangular Graph
A key innovation of this work is the connection established between linear algebra and spectral graph theory. The authors demonstrate that the inner product matrix $H$ is essentially a shifted version of the adjacency matrix of a triangular graph ($T_n$).
By mapping the MDS problem onto this graph structure, the authors were able to port known results from graph theory to provide an exact characterization of the spectrum of $H$. They prove that for any set of $n$ objects, $H$ has exactly three distinct eigenvalues: $2, n,$ and $2n$. This result replaces previous approximations with a precise mathematical identity.
Stability and the Metric Nearness Problem
The paper further explores the robustness of the dual basis expansion under noise. By establishing a concrete stability bound, the authors show that the error in a recovered Gram matrix is at most four times the maximum error in the input distance matrix.
This analysis also bridges the gap between MDS and the "metric nearness problem"—the task of finding the closest valid distance matrix to a noisy set of observations while satisfying the triangle inequality. The authors prove that the constraint matrices used in metric nearness are identical to the MDS basis matrices up to a diagonal scaling.
As shown in the table above, the matrix $A$ encodes the relationships required to satisfy the triangle inequality. This work provides the first formal proof for the singular values of this matrix, a property that had been observed empirically in literature since 2003 but remained unproven until now.
Conclusion
By unifying multidimensional scaling with spectral graph theory, this paper provides a complete theoretical picture of the dual basis approach. The derivation of exact eigenvalues for $H$ and the simplified dyadic form for dual basis vectors provide practitioners with more efficient tools for distance geometry. Future work aims to extend these spectral insights to the "sampled regime," where pairwise distances are only partially known, potentially leveraging matrix pencils to characterize the resulting Gram matrices.
Summary updated