### Abstract

The Nonnegative Matrix Factorization (NMF) problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormously popular in machine learning, where the factorization is computed using a variety of local search heuristics. Vavasis recently proved that this problem is NP-complete. We initiate a study of when this problem is solvable in polynomial time. Consider a nonnegative m x n matrix M and a target inner-dimension r. Our results are the following: 1. We give a polynomial-time algorithm for exact and approximate NMF for every constant r. Indeed NMF is most interesting in applications precisely when r is small. 2. We complement this with a hardness result, that if exact NMF can be solved in time (nm) ^{o(r)}, 3-SAT has a sub-exponential time algorithm. Hence, substantial improvements to the above algorithm are unlikely. 3. We give an algorithm that runs in time polynomial in n, m and r under the separablity condition identified by Donoho and Stodden in 2003. The algorithm may be practical since it is simple and noise tolerant (under benign assumptions). Separability is believed to hold in many practical settings. To the best of our knowledge, this last result is the first polynomial-time algorithm that provably works under a non-trivial condition on the input matrix and we believe that this will be an interesting and important direction for future work.

Original language | English (US) |
---|---|

Title of host publication | STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing |

Pages | 145-161 |

Number of pages | 17 |

DOIs | |

State | Published - Jun 26 2012 |

Event | 44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States Duration: May 19 2012 → May 22 2012 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 44th Annual ACM Symposium on Theory of Computing, STOC '12 |
---|---|

Country | United States |

City | New York, NY |

Period | 5/19/12 → 5/22/12 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- data analysis
- nonnegative matrix factorization
- semi-algebric sets

## Fingerprint Dive into the research topics of 'Computing a nonnegative matrix factorization - Provably'. Together they form a unique fingerprint.

## Cite this

*STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing*(pp. 145-161). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2213994