# How to reconstruct a Euclidean distance matrix from grouped pairwise-distance means and standard deviations?

### Coordinates and Labels

Take the simple case of 3 distinct object classes and 5 instances of each class situated in 3D Euclidean space. The coordinates and labels might look like the following:

import numpy as np
np.random.seed(0)
coords = np.round(2 * np.random.rand(15, 3), 2)

array([[1.1 , 1.43, 1.21],
[1.09, 0.85, 1.29],
[0.88, 1.78, 1.93],
[0.77, 1.58, 1.06],
[1.14, 1.85, 0.14],
[0.17, 0.04, 1.67],
[1.56, 1.74, 1.96],
[1.6 , 0.92, 1.56],
[0.24, 1.28, 0.29],
[1.89, 1.04, 0.83],
[0.53, 1.55, 0.91],
[1.14, 0.04, 1.24],
[1.22, 1.23, 1.89],
[1.36, 0.72, 0.87],
[1.4 , 0.12, 1.33]])


Assume that the first 5 entries are from class 1, the next 5 are from class 2, and the last 5 are from class 3.

labels = [0]*5 + [1]*5 + [2]*5
print(labels)

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]


### Distance Matrix

The distance matrix is as follows:

from scipy.spatial import distance_matrix
dm = distance_matrix(coords, coords)
print(np.round(dm,1))

[[0.  0.6 0.8 0.4 1.2 1.7 0.9 0.8 1.3 1.  0.7 1.4 0.7 0.8 1.3]
[0.6 0.  1.1 0.8 1.5 1.3 1.2 0.6 1.4 0.9 1.  0.8 0.7 0.5 0.8]
[0.8 1.1 0.  0.9 1.8 1.9 0.7 1.2 1.8 1.7 1.1 1.9 0.6 1.6 1.8]
[0.4 0.8 0.9 0.  1.  1.8 1.2 1.2 1.  1.3 0.3 1.6 1.  1.1 1.6]
[1.2 1.5 1.8 1.  0.  2.6 1.9 1.8 1.1 1.3 1.  2.1 1.9 1.4 2.1]
[1.7 1.3 1.9 1.8 2.6 0.  2.2 1.7 1.9 2.2 1.7 1.1 1.6 1.6 1.3]
[0.9 1.2 0.7 1.2 1.9 2.2 0.  0.9 2.2 1.4 1.5 1.9 0.6 1.5 1.7]
[0.8 0.6 1.2 1.2 1.8 1.7 0.9 0.  1.9 0.8 1.4 1.  0.6 0.8 0.9]
[1.3 1.4 1.8 1.  1.1 1.9 2.2 1.9 0.  1.8 0.7 1.8 1.9 1.4 1.9]
[1.  0.9 1.7 1.3 1.3 2.2 1.4 0.8 1.8 0.  1.5 1.3 1.3 0.6 1.2]
[0.7 1.  1.1 0.3 1.  1.7 1.5 1.4 0.7 1.5 0.  1.7 1.2 1.2 1.7]
[1.4 0.8 1.9 1.6 2.1 1.1 1.9 1.  1.8 1.3 1.7 0.  1.4 0.8 0.3]
[0.7 0.7 0.6 1.  1.9 1.6 0.6 0.6 1.9 1.3 1.2 1.4 0.  1.1 1.3]
[0.8 0.5 1.6 1.1 1.4 1.6 1.5 0.8 1.4 0.6 1.2 0.8 1.1 0.  0.8]
[1.3 0.8 1.8 1.6 2.1 1.3 1.7 0.9 1.9 1.2 1.7 0.3 1.3 0.8 0. ]]


### Group-wise Avg and StdDev Pairwise Distances

These pairwise distances can be grouped into average and standard deviation distances between classes in two $$3\times3$$ matrices as follows:

# tuple of indices in shape of dm
dm_lbl = np.zeros_like(dm, dtype="object")
for i, x in enumerate(labels):
for j, y in enumerate(labels):
dm_lbl[i,j] = (x,y)

# vertical and horizontally stacked repeat labels
dm1 = np.array([labels] * dm.shape[0])
dm2 = np.array([labels] * dm.shape[1]).T

# populate group-wise avg and stdDev matrices
ulbls = np.unique(labels)
nlbls = len(ulbls)
avg_dm = np.zeros((nlbls, nlbls))
std_dm = np.zeros((nlbls, nlbls))
for i, lbl1 in enumerate(ulbls):
for j, lbl2 in enumerate(ulbls):
sub_dm = dm[(dm1 == lbl1) & (dm2 == lbl2)]
avg_dm[i,j] = np.mean(sub_dm)
std_dm[i,j] = np.std(sub_dm)

# display
print(avg_dm)
print(" ")
print(std_dm)

array([[0.81586136, 1.33203866, 1.19429853],
[1.33203866, 1.34536439, 1.3081833 ],
[1.19429853, 1.3081833 , 0.91314575]])

array([[0.54127464, 0.44786271, 0.51059085],
[0.44786271, 0.79856538, 0.4198672 ],
[0.51059085, 0.4198672 , 0.58520838]])


## Question

Is there some way reconstruct or sample from avg_dm and std_dm to recover or get something similar to dm as an intermediate step to obtaining coordinates? I say similar to dm because translational and rotational invariance is at play here, so the absolute positions don't matter - just the relative positions matter. Note that instances from within a class are indistinguishable, i.e. the order of the instances in each class is interchangeable.

I get that this is probably not a one-to-one problem, hence the idea of "sampling" from the distribution that's been defined and trying to find something close to that of the original.

## Possible Applications

• Reconstruction of atomic coordinates in a crystal structure with multiple elements from the periodic table. For example, trigonal $$Fe_2O_3$$ is a compound with two classes ($$Fe$$ and $$O$$) which occur in a ratio of 2:3, and there are 10 sites, meaning 4 $$Fe$$ instances and 6 $$O$$ instances.
• Reconstruction of molecular coordinates in a molecule
• Reconstruction of atomic coordinates in a crystal structure supercell (i.e. many units cells stacked on/around each other to better approximate an infinite lattice)

## Possible Solutions

1. Ignore the standard deviations and perform regular MDS, IsoMap, or similar
2. Use MDS repeatedly on samples of a post-symmetrized distance matrix (e.g. $$15\times15$$) based on repeated values of the means and standard deviations, average the distance matrices, and then use MDS on the averaged ($$15\times15$$) distance matrix
3. Use the setup from 2. and then reconstruct coordinates using a method that explicitly handles uncertainty (related, but without a suitable answer for this: Using a distance matrix *with errors* to find the coordinates of points)
4. Find and train a different compact representation, e.g. k-nearest neighbor graph, variational autoencoder