Convergence multiplicative update

However, the global convergence of these updates is not formally guaranteed because they are not defined for all pairs of nonnegative matrices. In this paper, we consider slightly modified versions of the original multiplicative updates and study their global convergence properties. The only difference between the modified updates and the original ones is that the former do not allow variables to take values less than a user-specified positive constant.

Furthermore, we propose algorithms based on the modified updates that always stop within a finite number of iterations. This is a preview of subscription content, access via your institution.

Rent this article via DeepDyve. The conditions 7 — 12 are derived by eliminating Lagrange multipliers in the original KKT conditions. The conditions 19 — 24 are derived by eliminating Lagrange multipliers in the original KKT conditions.

Badeau, R. IEEE Trans. Neural Netw. Article Google Scholar. Berry, M. Theory 11 , — Data Anal. Boyd, S. Cambridge University Press, Cambridge Brunet, J. USA 12 , — Cai, D. Vavasis, S. Wang, R. Neurocomputing 72 , — Wang, Y. Data Eng. Wu, C. Xu, W. Yamauchi, S. Yang, Z. Zangwill, W. Prentice-Hall, Englewood Cliffs Zhao, R.

Download references. You can also search for this author in PubMed Google Scholar. Correspondence to Norikazu Takahashi. Part of this paper was presented in International Symposium on Nonlinear Theory and its Applications [ 34 , 37 ].

In the unified method of Yang and Oja [ 45 ], an auxiliary function is systematically derived from a given generalized polynomial by using three rules. They are described by the following lemmas. In either case, it is easy to see that the following statements hold true:. In either case, we easily see that the following statements hold true:.

We derive an auxiliary function for Kullback—Leibler divergence with the regularization term by using the unified method of Yang and Oja. First of all, we rewrite the error function by using 33 as follows:. Applying Lemmas 8 and 9 to these functions, we have the following auxiliary functions:. By simple mathematical manipulations, we have the following inequalities:.

Reprints and Permissions. A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization. Comput Optim Appl 71, — Download citation. Received : 10 April View full fingerprint. Computational Optimization and Applications , 57 2 , In: Computational Optimization and Applications , Vol.

Takahashi N , Hibi R. Computational Optimization and Applications. Takahashi, Norikazu ; Hibi, Ryota. Clearly, this framework cannot be directly used here because of the following two difficulties.

This procedure is not well defined if denominators in 3 or 1 Though Theorem 1 proves that and , it is 4 are zero. Moreover, the initial point is a concern; some use unclear if and or not. Hence, in 8 , an positive matrices, but some merely consider nonnegative ones. Theorem 1 [5, Th. This and and , , then KKT condition is due to nonnegative constraints. The pre- vious framework does not reveal how to have this result.

However, Lin [5] We hope that any limit point of is stationary stated that due to possible numerical inaccuracy, a mathemat- as a local minimum must be a stationary point. By defi- ical example is desired before drawing conclusions.

Thus, the nition is a stationary point of 1 if it satisfies the convergence issue remains open. For all , , , and Then, any limit point is stationary. Computational complexity is another concern as we hope that our modifications are not more time consuming.

Here, we analyze the cost of Algorithm 1. Lin [5] indicated that in 3 one should calculate but not 5 as. Hence, the main cost is on calculating and in 3 and 4 , each of which takes where operations. Therefore, the complexity of Algorithm 1 is 6 iterations are, respectively, partial derivatives to elements in and. Some implementations of the multiplicative updates nor- Lee and Seung [4] proved the following properties. This normalization does not change the function value as for any for any positive diagonal matrix ,.

We will consider this operation in our proposed algorithm. Similarly, the second inequality Lee and Seung [4] mentioned that the two update rules 3 is strict under conditions on. For updating All are less than , so the complexity per iteration re- mains the same. The use of follows from some NMF papers e. This is also related to penalty terms added to the objec- tive function. We discuss this aspect in more detail in Section VI. The new algorithm is well defined without requiring any con- is referred to as the step size.

The two difficulties raised in dition on. One could even start from only nonnegative ma- Section II can be reinterpreted as follows. Theorem 2: If and , , then 2 If , numerator of the step size is zero, and the gradient , is not changed. Hence, and 15 one cannot use the strategy 8 for proving fixed-point convergence. Moreover, if and , , then Therefore, we propose modifying the step size to and Proof: When , 15 holds by the assumption of this theorem.

Using induction, we assume results are correct at. Similarly, We then consider the following two situations: we can define.

The modified algorithm is as the following. Case 1 If , then using 16 Algorithm 2: A modified algorithm for minimizing 1 1 Given and. Initialize , for all , , , and. Case 2 If , then according to 12 2 For a If is stationary, stop. If the whole column is zero, then this as well as the corresponding row in are unchanged.

After normalization,. The proof of is similar. If and , , then the proof is the We denote and as intermediate matrices before same. Following [9], we impose the normalization op- eration in order to prove that is in a bounded set see Theorem 8.

In contrast, 2 calculate or ; elements satisfying KKT conditions remain the same. When 3 add. Hence, it is and sufficient to consider any column and discuss the function 28 19 Further, the following three properties are equivalent: where is the corresponding column in and. Here, 1 both inequalities in 28 are strict; both and are treated as constants.