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\mathrm{/}{ϵ}^3)$ Gaussians that is $ϵ$-close in statistical distance to the true distribution, without any separation assumptions. The time and sample complexity is roughly $O(kd\mathrm{/}{ϵ}^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.