Let $A=(d_{ij})$ be a distance matrix, i.e.,

  1. $d_{ii}=0$ for all $i$
  2. $d_{ij}>0$ for all $i\neq j$
  3. $d_{ij}=d_{ji}$ for all $i,j$
  4. $d_{ij}+d_{jk}\geq d_{ik}$ for all $i,j,k$

How to find a random distance matrix $A'$ close to $A$ (by any matrix norm)?

  • 1
    $\begingroup$ Please explain your statistical application. That will help us understand what you might mean by "random," which otherwise is too vague. After all, scaling all distances by any random positive value (using any distribution at all) will yield a "random distance matrix" and, by making that positive value likely to lie in a tiny neighborhood of $1,$ will yield a close matrix in any norm -- but that trivial construction seems unlikely to be of much use in any practical setting. $\endgroup$
    – whuber
    Commented Dec 21, 2022 at 18:23
  • 2
    $\begingroup$ Where does the distance matrix come from? If it's computed from a set of points, why not just perturb those points? $\endgroup$
    – whuber
    Commented Dec 21, 2022 at 18:36
  • 2
    $\begingroup$ @whuber good idea, and if it's not available for some reason, we can use MDS to get one "close" to it and perturb that. $\endgroup$ Commented Dec 21, 2022 at 18:54
  • 1
    $\begingroup$ @John Yes, but I am concerned such perturbations could be meaningless. For instance, if the MDS space has a smaller dimension than the original, then the perturbations will be artificially constrained. That doesn't mean your idea is bad or unworkable -- it's a natural approach -- but it throws a cautionary light on it. $\endgroup$
    – whuber
    Commented Dec 21, 2022 at 19:07
  • 1
    $\begingroup$ That idea is risky, because $A^\prime$ is not necessarily a distance matrix, even within arbitrarily small neighborhoods of $0$ (for $\epsilon$). Consider the case $A=\pmatrix{0&1&2\\1&0&1\\2&1&0}$ (the distance matrix for the points $(0,0),(1,0),(2,0)$) and $B=\pmatrix{0&1&1\\1&0&1\\1&1&0}$ (the distance matrix for an equilateral triangle). When $\epsilon \lt 0,$ $A+\epsilon B$ is not a distance matrix because it does not satisfy the triangle inequality. $\endgroup$
    – whuber
    Commented Dec 21, 2022 at 20:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.