zbMATH — the first resource for mathematics

SVD based initialization: A head start for nonnegative matrix factorization. (English) Zbl 1131.68084
Summary: We describe Nonnegative Double Singular Value Decomposition (NNDSVD), a new method designed to enhance the initialization stage of Nonnegative Matrix Factorization (NMF). NNDSVD can readily be combined with existing NMF algorithms. The basic algorithm contains no randomization and is based on two SVD processes, one approximating the data matrix, the other approximating positive sections of the resulting partial SVD factors utilizing an algebraic property of unit rank matrices. Simple practical variants for NMF with dense factors are described. NNDSVD is also well suited to initialize NMF algorithms with sparse factors. Many numerical examples suggest that NNDSVD leads to rapid reduction of the approximation error of many NMF algorithms.

68T10 Pattern recognition, speech recognition
68U10 Computing methodologies for image processing
Full Text: DOI
[1] Dhillon, I.; Sra, S., Generalized nonnegative matrix approximations with Bregman divergences, (), 283-290
[2] M. Chu, F. Diele, R. Plemmons, S. Ragni, Optimality, computation, and interpretation of nonnegative matrix factorization, unpublished preprint, October 2004.
[3] Ding, C.; Li, T.; Peng, W.; Park, H., Orthogonal nonnegative matrix tri-factorizations for clustering, (), 126-135
[4] Donoho, D.; Stodden, V., When does non-negative matrix factorization give a correct decomposition into parts?, Adv. neural inf. process. syst., 17, (2004)
[5] Eldén, L., Matrix methods in data mining and pattern recognition, (2007), SIAM Philadelphia, PA, USA · Zbl 1120.68092
[6] Hoyer, P., Non-negative sparse coding, (), 557-565
[7] Hoyer, P., Non-negative matrix factorization with sparseness constraints, J. Mach. learn. res., 5, 1457-1469, (2004) · Zbl 1222.68218
[8] Lee, D.D.; Seung, H.S., Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791, (1999) · Zbl 1369.68285
[9] Kim, D.; Sra, S.; Dhillon, I.S., Fast Newton-type methods for the least squares nonnegative matrix approximation problem, (), 343-354
[10] Marinetti, S.; Finesso, L.; Marsilio, E., Matrix factorization methods: application to thermal NDT/E, NDT&E int., 39, 611-616, (2006)
[11] Paatero, P.; Tapper, U., Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values, Environmetrics, 5, 111-126, (1994)
[12] Park, H.; Kim, H., One-sided non-negative matrix factorization and non-negative centroid dimension reduction for text classification, ()
[13] P. Pauca, F. Shahnaz, M. Berry, R. Plemmons, Text mining using non-negative matrix factorizations, in: 4th SIAM Conference on Data Mining, Orlando, FL, SIAM, Philadelphia, April 2004, pp. 452-456.
[14] Sajda, P.; Du, S.; Brown, T.; Stoyanova, R.; Shungu, D.; Mao, X.; Parra, L., Nonnegative matrix factorization for rapid recovery of constituent spectra in magnetic resonance chemical shift imaging of the brain, IEEE trans. med. imaging, 23, 12, 1453-1465, (2004)
[15] Shahnaz, F.; Berry, M.; Pauca, V.; Plemmons, R., Document clustering using nonnegative matrix factorization, Inf. process. manage., 42, 2, 373-386, (2006) · Zbl 1087.68104
[16] Xu, W.; Liu, X.; Gong, Y., Document clustering based on non-negative matrix factorization, (), 267-273
[17] D. Zhang, S. Chen, Z.-H. Zhou, Two-dimensional non-negative matrix factorization for face representation and recognition, in: Proceedings of the ICCV’05 Workshop on Analysis and Modeling of Faces and Gestures (AMFG’05), Lecture Notes in Computer Science, vol. 3723, Springer, Berlin, 2005, pp. 350-363.
[18] A. Cichocki, R. Zdunek, NMFLAB MATLAB toolbox for non-negative matrix factorization. URL: \(\langle\)www.bsp.brain.riken.jp/ICALAB/nmflab.html/⟩. · Zbl 1186.94391
[19] Pascual-Montano, A.; Carmona-Saez, P.; Chagoyen, M.; Tirado, F.; Carazo, J.; Pascual-Marqui, R., Bionmf: a versatile tool for non-negative matrix factorization in biology, BMC bioinformatics, 7, 366, (2006)
[20] Berman, A.; Plemmons, R., Nonnegative matrices in the mathematical sciences, (1994), SIAM Philadelphia · Zbl 0815.15016
[21] Berry, M.W.; Browne, M.; Langville, A.N.; Pauca, V.P.; Plemmons, R.J., Algorithms and applications for approximate nonnegative matrix factorization, Comput. stat. data anal., 52, 1, 155-173, (2007) · Zbl 05560147
[22] Gregory, D.; Pullman, N., Semiring rank: Boolean rank and nonnegative rank factorization, J. combin. inf. system sci., 3, 223-233, (1983) · Zbl 0622.15007
[23] Bertsekas, D., Nonlinear programming, (1999), Athena Scientific Belmont, MA
[24] Salakhutdinov, R.; Roweis, S.; Ghahramani, Z., On the convergence of bound optimization algorithms, (), 509-516
[25] Lee, D.D.; Seung, H.S., Algorithms for non-negative matrix factorizations, Adv. neural inf. process. syst., 13, 556-562, (2001)
[26] W. Liu, J. Yi, Existing and new algorithms for nonnegative matrix factorization, Technical Report, University Texas at Austin, 2003.
[27] M. Aharon, M. Elad, A. Bruckstein, K-SVD and its non-negative variant for dictionary design, in: M. Papadakis, A. Laine, M. Unser (Eds.), Proceedings of the SPIE Conference, Wavelets XI, vol. 5914, 2005, pp. 327-339
[28] V. Pauca, R. Plemmons, M. Giffin, K. Hamada, Unmixing spectral data for sparse low-rank non-negative matrix factorization, in: Proceedings of the Amos Technical Conference Maui, 2004.
[29] Liu, W.; Zheng, N., Learning sparse features for classification by mixture models, Pattern recognition lett., 25, 155-161, (2004)
[30] S. Wild, Seeding non-negative matrix factorizations with the spherical k-means clustering, Master’s Thesis, University of Colorado, Department of Applied Mathematics, 2003.
[31] Wild, S.; Curry, J.; Dougherty, A., Improving non-negative matrix factorizations through structured intitialization, Pattern recognition, 37, 2217-2232, (2004)
[32] Dhillon, I.S.; Modha, D.S., Concept decompositions for large sparse text data using clustering, Mach. learn., 42, 1, 143-175, (2001) · Zbl 0970.68167
[33] Zeimpekis, D.; Gallopoulos, E., CLSI: a flexible approximation scheme from clustered term-document matrices, (), 631-635
[34] Catral, M.; Han, L.; Neumann, M.; Plemmons, R., On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices, Linear algebra appl., 393, 1, 107-126, (2004) · Zbl 1085.15012
[35] Stewart, G.; Sun, J.g., Matrix perturbation theory, (1990), Academic Press Boston
[36] Cohen, J.; Rothblum, U., Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear algebra appl., 190, 149-168, (1993) · Zbl 0784.15001
[37] C. Ding, X. He, H. Simon, On the equivalence of nonnegative matrix factorization and spectral clustering, in: Proceedings of the 5th SIAM International Conference on Data Mining, Philadelphia, 2005, pp. 606-610.
[38] Pauca, V.; Piper, J.; Plemmons, R., Nonnegative matrix factorization for spectral data analysis, Linear algebra appl., 416, 1, 29-47, (2006) · Zbl 1096.65033
[39] Baglama, J.; Calvetti, D.; Reichel, L., IRBL: an implicitly restarted block Lanczos method for large-scale Hermitian eigenproblems, SIAM J. sci. comput., 24, 5, 1650-1677, (2003) · Zbl 1044.65027
[40] Berry, M., Large scale singular value decomposition, Int. J. supercomput. appl., 6, 13-49, (1992)
[41] Golub, G.; Loan, C.V., Matrix computations, (1996), The Johns Hopkins University Press Baltimore
[42] R. Larsen, PROPACK: a software package for the symmetric eigenvalue problem and singular value problems on Lanczos and Lanczos bidiagonalization with partial reorthogonalization. URL: \(\langle\)http://soi.stanford.edu/ rmunk/PROPACK/⟩.
[43] Mathworks MATLAB file exchange, \(\langle\)http://www.mathworks.com/matlabcentral/fileexchange⟩, (accessed 3.1.07).
[44] TMG: A MATLAB Toolbox for generating term-document matrices from text collections, \(\langle\)http://scgroup.hpclab.ceid.upatras.gr/scgroup/Projects/TMG/⟩, (accessed 3.1.07).
[45] CBCL face database # 1 \(\langle\)http://cbcl.mit.edu/cbcl/software-datasets/FaceData2.html⟩, (accessed 3.1.07).
[46] University of Bath Iris image database \(\langle\)http://www.bath.ac.uk/elec-eng/research/sipg/irisweb/sampleiris.htm⟩, (accessed 3.1.07).
[47] K. Heinrich, Automated gene classification using nonnegative matrix factorization on biomedical literature, Ph.D. Thesis, The University of Tennessee, Knoxville, May 2007.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.