×

Convergence analysis of a non-negative matrix factorization algorithm based on Gibbs random field modeling. (English) Zbl 1297.65047

Summary: Non-negative matrix factorization (NMF) is a new approach to deal with the multivariate nonnegative data. Although the classic multiplicative update algorithm can solve the NMF problems, it fails to find sparse and localized object parts. Then a Gibbs random field (GRF) modeling based NMF algorithm, called the GRF-NMF algorithm, try to directly model the prior object structure of the components into the NMF problem. In this paper, the convergence of the GRF-NMF algorithm and its advantages are investigated. Based on a classic model, the equilibrium points are obtained. Some invariant sets are constructed to prepare for the analysis of the convergence of the GRF-NMF algorithm. Then using stability theory of the equilibrium point, the convergence of the algorithm is proved and the convergence conditions of the algorithm are obtained. We theoretically present the advantages of the GRF-NMF algorithm in the end.

MSC:

65F30 Other matrix algorithms (MSC2010)
62M40 Random fields; image analysis
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lee, D.D., Seung, H.S.: Learning the parts of objects by non-negative matrix factorization. Nature 401, 788–791 (1999) · Zbl 1369.68285 · doi:10.1038/44565
[2] Paatero, P., Tapper, U.: Positive matrix factorization: a non-negative factor model with optimal utilization of error. Environmetrics 5, 111–126 (1994) · doi:10.1002/env.3170050203
[3] Chu, M., Diele, F., Plemmons, R., Ragni, S.: Optimality, computation, and interpretation of nonnegative matrix factorizations. Unpublished report (2004)
[4] Kim, P.M., Tidor, B.: Subsystem identification through dimensionality reduction of large-scale gene expression data. Genome Res. 13, 1706–1718 (2003) · doi:10.1101/gr.903503
[5] Pauca, V.P., Piper, J., Plemmons, R.J.: Nonnegative matrix factorization for spectral data analysis. Linear Algebra Appl. 416, 29–47 (2006) · Zbl 1096.65033 · doi:10.1016/j.laa.2005.06.025
[6] Cichocki, A., Zdunek, R., Amari, S.: New algorithms for non-negative matrix factorization in applications to blind source separation. In: ICASSP, pp. 621–625 (2006) · Zbl 1178.94057
[7] Gao, Y., Church, G.: Improving molecular cancer class discovery through sparse non-negative matrix factorization. Bioinformatics 21, 3970–3975 (2005) · doi:10.1093/bioinformatics/bti653
[8] Saul, L.K., Sha, F., Lee, D.D.: Statistical signal processing with nonnegativity constraints. In: Proceedings of EuroSpeech, vol. 2, pp. 1001–1004 (2003)
[9] Shahnaz, F., Berry, M.W., Pauca, V.P., Plemmons, R.: Document clustering using nonnegative matrix factorization. Inf. Process. Manag. 42, 373–386 (2006) · Zbl 1087.68104 · doi:10.1016/j.ipm.2004.11.005
[10] Sha, F., Saul, L.K.: Real-time pitch determination of one or more voices by nonnegative matrix factorization. University of Pennsylvania Scholarly Commons, Departmental Papers (CIS) (2004)
[11] Smaragdis, P., Brown, J.C.: Non-negative matrix factorization for polyphonic music transcription. In: Proceedings of IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, pp. 177–180 (2003)
[12] Kim, H., Park, H.: Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares. In: Proceedings of the IASTED International Conference on Computational and Systems Biology (CASB2006), pp. 95–100 (2006)
[13] Brunet, J.P., Tamayo, P., Golub, T.R., Mesirov, J.P.: Metagenes and molecular pattern discovery using matrix factorization. Proc. Natl. Acad. Sci. USA 101, 4164–4169 (2004) · doi:10.1073/pnas.0308531101
[14] Berry, M., Browne, M., Langville, A., Pauca, P., Plemmons, R.: Algorithms and applications for approximate nonnegative matrix factorization. Comput. Stat. Data Anal. 52, 155–173 (2006) · Zbl 1452.90298 · doi:10.1016/j.csda.2006.11.006
[15] Lin, C.J.: Projected gradient methods for non-negative matrix factorization. In: Tech. Report Information and Support Service ISSTECH, pp. 95–113 (2005)
[16] Hoyer, P.O., Dayan, P.: Non-negative matrix factorization with sparseness constraints. J. Mach. Learn. Res. 5, 1457–1469 (2004) · Zbl 1222.68218
[17] Li, S.Z., Hou, X.W., Zhang, H.J.: Learning spatially localized, parts-based representation. In: Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Hawaii, pp. 11–13 (2001)
[18] Liao, S., Lei, Z., Li, S.Z.: Nonnegative matrix factorization with Gibbs random field modeling. In: IEEE 12th International Conference on Computer Vision Workshops. ICCV Workshops (2009)
[19] Cichocki, A., Zdunek, R.: Multilayer non-negative matrix factorization using project gradient approaches. Int. J. Neural Syst. 17, 431–446 (2007) · doi:10.1142/S0129065707001275
[20] Salakhutdinov, R., Roweis, S.T., Ghahramani, Z.: The convergence of bound optimization algorithms. In: 19th International Conference on Uncertainty in Artificial Intelligence (2003)
[21] Lin, C.J.: On the convergence of multiplicative update algorithms for nonnegative matrix factorization. Trans. Neural Netw. 18(6), 1589–1596 (2007) · doi:10.1109/TNN.2007.891185
[22] Kocic, V.L., Ladas, G.: Global Behavior of Nonlinear Difference Equations of Higher Order. Kluwer Academic, Dordrecht (1953) · Zbl 0787.39001
[23] Yang, S.M., Yi, Z.: Convergence analysis of non-negative matrix factorization for BSS algorithm. Neural Process. Lett. 31, 45–64 (2010) · Zbl 05802915 · doi:10.1007/s11063-009-9126-0
[24] Hale, J.K.: Theory of Functional Differential Equations. Springer, New York (1977) · Zbl 0352.34001
[25] Dai, J., Meyn, S.: Stability and convergence of moments for multiclass queueing networks via fluid limit models. Trans. Autom. Control 40(11), 1889–1904 (1995) · Zbl 0836.90074 · doi:10.1109/9.471210
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.