  


Factoring nonnegative matrices with linear programs
Victor Bittorf(bittorfcs.wisc.edu) Abstract: This paper describes a new approach for computing nonnegative matrix factorizations (NMFs) with linear programming. The key idea is a datadriven model for the factorization, in which the most salient features in the data are used to express the remaining features. More precisely, given a data matrix X, the algorithm identifies a matrix C that satisfies X is approximately equal to CX and some linear constraints. The matrix C selects features, which are then used to compute a lowrank NMF of X. A theoretical analysis demonstrates that this approach has the same type of guarantees as the recent NMF algorithm of Arora et al. (2012). In contrast with this earlier work, the proposed method (1) has better noise tolerance, (2) extends to more general noise models, and (3) leads to efficient, scalable algorithms. Experiments with synthetic and real datasets provide evidence that the new approach is also superior in practice. An optimized C++ implementation of the new algorithm can factor a multiGigabyte matrix in a matter of minutes. Keywords: Nonnegative Matrix Factorization, Linear Programming, Stochastic gradient descent, Machine learning, Parallel computing, Multicore Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Applications  Science and Engineering (DataMining ) Citation: Download: [PDF] Entry Submitted: 06/06/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  