Convergence Analysis of an Alternative Gradient Algorithm for Non-Negative Matrix Factorization
Non-negative matrix factorization (NMF) is a useful computational method to find basis information of multivariate nonnegative data. A popular approach to solve the NMF problem is the multiplicative update (MU) algorithm. But, it has some defects. So the columnwisely alternating gradient (cAG) algorithm was proposed. In this paper, we analyze convergence of the cAG algorithm and show advantages over the MU algorithm. The stability of the equilibrium point is used to prove the convergence of the cAG algorithm. A classic model is used to obtain the equilibrium point and the invariant sets are constructed to guarantee the integrity of the stability. Finally, the convergence conditions of the cAG algorithm are obtained, which help reducing the evaluation time and is confirmed in the experiments. By using the same method, the MU algorithm has zero divisor and is convergent at zero has been verified. In addition, the convergence conditions of the MU algorithm at zero are similar to that of the cAG algorithm at non-zero. However, it is meaningless to discuss the convergence at zero, which is not always the result that we want for NMF. Thus, we theoretically illustrate the advantages of the cAG algorithm.
[1] D.D. Lee, H.S. Seung, Learning the parts of objects by non-negative
matrix factorization, Nature 401 (6755) (1999) 788-791.
[2] E. F. Gonzales, Y. Zhang, Accelerating the Lee-Seung algorithm for nonnegative
matrix factorization, Dept. Comput. Appl. Math., Rice Univ.,
Houston, TX, Tech. Rep. (2005).
[3] M. Berry, M. Browne, A. Langville, P. Pauca, R. Plemmons, Algorithms
and applications for approximate nonnegative matrix factorization,
Computational Statistics and Data Analysis 52 (2006) 155-173.
[4] P. Paatero, U. Tapper, Positive matrix factorization: a non-negative
factor model with optimal utilization of error estimates of data values,
Environmetrics, 5 (1994) 111-126.
[5] M. Chu, F. Diele, R. Plemmons, S. Ragni, Optimality, computation, and
interpretation of nonnegative matrix factorizations, unpublished report
(2004).
[6] P. Paatero and U. Tapper, Positive matrix factorization: A non-negative
factor model with optimal utilization of error, Environmetrics, 5 (1994)
111-126.
[7] L.K. Saul, F. Sha, D.D. Lee, Statistical signal processing with
nonnegativity constraints, Proceedings of EuroSpeech 2 (2003) 1001-
1004.
[8] F. Shahnaz, M.W. Berry, V.P. Pauca, R. Plemmons, Document clusting
using nonnegative matrix factorization, Information Processing and
Management 42 (2006) 373-386.
[9] P.M. Kim, B. Tidor, Subsystem identification through dimensionality
reduction of large-scale gene expression data Genome Research, 13
(2003) 1706C1718.
[10] V.P. Pauca, J. Piper, R.J. Plemmons, Nonnegative matrix factorization for
spectral data analysis, Linear Algebra and its Applications 416 (2006)
29-47.
[11] F. Sha, L.K. Saul, Real-time pitch determination of one or more voices
by nonnegative matrix factorization, Advances in Neural Information
Processing Systems (2005). online papers.
[12] P. Smaragdis, J.C. Brown, Non-negative matrix factorization for
polyphonic music transcription, in: Proceedings of IEEE Workshop on
Applications of Signal Processing to Audio and Acoustics (2003) 177-
180.
[13] L. Lu, Alternative gradient algorithms with applications to nonnegative
matrix factorizations, Applied Mathematics and Computation 216
(2010) 1763-1770.
[14] A. Cichocki, R. Zdunek, S. Amari, New algorithms for non-negative
matrix factorization in applications to blind source separation, ICASSP
2006, Toulouse, France, 621-625.
[15] C.J. LIN, Projected gradient methods for non-negative matrix
factorization, Tech. Report Information and Support Service ISSTECH-
95-013 (2005).
[16] S.M. Yang, Z. Yi, Convergence analysis of non-negative matrix
factorization for BSS algorithm, Neural Process Lett (2010) 45-64.
[17] A. Cichocki, R. Zdunek, Multilayer non-negative matrix factorization
using project gradient approaches, International Journal of Neural
Systems (2007) 431-446.
[18] R. Salakhutdinov, S.T. Roweis, Z. Ghahramani, The convergence of
bound optimization algorithms, In: The 19th International Conference
on Uncertainty in Artificial Intelligence, (2003).
[19] C.J. Lin, On the convergence of multiplicative update algorithms for
nonnegative matrix factorization, Transactions on Neural Networks
(2007) 18.
[20] V.L. Kocic, G. Ladas, Global behavior of nonlinear difference equations
of higher order, Kluwer Academic Publishers (1953).
[21] J.K. Hale, Theory of functional differential equations, Springer,
Heidelberg, New York (1977).
[22] J. Dai, S. Meyn, Stabilitity and convergence of moments for multiclass
queueing networks via fluid limit models, Translation on Automatic
Control (1995) 1889-1904.
[1] D.D. Lee, H.S. Seung, Learning the parts of objects by non-negative
matrix factorization, Nature 401 (6755) (1999) 788-791.
[2] E. F. Gonzales, Y. Zhang, Accelerating the Lee-Seung algorithm for nonnegative
matrix factorization, Dept. Comput. Appl. Math., Rice Univ.,
Houston, TX, Tech. Rep. (2005).
[3] M. Berry, M. Browne, A. Langville, P. Pauca, R. Plemmons, Algorithms
and applications for approximate nonnegative matrix factorization,
Computational Statistics and Data Analysis 52 (2006) 155-173.
[4] P. Paatero, U. Tapper, Positive matrix factorization: a non-negative
factor model with optimal utilization of error estimates of data values,
Environmetrics, 5 (1994) 111-126.
[5] M. Chu, F. Diele, R. Plemmons, S. Ragni, Optimality, computation, and
interpretation of nonnegative matrix factorizations, unpublished report
(2004).
[6] P. Paatero and U. Tapper, Positive matrix factorization: A non-negative
factor model with optimal utilization of error, Environmetrics, 5 (1994)
111-126.
[7] L.K. Saul, F. Sha, D.D. Lee, Statistical signal processing with
nonnegativity constraints, Proceedings of EuroSpeech 2 (2003) 1001-
1004.
[8] F. Shahnaz, M.W. Berry, V.P. Pauca, R. Plemmons, Document clusting
using nonnegative matrix factorization, Information Processing and
Management 42 (2006) 373-386.
[9] P.M. Kim, B. Tidor, Subsystem identification through dimensionality
reduction of large-scale gene expression data Genome Research, 13
(2003) 1706C1718.
[10] V.P. Pauca, J. Piper, R.J. Plemmons, Nonnegative matrix factorization for
spectral data analysis, Linear Algebra and its Applications 416 (2006)
29-47.
[11] F. Sha, L.K. Saul, Real-time pitch determination of one or more voices
by nonnegative matrix factorization, Advances in Neural Information
Processing Systems (2005). online papers.
[12] P. Smaragdis, J.C. Brown, Non-negative matrix factorization for
polyphonic music transcription, in: Proceedings of IEEE Workshop on
Applications of Signal Processing to Audio and Acoustics (2003) 177-
180.
[13] L. Lu, Alternative gradient algorithms with applications to nonnegative
matrix factorizations, Applied Mathematics and Computation 216
(2010) 1763-1770.
[14] A. Cichocki, R. Zdunek, S. Amari, New algorithms for non-negative
matrix factorization in applications to blind source separation, ICASSP
2006, Toulouse, France, 621-625.
[15] C.J. LIN, Projected gradient methods for non-negative matrix
factorization, Tech. Report Information and Support Service ISSTECH-
95-013 (2005).
[16] S.M. Yang, Z. Yi, Convergence analysis of non-negative matrix
factorization for BSS algorithm, Neural Process Lett (2010) 45-64.
[17] A. Cichocki, R. Zdunek, Multilayer non-negative matrix factorization
using project gradient approaches, International Journal of Neural
Systems (2007) 431-446.
[18] R. Salakhutdinov, S.T. Roweis, Z. Ghahramani, The convergence of
bound optimization algorithms, In: The 19th International Conference
on Uncertainty in Artificial Intelligence, (2003).
[19] C.J. Lin, On the convergence of multiplicative update algorithms for
nonnegative matrix factorization, Transactions on Neural Networks
(2007) 18.
[20] V.L. Kocic, G. Ladas, Global behavior of nonlinear difference equations
of higher order, Kluwer Academic Publishers (1953).
[21] J.K. Hale, Theory of functional differential equations, Springer,
Heidelberg, New York (1977).
[22] J. Dai, S. Meyn, Stabilitity and convergence of moments for multiclass
queueing networks via fluid limit models, Translation on Automatic
Control (1995) 1889-1904.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:66731", author = "Chenxue Yang and Mao Ye and Zijian Liu and Tao Li and Jiao Bao", title = "Convergence Analysis of an Alternative Gradient Algorithm for Non-Negative Matrix Factorization", abstract = "Non-negative matrix factorization (NMF) is a useful computational method to find basis information of multivariate nonnegative data. A popular approach to solve the NMF problem is the multiplicative update (MU) algorithm. But, it has some defects. So the columnwisely alternating gradient (cAG) algorithm was proposed. In this paper, we analyze convergence of the cAG algorithm and show advantages over the MU algorithm. The stability of the equilibrium point is used to prove the convergence of the cAG algorithm. A classic model is used to obtain the equilibrium point and the invariant sets are constructed to guarantee the integrity of the stability. Finally, the convergence conditions of the cAG algorithm are obtained, which help reducing the evaluation time and is confirmed in the experiments. By using the same method, the MU algorithm has zero divisor and is convergent at zero has been verified. In addition, the convergence conditions of the MU algorithm at zero are similar to that of the cAG algorithm at non-zero. However, it is meaningless to discuss the convergence at zero, which is not always the result that we want for NMF. Thus, we theoretically illustrate the advantages of the cAG algorithm.
", keywords = "Non-negative matrix factorizations, convergence, cAG
algorithm, equilibrium point, stability.", volume = "8", number = "1", pages = "208-10", }
