A Caltech Library Service

Factoring nonnegative matrices with linear programs

Bittorf, Victor and Recht, Benjamin and Ré, Christopher and Tropp, Joel A. (2012) Factoring nonnegative matrices with linear programs. In: Advances in Neural Information Processing Systems 25 (NIPS 2012). Advances in Neural Information Processing Systems. No.25. Neural Information Processing Systems , La Jolla, CA. ISBN 978-1-62748-003-1.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper describes a new approach, based on linear programming, for computing nonnegative matrix factorizations (NMFs). The key idea is a data-driven model for the factorization where 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 ≈ CX and some linear constraints. The constraints are chosen to ensure that the matrix C selects features; these features can then be used to find a low-rank NMF of X. A theoretical analysis demonstrates that this approach has guarantees similar to those of the recent NMF algorithm of Arora et al. (2012). In contrast with this earlier work, the proposed method extends to more general noise models and 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 can factor a multigigabyte matrix in a matter of minutes.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Tropp, Joel A.0000-0003-1024-1791
Additional Information:©2012 by Neural Information Processing Systems. The authors would like to thank Sanjeev Arora, Michael Ferris, Rong Ge, Nicolas Gillis, Ankur Moitra, and Stephen Wright for helpful suggestions. BR is generously supported by ONR award N00014-11-1-0723, NSF award CCF-1139953, and a Sloan Research Fellowship. CR is generously supported by NSF CAREER award under IIS-1054009, ONR award N000141210041, and gifts or research awards from American Family Insurance, Google, Greenplum, and Oracle. JAT is generously supported by ONR award N00014-11-1002, AFOSR award FA9550-09-1-0643, and a Sloan Research Fellowship.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1-0723
Alfred P. Sloan FoundationUNSPECIFIED
Office of Naval Research (ONR)N00014-12-1-0041
American Family InsuranceUNSPECIFIED
Office of Naval Research (ONR)N00014-11-1002
Air Force Office of Scientific Research (AFOSR)FA9550-09-1-0643
Series Name:Advances in Neural Information Processing Systems
Issue or Number:25
Record Number:CaltechAUTHORS:20160401-165447853
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65862
Deposited By: Kristin Buxton
Deposited On:03 Apr 2016 13:29
Last Modified:03 Oct 2019 09:51

Repository Staff Only: item control page