CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20160401-165447853

[img] PDF - Published Version
See Usage Policy.

360kB
[img] 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:
URLURL TypeDescription
https://papers.nips.cc/paper/4518-factoring-nonnegative-matrices-with-linear-programsOrganizationPaper
https://arxiv.org/abs/1206.1270arXivDiscussion Paper
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1-0723
NSFCCF-1139953
Alfred P. Sloan FoundationUNSPECIFIED
NSFIIS-1054009
Office of Naval Research (ONR)N00014-12-1-0041
American Family InsuranceUNSPECIFIED
GoogleUNSPECIFIED
GreenplumUNSPECIFIED
OracleUNSPECIFIED
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: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