Sharp Phase Transition for Ellipsoid Fitting
We resolve the ellipsoid fitting conjecture of Saunderson, Chandrasekaran, Parrilo, and Willsky up to a vanishing factor. Concretely, for $m$ independent Gaussian points in dimension $d$, we show that with high probability, for $m \leq (1-o_d(1)) \cdot d^2/4$, there exists a centered ellipsoid passing through all $m$ points; for $m\geq (1+o_d(1) )\cdot d^2/4$, no such ellipsoid exists. This confirms that the ellipsoid fitting problem has a sharp phase transition at $d^2/4$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.12415
curl -X POST /api/v1/records/arxiv/2608.12415/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.12415/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'