  We consider the sparse moment problem of learning a $k$-spike mixture in
high-dimensional space from its noisy moment information in any dimension. We
measure the accuracy of the learned mixtures using transportation distance.
Previous algorithms either assume certain separation assumptions, use more
recovery moments, or run in (super) exponential time. Our algorithm for the
one-dimensional problem (also called the sparse Hausdorff moment problem) is a
robust version of the classic Prony's method, and our contribution mainly lies
in the analysis. We adopt a global and much tighter analysis than previous work
(which analyzes the perturbation of the intermediate results of Prony's
method). A useful technical ingredient is a connection between the linear
system defined by the Vandermonde matrix and the Schur polynomial, which allows
us to provide tight perturbation bound independent of the separation and may be
useful in other contexts. To tackle the high-dimensional problem, we first
solve the two-dimensional problem by extending the one-dimensional algorithm
and analysis to complex numbers. Our algorithm for the high-dimensional case
determines the coordinates of each spike by aligning a 1d projection of the
mixture to a random vector and a set of 2d projections of the mixture. Our
results have applications to learning topic models and Gaussian mixtures,
implying improved sample complexity results or running time over prior work.
