Recovering Lower-Dimensional Semialgebraic Support of a Measure from its Moments

Mixture models, such as Gaussian mixture models, are widely used in machine learning to represent complex data distributions. A key challenge, especially in high-dimensional settings, is to determine the mixture order and estimate the mixture parameters. We study the problem of approximating a target measure, available only through finitely many of its moments, by a mixture of distributions from a parametric family (e.g., Gaussian, exponential, Poisson), with approximation quality measured by the 2-Wasserstein or the total variation distance. Unlike many existing approaches, the parameter set is not assumed to be finite; it is modeled as a compact basic semi-algebraic set. We introduce a hierarchy of semidefinite relaxations with asymptotic convergence to the desired optimal value. In addition, when a certain rank condition is satisfied, the convergence is even finite and recovery of an optimal mixing measure is obtained. We also present an application to clustering, where our framework serves either as a stand-alone method or as a preprocessing step that yields both the number of clusters and strong initial parameter estimates, thereby accelerating convergence of standard (local) clustering algorithms.

We study the approximation of probability measures in the Wasserstein-$p$ distance by structured classes of approximators, motivated by applications in imaging, machine learning, and physical measurement under sensor constraints. We obtain three sets of results. First, for measures with densities bounded away from zero on a bounded Lipschitz domain $Ω$, we prove that any approximation scheme for functions in $\mathrm{L}_p(Ω)$ transfers, with linear rate, to a corresponding approximation scheme for measures in $\mathrm{W}_p(Ω)$. The argument applies a theorem of Bogovskii on regularity of solutions to the continuity equation in the Benamou-Brenier formulation of optimal transport. We exhibit concrete approximation schemes (polynomials, shift-invariant spaces, cardinal interpolation with radial basis functions, kernel density estimators, and piecewise approximations on nonuniform Voronoi partitions) that fit the framework. As a matter of independent interest, we prove a negative Sobolev lower bound that generalizes existing bounds from $p=2$ to all $p\in(1,\infty)$. We also consider deterministic bounds for discrete approximations to arbitrary measures in terms of the mesh norm of a quasi-uniform set of points. We specialize these bounds to show that compactly supported measures admit a deterministic $N$-term approximation $μ_N$ such that $\mathrm{W}_p(μ,μ_N) = O(N^{-\frac{1}{d}})$ for all $d\geq 1$, which matches the asymptotic optimal quantizer rate. We also extend these results to non-compactly supported measures with appropriate tail decay.

For an arbitrary isotropic log-concave distribution $P$ on $\mathbb{R}^d$, we prove that the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares for every even $m\ge2$, where $C>0$ is a universal constant. This removes the dependence on the Poincaré constant in the theorem of Kothari and Steinhardt (arXiv:1711.07465), recovering the optimal moment bounds for log-concave distributions. As an immediate corollary, we obtain computationally efficient algorithms with dimension-free error guarantees for a wide range of high-dimensional statistical estimation problems. Our proof uses stochastic localization to decompose $P$ as an average of random strongly log-concave measures, whose centered moments admit the subgaussian certificates of Diakonikolas, Hopkins, Pensia, and Tiegel (STOC 2025; arXiv:2410.21194). With a covariance-adapted choice of localization, we show that a fourth-moment certificate derived from Letwin's variance inequality for quadratic forms (arXiv:2607.24164) suffices to control this averaging at every even degree.