The Strict Threshold for Gaussian Ellipsoid Fitting

Abstract

Let x_1, . . . , x_n be independent N(0, I_d) vectors. We study whether there exists a positive semidefinite matrix S such that xi^T S xi = d for every 1 ≤ i ≤ n. We prove a sharp threshold at n ∼ d^2/4. If limsup_d→∞ n(d)/d^2 < 1/4 , then with probability tending to one such an S exists, with S in fact positive definite. If liminf_d→∞ n(d) / d^2 > 1/4 , then with probability tending to one no such S exists. We make no claim when n(d)/d^2 → 1/4. We remark on the use of AI in this research, see Statement of AI Use.