Abstract | ||
---|---|---|
Let f(x)=p(x)−q(x) be a polynomial with real coefficients whose roots have nonnegative real part, where p and q are polynomials with nonnegative coefficients. In this paper, we prove the following: Given an initial point x0>0, the multiplicative update xt+1=xtp(xt)/q(xt) (t=0,1,…) monotonically and linearly converges to the largest (resp. smallest) real roots of f smaller (resp. larger) than x0 if p(x0)<q(x0) (resp. q(x0)<p(x0)). The motivation to study this algorithm comes from the multiplicative updates proposed in the literature to solve optimization problems with nonnegativity constraints; in particular many variants of nonnegative matrix factorization. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.ipl.2017.11.008 | Information Processing Letters |
Keywords | Field | DocType |
Polynomial root finding,Multiplicative updates,Analysis of algorithms | Monotonic function,Discrete mathematics,Combinatorics,Polynomial root finding,Real roots,Multiplicative function,Polynomial,Analysis of algorithms,Non-negative matrix factorization,Mathematics | Journal |
Volume | ISSN | Citations |
132 | 0020-0190 | 0 |
PageRank | References | Authors |
0.34 | 2 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nicolas Gillis | 1 | 503 | 39.77 |