Saunderson–Chandrasekaran–Parrilo–Willsky ellipsoid-fitting conjecture

From papers

An origin-symmetric ellipsoid in \varmathbbRd{\varmathbb R}^d is specified by an equation

x,Qx=1,\langle x,Qx\rangle=1,

for a positive semidefinite matrix Q0Q\succeq 0. Let z1,,znz_1,\ldots,z_n be independent random points with

z1,,znN(0,1dId).z_1,\ldots,z_n\sim\mathcal N\left(0,\frac{1}{d}\cdot I_d\right).

Saunderson–Chandrasekaran–Parrilo–Willsky conjecture. For arbitrarily small ε>0\varepsilon>0, if n<(14ε)d2n<(\frac14-\varepsilon)\cdot d^2, then with high probability over z1,,znz_1,\ldots,z_n, there exists an ellipsoid passing through all the points.

The problem asks how many random Gaussian points can lie on a common ellipsoid and is motivated by recovering a subspace from noisy measurements through semidefinite programming. The conjecture was based on experimental results; the supplied source gives no resolution status, so it is recorded as open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Madhur Tulsiani and June Wu, “Ellipsoid fitting up to constant via empirical covariance estimation”, arXiv:2307.10941 (2023).

Solutions 0

No solutions have been posted yet.