Sparse Solutions to Nonnegative Linear Systems and Applications
  We give an efficient algorithm for finding sparse approximate solutions to
linear systems of equations with nonnegative coefficients. Unlike most known
results for sparse recovery, we do not require {\em any} assumption on the
matrix other than non-negativity. Our algorithm is combinatorial in nature,
inspired by techniques for the set cover problem, as well as the multiplicative
weight update method.
  We then present a natural application to learning mixture models in the PAC
framework. For learning a mixture of $k$ axis-aligned Gaussians in $d$
dimensions, we give an algorithm that outputs a mixture of $O(k/\epsilon^3)$
Gaussians that is $\epsilon$-close in statistical distance to the true
distribution, without any separation assumptions. The time and sample
complexity is roughly $O(kd/\epsilon^3)^{d}$. This is polynomial when $d$ is
constant -- precisely the regime in which known methods fail to identify the
components efficiently.
  Given that non-negativity is a natural assumption, we believe that our result
may find use in other settings in which we wish to approximately explain data
using a small number of a (large) candidate set of components.
