{
  "id": "2310.01169",
  "version": "v1",
  "published": "2023-10-02T12:57:39.000Z",
  "updated": "2023-10-02T12:57:39.000Z",
  "title": "Fitting an ellipsoid to random points: predictions using the replica method",
  "authors": [
    "Antoine Maillard",
    "Dmitriy Kunisky"
  ],
  "comment": "39 pages",
  "categories": [
    "cond-mat.dis-nn",
    "cond-mat.stat-mech",
    "cs.DS",
    "math.PR",
    "math.ST",
    "stat.TH"
  ],
  "abstract": "We consider the problem of fitting a centered ellipsoid to $n$ standard Gaussian random vectors in $\\mathbb{R}^d$, as $n, d \\to \\infty$ with $n/d^2 \\to \\alpha > 0$. It has been conjectured that this problem is, with high probability, satisfiable (SAT; that is, there exists an ellipsoid passing through all $n$ points) for $\\alpha < 1/4$, and unsatisfiable (UNSAT) for $\\alpha > 1/4$. In this work we give a precise analytical argument, based on the non-rigorous replica method of statistical physics, that indeed predicts a SAT/UNSAT transition at $\\alpha = 1/4$, as well as the shape of a typical fitting ellipsoid in the SAT phase (i.e., the lengths of its principal axes). Besides the replica method, our main tool is the dilute limit of extensive-rank \"HCIZ integrals\" of random matrix theory. We further study different explicit algorithmic constructions of the matrix characterizing the ellipsoid. In particular, we show that a procedure based on minimizing its nuclear norm yields a solution in the whole SAT phase. Finally, we characterize the SAT/UNSAT transition for ellipsoid fitting of a large class of rotationally-invariant random vectors. Our work suggests mathematically rigorous ways to analyze fitting ellipsoids to random vectors, which is the topic of a companion work.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-10-02T12:57:39.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "replica method",
      "random points",
      "standard gaussian random vectors",
      "predictions",
      "sat/unsat transition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 39,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}