|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Computing a Nonnegative Matrix Factorization -- Provably | | Sanjeev Arora
; Rong Ge
; Ravi Kannan
; Ankur Moitra
; | | Date: |
3 Nov 2011 | | Abstract: | In the Nonnegative Matrix Factorization (NMF) problem we are given an $n
imes m$ nonnegative matrix $M$ and an integer $r > 0$. Our goal is to express
$M$ as $A W$ where $A$ and $W$ are nonnegative matrices of size $n imes r$
and $r imes m$ respectively. In some applications, it makes sense to ask
instead for the product $AW$ to approximate $M$ -- i.e. (approximately)
minimize $
orm{M - AW}_F$ where $
orm{}_F$ denotes the Frobenius norm; we
refer to this as Approximate NMF. This 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 $A$ and $W$ are
computed using a variety of local search heuristics. Vavasis proved that this
problem is NP-complete. We initiate a study of when this problem is solvable in
polynomial time:
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. This rules
out substantial improvements to the above algorithm.
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 example of a
polynomial-time algorithm that provably works under a non-trivial condition on
the input and we believe that this will be an interesting and important
direction for future work. | | Source: | arXiv, 1111.0952 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER