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

Question

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

See also https://stackoverflow.com/questions/45764761/algorithmically-correcting-noisy-distance-measurements-between-data-points-on-a

Answer 1

As the summary statistics of the between class averages and standard deviations have much less degrees of freedoms than the original distance matrix, there will be many possible point configurations that match the summary statistics. Here is a rough idea how to construct one possible solution:

1. Use classical MDS to reconstruct a configuration of the class centers (i.e. class means) that matches the class mean distances. One possible method is described in

J.C. Gower: "Some distance properties of latent root and vector methods used in multivariate analysis." Biometrika 53.3-4, pp. 25-338, 1966

2. Set all points within each class equal to the mean (center) of the class, except for two points.

3. Chose the remaining two points in each class in opposite directions from the center, such that the given variances per class are met.