Points sampled from a Euclidean space should hopefully always embed in a Euclidean space

euclidean_metric.py

import numpy as np


# Give me some random vectors
def random_vectors_generator(dimension=10, num_vectors=10):
    for _ in range(num_vectors):
        yield np.random.rand(dimension)


# Give me a random distance matrix
def random_euclidean_metric_space_generator(dimension=10, num_vectors=10):
    while True:
        # generate random sets
        random_vectors = [random_vector for random_vector in random_vectors_generator(dimension, num_vectors)]

        # compute Gram matrix
        matrix_as_list = []
        for i in range(num_vectors):
            matrix_as_list.append([])
            for j in range(num_vectors):
                distance = np.linalg.norm(random_vectors[i] - random_vectors[j]) ** 2
                matrix_as_list[i].append(distance)

        yield np.array(matrix_as_list), random_vectors


# A finite metric space can be embedded in Euclidean space if the following matrix is positive semidefinite
# https://en.wikipedia.org/wiki/Euclidean_distance_matrix#Characterizations
def is_embeddable(distance_matrix):
    num_points = distance_matrix.shape[0]
    matrix_as_list = []
    for i in range(1, num_points):
        matrix_as_list.append([])
        for j in range(1, num_points):
            elt = (distance_matrix[0][i] + distance_matrix[0][j] - distance_matrix[i][j]) / 2
            matrix_as_list[i - 1].append(elt)

    is_this_positive_semidefinite = np.array(matrix_as_list)

    return np.all(np.linalg.eigvals(is_this_positive_semidefinite) >= 0)


if __name__ == "__main__":
    for random_distance_matrix, random_vectors in random_euclidean_metric_space_generator():
        if not is_embeddable(random_distance_matrix):
            print("Counterexample found!")
            print(random_vectors)
            exit()