Classical MDS

Intermediate Netflix, Spotify+5

Coordinates from distances alone

Multidimensional scaling starts from a matrix of pairwise distances and looks for points whose distances match. Classical MDS solves this exactly when the distances are Euclidean.

Implement classical_mds(D, k). Return coordinates of shape (n, k).

Square the distances: S = D ∘ D (element-wise).
Double-center: B = −½ J S J, where J = I − (1/n) 11ᵀ.
Take the eigendecomposition of B. Keep the k largest eigenvalues.
Coordinates are the eigenvectors times the square roots of their eigenvalues. A negative eigenvalue contributes a zero column.

Constraints

D must be square, symmetric, with a zero diagonal, otherwise raise ValueError.
1 ≤ k ≤ n, otherwise raise ValueError.
Do not modify D.

Hints

Hint 1

Write the centering as J @ S @ J with J = np.eye(n) - np.ones((n, n)) / n.

Keywords

classical-mlunsupervisedmdsdimensionality-reduction

Python

Run your code to see results

No results yet

Run your code to check it against the examples, or submit to run every test.