Sparse Solutions to Nonnegative Linear Systems and Applications
This addresses the problem of learning mixture models without separation assumptions for researchers in machine learning, offering a novel approach but with incremental improvements in specific settings.
The paper presents an efficient combinatorial algorithm for finding sparse approximate solutions to nonnegative linear systems without requiring assumptions on the matrix, and applies it to learning mixture models, achieving an algorithm that outputs a mixture of O(k/ε^3) Gaussians ε-close to the true distribution with polynomial time and sample complexity for constant dimensions.
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/ε^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/ε^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.