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. https://resolver.caltech.edu/CaltechAUTHORS:20160401-165447853
![]() |
PDF
- Published Version
See Usage Policy. 360kB |
![]() |
PDF
- Submitted Version
See Usage Policy. 423kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160401-165447853
Abstract
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: |
| ||||||||||||||||||||||||
ORCID: |
| ||||||||||||||||||||||||
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. | ||||||||||||||||||||||||
Funders: |
| ||||||||||||||||||||||||
Series Name: | Advances in Neural Information Processing Systems | ||||||||||||||||||||||||
Issue or Number: | 25 | ||||||||||||||||||||||||
Record Number: | CaltechAUTHORS:20160401-165447853 | ||||||||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20160401-165447853 | ||||||||||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||||||||
ID Code: | 65862 | ||||||||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||||||||
Deposited By: | Kristin Buxton | ||||||||||||||||||||||||
Deposited On: | 03 Apr 2016 13:29 | ||||||||||||||||||||||||
Last Modified: | 03 Oct 2019 09:51 |
Repository Staff Only: item control page