# Project new point into MDS space

I am trying to project a new point A(x, y, z) into a predefined MDS space in R. This is what I have so far:

set.seed(1)
x <- matrix(rnorm(3*10), ncol = 3)
DM <- dist(x)
MDS <- cmdscale(DM)

# New data point to be projected
A <- c(1, 2, 3)


I am not including A directly into x then fitting the MDS because it would affect the space coordinates. Is there a practical solution?

EDIT
I believe I found a solution by estimating the betas to predict the MDS axis:

x1 <- cbind(1, x) # add intercept
B <- solve(t(x1) %*% x1) %*% t(x1) %*% MDS # Betas

> MDS
[,1]        [,2]
[1,] -1.80789362  0.06801597
[2,] -0.64418055 -0.21163109
[3,]  0.04694820 -1.27040928
[4,]  3.39617277 -0.21657115
[5,] -0.96981358  0.46269025
[6,] -0.24716695 -0.79861234
[7,]  0.33620625  0.02618564
[8,]  0.62473570  1.35544267
[9,]  0.01895042  0.80023822
[10,] -0.75395865 -0.21534889

> x1 %*% B # same as MDS
[,1]        [,2]
[1,] -1.80789362  0.06801597
[2,] -0.64418055 -0.21163109
[3,]  0.04694820 -1.27040928
[4,]  3.39617277 -0.21657115
[5,] -0.96981358  0.46269025
[6,] -0.24716695 -0.79861234
[7,]  0.33620625  0.02618564
[8,]  0.62473570  1.35544267
[9,]  0.01895042  0.80023822
[10,] -0.75395865 -0.21534889

A <- c(1, 2, 3)
A <- c(1, A) # add intercept

> A %*% B # coordinates of A in the MDS plane
[,1]      [,2]
[1,] -2.759456 0.5927178


Is my procedure correct?

• @amoeba The idea is simply to plot A into the new MDS space in order to further improve the meaning of the plane drawn from the MDS. Don't know if this answers your question?
– mat
Sep 24, 2018 at 8:19
• I was just wondering if you have a specific application in mind, and if so, what that application is. Sep 24, 2018 at 8:21
• @amoeba In practice x represent some scores from participants, and A represent a "perfect score".
– mat
Sep 24, 2018 at 8:29
• @amoeba I edited my original post
– mat
Sep 24, 2018 at 9:10
• You use cmdscale which is just PCA and not really MDS. "Classical multidimensional scaling (MDS) of a data matrix. Also known as principal coordinates analysis (Gower, 1966)." rdocumentation.org/packages/stats/versions/3.5.1/topics/…. If that's what you want, then projecting a new point is trivial (as per your Edit). Sep 24, 2018 at 9:46

If you're using Euclidean distances, then classical MDS is equivalent to PCA, which readily defines a mapping into the low dimensional space, as amoeba mentioned. There should be various threads on this site describing how to do this. Otherwise, De Silva and Tenenbaum (2004) describe how to perform this mapping for classical MDS with arbitrary distances (note that it won't work for non-classical variants of MDS, e.g. non-metric MDS, variants that minimize the stress criterion, etc.). They call this procedure "distance-based triangulation". Although not originally formulated as such, it turns out to work by using the Nyström approximation, which is a way to approximate the eigenvalues/eigenvectors of a large matrix using a smaller submatrix (see Platt 2005).

Suppose we have $$n$$ training points. The squared distance between points $$i$$ and $$j$$ is stored in the $$(i,j)$$th entry of matrix $$\Delta_n$$. We use these distances with classical MDS to compute a $$k$$-dimensional embedding. Let each column of $$k \times n$$ matrix $$L_k$$ contain the low-dimensional embedding coordinates of a training point. Let $$L_k^\#$$ denote the transpose of the pseudoinverse of $$L_k$$. Instead of starting from scratch, this can be computed using components that were originally used to compute $$L_k$$ (see the paper for details). Let $$\vec{\delta}_i$$ denote the $$i$$th column of $$\Delta_n$$ (containing the squared distances from point $$i$$ to all other points), and let $$\vec{\delta}_\mu = \frac{1}{n} \sum_{i=1}^n \vec{\delta}_i$$ denote the mean of the columns.

Now, suppose we want to map a new point $$a$$ into the low dimensional space. Compute vector $$\vec{\delta}_a$$, containing the squared distance from $$a$$ to every training point. The low dimensional emedding coordinates of $$a$$ are then given by:

$$\vec{x}_a = -\frac{1}{2} L_k^\# (\vec{\delta}_a - \vec{\delta}_\mu)$$

References:

De Silva and Tenenbaum (2004). Sparse multidimensional scaling using landmark points.

Platt (2005). FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms.

• +1 Interesting. But I suggest you mention that if one uses "real" (what's the term?) MDS as opposed to "classical" MDS, then a mapping is not possible at all. By "real" I mean what Wikipedia calls metric MDS with "stress" loss function; this is what I think by default when somebody says "MDS". Sep 24, 2018 at 10:39
• @amoeba true, this wouldn't work for non-classical MDS (the real stuff :). I'll edit to emphasize that Sep 24, 2018 at 10:45
• Has anyone tested the accuracy of this in some capacity? Aug 13, 2021 at 5:10
• For pairwise distances computed using the earth mover's distance, I get reasonable (95%) correspondence between the true distances and a PCA embedding to 3 dimensions. However, if I use this out-of-sample MDS approach, the parity plot is a large blob. Aug 13, 2021 at 6:44
• ~4000 training points and ~700 validation points Aug 13, 2021 at 6:53

As per amoeba's comment, another practical solution in R would be to use the stats::prcomp() and its associated predict() method if using the Euclidean distance for your MDS:

set.seed(1)
x <- matrix(rnorm(3*10), ncol = 3)

# New data point to be projected
A <- c(1, 2, 3)

> predict(prcomp(x, rank. = 2), matrix(A, nrow = 1))
PC1        PC2
[1,] -2.759456 -0.5927178