2023/10/02 by Antoine Maillard, Dmitriy Kunisky, Maillard, Antoine +1 · 3 citations
Computer Science · Mathematics · #Geochemistry and Geologic Mapping #Morphological variations and asymmetry #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2310.01169
We consider the problem of fitting a centered ellipsoid to n standard Gaussian random vectors in ℝd, as n, d → ∞ with n/d2 → α> 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 α< 1/4, and unsatisfiable (UNSAT) for α> 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 α= 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.