Vrftsjtryk

Suppose you have 3 shops and 2 supply units, and you only know the 6 pairwise (Euclidean, assuming 2D) distances between each shop and each supply unit, but not the pairwise distances between the shops and between the units.

df2 <- structure(list(shop = c("shop 1", "shop 2", "shop 3", "shop 1", 

"shop 2", "shop 3"), supply = c("supply 1", "supply 1", "supply 1", 

"supply 2", "supply 2", "supply 2"), distance = c(2.8, 5.4, 1.4, 

4.2, 3, 6.3)), .Names = c("shop", "supply", "distance"), row.names = c(NA, 

-6L), class = "data.frame")



df2

    shop   supply distance

1 shop 1 supply 1      2.8

2 shop 2 supply 1      5.4

3 shop 3 supply 1      1.4

4 shop 1 supply 2      4.2

5 shop 2 supply 2      3.0

6 shop 3 supply 2      6.3

How could you represent the shops and supply units in a 2D plot, so that the pairwise distances are 'more or less' conserved?

I did my searches and reading about this topic, and I know that Multi Dimensional Scaling (cmdscale in R) is a technique that converts a distance matrix into a set of coordinates. Trouble is, as far as I can tell it only accepts complete distance matrices. I tried:

fulldf <- expand.grid(loc1=unique(c(df2$shop,df2$supply)),loc2=unique(c(df2$shop,df2$supply)),stringsAsFactors = F)



mdf <- merge(fulldf,df2,by.x=c("loc1","loc2"),by.y=c("shop","supply"),all.x=T)



distmat <- as.matrix(xtabs(distance~loc1+loc2,mdf,na.action=na.pass))



distmat[distmat==0] <- NA



distmat

          loc2

loc1       shop 1 shop 2 shop 3 supply 1 supply 2

  shop 1                             2.8      4.2

  shop 2                             5.4      3.0

  shop 3                             1.4      6.3

  supply 1                                       

  supply 2                                       



cmdscale(as.dist(distmat))

Error in cmdscale(as.dist(distmat)) : NA values not allowed in 'd'

So I looked for ways to 'fill the missing values' in the distance matrix.
Packages like softImpute seem to do that, but I am not sure they are OK for a distance matrix, where some conditions must be respected (for instance all diagonal elements should be 0). When I tried softImpute on the above matrix, it gave me non-zero values on the diagonal.

These papers seem to be related to this topic:

https://arxiv.org/pdf/1811.12803.pdf

http://lipas.uwasa.fi/~rvir/matrix_reconstruction_SECON06.pdf

https://pdfs.semanticscholar.org/c7ba/9941e547d1f4c05e70716f7a58ff2826024a.pdf

but the maths is far above my level.

Question: Does anyone know if the methods described in these papers (or something similar) are implemented in any R packages?

I found this one:

https://rdrr.io/cran/edmcr/

but apparently it has been removed from CRAN because of some 'problems':

https://cran.r-project.org/web/packages/edmcr/index.html

That's a shame, because it seemed to do exactly what I needed. I tried installing the archived version but it didn't work.

I saw this post too:

https://stats.stackexchange.com/questions/56827/r-multidimensional-scaling-and-missing-values

but the link in the post is broken.

I tried other approaches, too.

For instance using Excel's Solver. I wrote an initial set of coordinates, (0,0) for all 5 points, and the corresponding calculated pairwise distances, and ran the iterations to find the coordinates for which the sum of squared differences between the known and calculated distances was minimal. Bizarrely, starting with (0,0) everywhere resulted in all points being aligned on a straight line, and a very disappointing sum of squares. Starting with random coordinates instead gave a very good picture. But yeah, I wouldn't want to use Excel if possible. I'd rather stick to R.

Maybe I could use nlm to do a non-linear minimization of the same type as I did in Excel. Would that be the right thing to do?

Apart from the above question, answering which is my main objective at the moment, I considered the problem from a theoretical point of view as well, and I got a bit stuck.

If we have $S$ shops and $U$ supply units, the total number of coordinates to calculate is $2 cdot (S+U)$. The number of possible pairwise distances (meaning only between shops and units) is $S cdot U$.

It is easy to show that the number of coordinates is always larger than the number of possible pairwise distances for $U=1$ or $U=2$. This makes sense: with 1 supply unit, I can put as many shops as I want, and each of them is free to be placed on a circumference with the specified radius around it. With 2 supply units, things become more rigid, but there is still some freedom.

However, for any $U>2$, the number of coordinates is larger than the number of possible pairwise distances only if $S > 2 cdot frac U {U-2}$.

So for instance for $U=3$ and $S=6$ it looks like there are as many coordinates as possible pairwise distances (18).

Does that mean that with 3 supply units and 6 shops, once you specify all possible pairwise shop-unit distances, the coordinates of all points are exactly fixed? Shouldn't the positions of the points be subject to translation, rotation, reflection without altering the pairwise distances?
And what if an additional shop is added to the above configuration? Is its position somehow 'forced'? How is that possible?

Going even further, if one does not distinguish between shops and units, so $N$ locations are considered 'equivalent', then the number of coordinates is $2 cdot N$ and the number of possible pairwise distances is $N cdot (N-1) / 2$.

With $N=1$, there is complete freedom: the 2 coordinates can be chosen any way we want, and there is no distance.

With $N=2$, there are 4 coordinates and 1 possible distance, so we need to fix 3 coordinates: the 2 coordinates of one point and either the x or y of the other point; then specifying the distance determines the 4th coordinate.

With $N=3$, 6 coordinates and 3 possible distances, so again 3 coordinates need to be fixed before the whole system is determined.

With $N=4$, 8 coordinates and 6 possible distances, so once the 6 distances are specified, it appears that only 2 coordinates need to be fixed to determine the positions of all points.

However, with $N=5$ there are as many possible pairwise distances as coordinates. This would seem to imply that if you specify all pairwise distances, there is no freedom to choose any of the coordinates, which, like for the shop-unit case, is puzzling to me, as I would think that you can always translate, rotate, reflect all the points together.

And for any $N>5$, it would even seem that once you specify $2 cdot N$ distances, the remaining distances are already determined. Is that so?