probability-statistics / Random matrix theory
Given $n$ independent standard Gaussian vectors in $\mathbb{R}^d$, an ellipsoid fit is a positive semidefinite matrix $S$ with $x_i' S x_i = d$ for every $i$. Saunderson, Parrilo and Willsky conjectured that this semidefinite feasibility problem has a sharp threshold at $n \sim \frac{d^2}{4}$. Proved: below the threshold a fit exists with probability tending to one, above it none does.
Temporal state
No reconciled state yet.
Append-only history
Closes both gaps left open by Bandeira and Maillard: exact fitting, and removal of the operator-norm constraint. The threshold turns out to be governed by the statistical dimension d(d+1)/4 of the PSD cone.
Research memory
Given $n$ independent standard Gaussian vectors in $\mathbb{R}^d$, an ellipsoid fit is a positive semidefinite matrix $S$ with $x_i' S x_i = d$ for every $i$. Saunderson, Parrilo and Willsky conjectured that this semidefinite feasibility problem has a sharp threshold at $n \sim \frac{d^2}{4}$. Proved: below the threshold a fit exists with probability tending to one, above it none does.
Closes both gaps left open by Bandeira and Maillard: exact fitting, and removal of the operator-norm constraint. The threshold turns out to be governed by the statistical dimension d(d+1)/4 of the PSD cone.
Evidence graph
No public relationships recorded yet.