Saunderson–Chandrasekaran–Parrilo–Willsky ellipsoid-fitting conjecture
Saunderson–Chandrasekaran–Parrilo–Willsky ellipsoid-fitting conjecture
An origin-symmetric ellipsoid in is specified by an equation
for a positive semidefinite matrix . Let be independent random points with
Saunderson–Chandrasekaran–Parrilo–Willsky conjecture. For arbitrarily small , if , then with high probability over , 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
Sign in to submit a solution.
No solutions have been posted yet.