# Efficient Algorithms for Sparse Moment Problems without Separation

arXiv: https://arxiv.org/abs/2207.13008 · HTML: https://mlsanity.com/paper/2207.13008/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 88 references that are in the map.
- First posted on arXiv 26 Jul 2022.

## Builds on (most cited first, 11 of 11)

- [Probabilistic Latent Semantic Analysis](https://mlsanity.com/paper/1301.6705/) (2013)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Solving SDP Faster: A Robust IPM Framework and Efficient Implementation](https://mlsanity.com/paper/2101.08208/) (2021)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Efficiently Learning Mixtures of Mallows Models](https://mlsanity.com/paper/1808.05731/) (2018)
- [Source Identification for Mixtures of Product Distributions](https://mlsanity.com/paper/2012.14540/) (2020)
- [Fast Regression for Structured Inputs](https://mlsanity.com/paper/2203.07557/) (2022)
- [Fourier-sparse interpolation without a frequency gap](https://mlsanity.com/paper/1609.01361/) (2016)
- [The Sparse Hausdorff Moment Problem, with Application to Topic Models](https://mlsanity.com/paper/2007.08101/) (2020)
- [Super-Resolution Off the Grid](https://mlsanity.com/paper/1509.07943/) (2015)
- [Learning Arbitrary Statistical Mixtures of Discrete Distributions](https://mlsanity.com/paper/1504.02526/) (2015)

## Built on by (most cited first, 3 of 3)

- [Identifiability of Product of Experts Models](https://mlsanity.com/paper/2310.09397/) (2023)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Multidimensional unstructured sparse recovery via eigenmatrix](https://mlsanity.com/paper/2402.17215/) (2024)

## Abstract (arXiv)

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.