{
  "id": "1809.09879",
  "version": "v1",
  "published": "2018-09-26T09:55:03.000Z",
  "updated": "2018-09-26T09:55:03.000Z",
  "title": "Learning random points from geometric graphs or orderings",
  "authors": [
    "Josep Diaz",
    "Colin McDiarmid",
    "Dieter Mitsche"
  ],
  "categories": [
    "math.PR",
    "cs.LG",
    "math.ST",
    "stat.TH"
  ],
  "abstract": "Suppose that there is a family of $n$ random points $X_v$ for $v \\in V$, independently and uniformly distributed in the square $\\left[-\\sqrt{n}/2,\\sqrt{n}/2\\right]^2$. We do not see these points, but learn about them in one of the following two ways. Suppose first that we are given the corresponding random geometric graph $G$, where distinct vertices $u$ and $v$ are adjacent when the Euclidean distance $d_E(X_u,X_v)$ is at most $r$. Assume that the threshold distance $r$ satisfies $n^{3/14} \\ll r \\ll n^{1/2}$. We shall see that the following holds with high probability. Given the graph $G$ (without any geometric information), in polynomial time we can approximately reconstruct the hidden embedding, in the sense that, `up to symmetries', for each vertex $v$ we find a point within distance about $r$ of $X_v$; that is, we find an embedding with `displacement' at most about $r$. Now suppose that, instead of being given the graph $G$, we are given, for each vertex $v$, the ordering of the other vertices by increasing Euclidean distance from $v$. Then, with high probability, in polynomial time we can find an embedding with the much smaller displacement error $O(\\sqrt{\\log n})$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-09-26T09:55:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "learning random points",
      "polynomial time",
      "euclidean distance",
      "high probability",
      "corresponding random geometric graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}