Constant-Degree Localization for Gaussian Mean-Shift Contamination with Unknown Covariance

We study estimation of the distinguished mean in a Gaussian mean-shift mixture with unknown common covariance, sufficiently small constant contamination, and unrestricted outlier locations. We construct an observable mean-covering subspace of dimension ε^(−C)(1+log d) using poly(d,1/ε) samples and time, with absolute exponents. The main new mechanism is a constant-degree rational score family: a majority-atom Christoffel inequality supplies a witness, a fixed inverse-heat expansion transfers it to noisy observations, and a fixed-degree sum-of-squares Gaussian coupling localizes every high-score pseudoexpectation. Combined with cumulative quadratic reweighting and a convex subspace game, this yields two estimation tradeoffs. One has sample and runtime d^C exp(C ε^(−8) log^8(e/ε)), with a dimension exponent independent of accuracy. Another uses poly(d,1/ε)+ε^(−C) log(ed) exp(C/ε²) samples, but has runtime (d/ε)^C+exp(C ε^(−C) log(ed)+C/ε²). The guarantee is Euclidean error ε√(‖Σ‖_op). Neither tradeoff gives simultaneously optimal sample complexity and sample-polynomial computation.