Sparsification for Sums of Exponentials and its Algorithmic Applications
  Many works in signal processing and learning theory operate under the
assumption that the underlying model is simple, e.g. that a signal is
approximately $k$-Fourier-sparse or that a distribution can be approximated by
a mixture model that has at most $k$ components. However the problem of fitting
the parameters of such a model becomes more challenging when the
frequencies/components are too close together.
  In this work we introduce new methods for sparsifying sums of exponentials
and give various algorithmic applications. First we study Fourier-sparse
interpolation without a frequency gap, where Chen et al. gave an algorithm for
finding an $\epsilon$-approximate solution which uses $k' = \mbox{poly}(k, \log
1/\epsilon)$ frequencies. Second, we study learning Gaussian mixture models in
one dimension without a separation condition. Kernel density estimators give an
$\epsilon$-approximation that uses $k' = O(k/\epsilon^2)$ components. These
methods both output models that are much more complex than what we started out
with. We show how to post-process to reduce the number of
frequencies/components down to $k' = \widetilde{O}(k)$, which is optimal up to
logarithmic factors. Moreover we give applications to model selection. In
particular, we give the first algorithms for approximately (and robustly)
determining the number of components in a Gaussian mixture model that work
without a separation condition.
