Fitting an ellipsoid to random points: predictions using the replica method
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913387160535040 |
|---|---|
| author | Maillard, Antoine Kunisky, Dmitriy |
| author_facet | Maillard, Antoine Kunisky, Dmitriy |
| contents | 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 α> 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_01169 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fitting an ellipsoid to random points: predictions using the replica method Maillard, Antoine Kunisky, Dmitriy Disordered Systems and Neural Networks Statistical Mechanics Data Structures and Algorithms Probability Statistics Theory 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 α> 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. |
| title | Fitting an ellipsoid to random points: predictions using the replica method |
| topic | Disordered Systems and Neural Networks Statistical Mechanics Data Structures and Algorithms Probability Statistics Theory |
| url | https://arxiv.org/abs/2310.01169 |