Sparse Solutions to Nonnegative Linear Systems and Applications by Aditya Bhaskara, Ananda Theertha Suresh, Morteza Zadimoghaddam
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.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment