×

Algorithms and applications for approximate nonnegative matrix factorization. (English) Zbl 1452.90298

Summary: The development and use of low-rank approximate nonnegative matrix factorization (NMF) algorithms for feature extraction and identification in the fields of text mining and spectral data analysis are presented. The evolution and convergence properties of hybrid methods based on both sparsity and smoothness constraints for the resulting nonnegative matrix factors are discussed. The interpretability of NMF outputs in specific contexts are provided along with opportunities for future work in the modification of NMF algorithms for large-scale and time-varying data sets.

MSC:

90C30 Nonlinear programming
15A23 Factorization of matrices
65K05 Numerical mathematical programming methods
62-08 Computational methods for problems pertaining to statistics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berman, A.; Plemmons, R., Non-Negative Matrices in the Mathematical Sciences (1994), SIAM Press Classics Series: SIAM Press Classics Series Philadelphia, PA
[2] Berman, G., Lattice approximations to the minima of functions of several variables, J. Assoc. Comput. Mach., 16, 286-294 (1969) · Zbl 0176.46402
[3] Berry, M.; Browne, M., Email surveillance using nonnegative matrix factorization, Comput. Math. Organization Theory, 11, 249-264 (2005) · Zbl 1086.68502
[4] Berry, M.; Browne, M., Understanding Search Engines: Mathematical Modeling and Text Retrieval (2005), SIAM: SIAM Philadelphia, PA · Zbl 1075.68591
[5] Bertsekas, D., Nonlinear Programming (1999), Athena Scientific: Athena Scientific Belmont, MA · Zbl 0935.90037
[6] Boutsidis, C., Gallopoulos, E., 2005. On SVD-based initialization for nonnegative matrix factorization. Technical Report HPCLAB-SCG-6/08-05, University of Patras, Patras, Greece.; Boutsidis, C., Gallopoulos, E., 2005. On SVD-based initialization for nonnegative matrix factorization. Technical Report HPCLAB-SCG-6/08-05, University of Patras, Patras, Greece. · Zbl 1131.68084
[7] British National Corpus (BNC), \(2004. \langle;\) http://www.natcorp.ox.ac.uk \(\rangle;\); British National Corpus (BNC), \(2004. \langle;\) http://www.natcorp.ox.ac.uk \(\rangle;\)
[8] Bro, R.; de Jong, S., A fast non-negativity constrained linear least squares algorithm, J. Chemometrics, 11, 393-401 (1997)
[9] Catral, M.; Han, L.; Neumann, M.; Plemmons, R., On reduced rank non-negative factorization for symmetric non-negative matrices, Linear Algebra Appl., 393, 107-126 (2004) · Zbl 1085.15012
[10] Cea, J., Optimisation: Theorie et algorithmes (1971), Dunod: Dunod Paris · Zbl 0211.17402
[11] Chang, C.-I., An information theoretic-based approach to spectral variability, similarity, and discriminability for hyperspectral image analysis, IEEE Trans. Inform. Theory, 46, 1927-1932 (2000) · Zbl 1006.94010
[12] Chen, Z., Cichocki, A., 2005. Nonnegative matrix factorization with temporal smoothness and/or spatial decorrelation constraints, preprint.; Chen, Z., Cichocki, A., 2005. Nonnegative matrix factorization with temporal smoothness and/or spatial decorrelation constraints, preprint.
[13] Chu, M., Diele, F., Plemmons, R., Ragni, S., 2004. Optimality, computation, and interpretations of nonnegative matrix factorizations, available at \(\langle;\) http://www.wfu.edu/\( \sim;\rangle;\); Chu, M., Diele, F., Plemmons, R., Ragni, S., 2004. Optimality, computation, and interpretations of nonnegative matrix factorizations, available at \(\langle;\) http://www.wfu.edu/\( \sim;\rangle;\)
[14] Cichocki, A., Zdunek, R., 2006. NMFLAB for Signal Processing, available at \(\langle;\) http://www.bsp.brain.riken.jp/ICALAB/nmflab.html \(\rangle;\); Cichocki, A., Zdunek, R., 2006. NMFLAB for Signal Processing, available at \(\langle;\) http://www.bsp.brain.riken.jp/ICALAB/nmflab.html \(\rangle;\)
[15] Cichocki, A., Zdunek, R., Amari, S., 2006. Csiszar’s divergences for non-negative matrix factorization: family of new algorithms. In: Proceedings of the Sixth International Conference on Independent Component Analysis and Blind Signal Separation, Charleston, SC, March 5-8.; Cichocki, A., Zdunek, R., Amari, S., 2006. Csiszar’s divergences for non-negative matrix factorization: family of new algorithms. In: Proceedings of the Sixth International Conference on Independent Component Analysis and Blind Signal Separation, Charleston, SC, March 5-8. · Zbl 1178.94057
[16] de Leeuw, J.; Young, F.; Takane, Y., Additive structure in qualitative data: an alternating least squares method with optimal scaling features, Psychometrika, 41, 471-503 (1976) · Zbl 0351.92031
[17] Dhillon, I., Sra, S., 2005. Generalized nonnegative matrix approximations with bregman divergences. In: Proceeding of the Neural Information Processing Systems (NIPS) Conference, Vancouver, BC.; Dhillon, I., Sra, S., 2005. Generalized nonnegative matrix approximations with bregman divergences. In: Proceeding of the Neural Information Processing Systems (NIPS) Conference, Vancouver, BC.
[18] Ding, C., He, X., Simon, H., 2005. On the equivalence of nonnegative matrix factorization and spectral clustering. In: Proceedings of the Fifth SIAM International Conference on Data Mining, Newport Beach, CA.; Ding, C., He, X., Simon, H., 2005. On the equivalence of nonnegative matrix factorization and spectral clustering. In: Proceedings of the Fifth SIAM International Conference on Data Mining, Newport Beach, CA.
[19] Donoho, D., Stodden, V., 2003. When does non-negative matrix factorization give a correct decomposition into parts? In: Seventeenth Annual Conference on Neural Information Processing Systems.; Donoho, D., Stodden, V., 2003. When does non-negative matrix factorization give a correct decomposition into parts? In: Seventeenth Annual Conference on Neural Information Processing Systems.
[20] Drineas, P.; Kannan, R.; Mahoney, M., Fast Monte Carlo algorithms for matrices iii: computing a compressed approximate matrix decomposition, SIAM J. Comput., 36, 1, 132-157 (2006) · Zbl 1111.68147
[21] Finesso, L., Spreij, P., 2004. Approximate nonnegative matrix factorization via alternating minimization. In: Proceedings of the 16th International Symposium on Mathematical Theory of Networks and Systems, Leuven, Belgium, July 5-9.; Finesso, L., Spreij, P., 2004. Approximate nonnegative matrix factorization via alternating minimization. In: Proceedings of the 16th International Symposium on Mathematical Theory of Networks and Systems, Leuven, Belgium, July 5-9.
[22] Gill, P.; Murray, W.; Wright, M., Practical Optimization (1981), Academic Press: Academic Press London
[23] Gonzalez, E., Zhang, Y., 2005. Accelerating the Lee-Seung algorithm for nonnegative matrix factorization. Technical Report TR-05-02, Rice University.; Gonzalez, E., Zhang, Y., 2005. Accelerating the Lee-Seung algorithm for nonnegative matrix factorization. Technical Report TR-05-02, Rice University.
[24] Grieve, T., 2003. The Decline and Fall of the Enron Empire. Slate \(\langle;\) http://www.salon.com/news/feature/2003/10/14/enron/index_np.html \(\rangle;\); Grieve, T., 2003. The Decline and Fall of the Enron Empire. Slate \(\langle;\) http://www.salon.com/news/feature/2003/10/14/enron/index_np.html \(\rangle;\)
[25] Grippo, L.; Sciandrone, M., On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Oper. Res. Lett., 26, 3, 127-136 (2000) · Zbl 0955.90128
[26] Guillamet, D., Bressan, M., Vitria, J., 2001. A weighted non-negative matrix factorization for local representations. In: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, Kavai, HI, pp. 942-947.; Guillamet, D., Bressan, M., Vitria, J., 2001. A weighted non-negative matrix factorization for local representations. In: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, Kavai, HI, pp. 942-947.
[27] Hamza, A. B.; Brady, D., Reconstruction of reflectance spectra using robust non-negative matrix factorization, IEEE Transactions on Signal Processing, 54, 9, 3637-3642 (2006) · Zbl 1375.94068
[28] Hoyer, P., 2002. Non-negative sparse coding. In: Proceedings of the IEEE Workshop on Neural Networks for Signal Processing. Martigny, Switzerland.; Hoyer, P., 2002. Non-negative sparse coding. In: Proceedings of the IEEE Workshop on Neural Networks for Signal Processing. Martigny, Switzerland.
[29] Hoyer, P., Non-negative matrix factorization with sparseness constraints, J. Mach. Learning Res., 5, 1457-1469 (2004) · Zbl 1222.68218
[30] Karvanen, J., Cichocki, A., 2003. Measuring sparseness of noisy signals. In: Proceedings of the Fourth International Symposium on Independent Component Analysis and Blind Signal Separation (ICA2003), Nara, Japan.; Karvanen, J., Cichocki, A., 2003. Measuring sparseness of noisy signals. In: Proceedings of the Fourth International Symposium on Independent Component Analysis and Blind Signal Separation (ICA2003), Nara, Japan.
[31] Keila, P., Skillicorn, D., 2005. Detecting unusual and deceptive communication in email. Technical Report, School of Computing, Queen’s University, Kingston, Ont., Canada.; Keila, P., Skillicorn, D., 2005. Detecting unusual and deceptive communication in email. Technical Report, School of Computing, Queen’s University, Kingston, Ont., Canada. · Zbl 1086.68505
[32] Keshava, N., A survey of spectral unmixing algorithms, Lincoln Laboratory J., 14, 1, 55-77 (2003)
[33] Langville, A., Meyer, C., Albright, R., Cox, J., Duling, D., 2006. Algorithms, initializations, and convergence for the nonnegative matrix factorization, preprint.; Langville, A., Meyer, C., Albright, R., Cox, J., Duling, D., 2006. Algorithms, initializations, and convergence for the nonnegative matrix factorization, preprint.
[34] Lawson, C.; Hanson, R., Solving Least Squares Problems (1995), SIAM: SIAM Philadelphia, PA
[35] Lee, D.; Seung, H., Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791 (1999) · Zbl 1369.68285
[36] Lee, D.; Seung, H., Algorithms for non-negative matrix factorization, Adv. Neural Inform. Process. Systems, 13, 556-562 (2001)
[37] Lin, C.-J., 2005a. On the convergence of multiplicative update algorithms for non-negative matrix factorization. Technical Report Information and Support Services Technical Report, Department of Computer Science, National Taiwan University.; Lin, C.-J., 2005a. On the convergence of multiplicative update algorithms for non-negative matrix factorization. Technical Report Information and Support Services Technical Report, Department of Computer Science, National Taiwan University.
[38] Lin, C.-J., 2005b. Projected gradient methods for non-negative matrix factorization. Technical Report Information and Support Services Technical Report ISSTECH-95-013, Department of Computer Science, National Taiwan University.; Lin, C.-J., 2005b. Projected gradient methods for non-negative matrix factorization. Technical Report Information and Support Services Technical Report ISSTECH-95-013, Department of Computer Science, National Taiwan University.
[39] Luu, K., Matson, C., Snodgrass, J., Giffin, M., Hamada, K., Lambert, J., 2003. Object characterization from spectral data. In: Proceedings of the 2003 AMOS Technical Conference, Maui, HI, September.; Luu, K., Matson, C., Snodgrass, J., Giffin, M., Hamada, K., Lambert, J., 2003. Object characterization from spectral data. In: Proceedings of the 2003 AMOS Technical Conference, Maui, HI, September.
[40] McLean, B., Elkind, P., 2003. The Smartest Guys in the Room: The Amazing Rise and Scandalous Fall of Enron. Portfolio.; McLean, B., Elkind, P., 2003. The Smartest Guys in the Room: The Amazing Rise and Scandalous Fall of Enron. Portfolio.
[41] Nagy, J. G.; Strakos, Z., Enforcing nonnegativity in image reconstruction algorithms, Math. Modeling, Estimation, and Imaging, 4121, 182-190 (2000)
[42] Nocedal, J.; Wright, S., Numerical Optimization (1999), Springer: Springer Berlin · Zbl 0930.65067
[43] Paatero, P., Least squares formulation of robust non-negative factor analysis, Chemometrics and Intell. Laboratory Syst., 37, 23-35 (1997)
[44] Paatero, P., The multilinear engine—a table-driven least squares program for solving multilinear problems, including the n-way parallel factor analysis model, J. Comput. Graphical Statist., 8, 4, 1-35 (1999)
[45] 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)
[46] Pauca, V., Shahnaz, F., Berry, M., Plemmons, R., 2004. Text mining using non-negative matrix factorizations. In: Proceedings of the Fourth SIAM International Conference on Data Mining, April 22-24. SIAM, Lake Buena Vista, FL.; Pauca, V., Shahnaz, F., Berry, M., Plemmons, R., 2004. Text mining using non-negative matrix factorizations. In: Proceedings of the Fourth SIAM International Conference on Data Mining, April 22-24. SIAM, Lake Buena Vista, FL.
[47] Pauca, P., Piper, J., Plemmons, R., 2006a. Nonnegative matrix factorization for spectral data analysis. Linear Algebra Appl. 416 (1), 29-47.; Pauca, P., Piper, J., Plemmons, R., 2006a. Nonnegative matrix factorization for spectral data analysis. Linear Algebra Appl. 416 (1), 29-47. · Zbl 1096.65033
[48] Pauca, V., Plemmons, R., Abercromby, K., 2006b. Nonnegative matrix factorization methods with physical constraints for spectral unmixing, in preparation.; Pauca, V., Plemmons, R., Abercromby, K., 2006b. Nonnegative matrix factorization methods with physical constraints for spectral unmixing, in preparation.
[49] Piper, J., Pauca, V., Plemmons, R., Giffin, M., 2004. Object characterization from spectral data using nonnegative factorization and information theory. In: Proceedings of the 2004 AMOS Technical Conference, Maui, HI, September.; Piper, J., Pauca, V., Plemmons, R., Giffin, M., 2004. Object characterization from spectral data using nonnegative factorization and information theory. In: Proceedings of the 2004 AMOS Technical Conference, Maui, HI, September.
[50] Plaza, A.; Martinez, P.; Perez, R.; Plaza, J., A quantitative and comparative analysis of endmember extraction algorithms from hyperspectral data, IEEE Trans. on Geoscience and Remote Sensing, 42, 3, 650-663 (2004)
[51] Polak, E., Computational Methods in Optimization: A Unified Approach (1971), Academic Press: Academic Press New York
[52] Powell, M., An efficient method for finding the minimum of a function of several variables without calculating derivatives, Comput. J., 7, 155-162 (1964) · Zbl 0132.11702
[53] Powell, M., On search directions for minimization, Math. Programming, 4, 193-201 (1973) · Zbl 0258.90043
[54] Salakhutdinov, R.; Roweis, S. T.; Ghahramani, Z., On the convergence of bound optimization algorithms, Uncertainty in Artificial Intelligence, 19, 509-516 (2003)
[55] Shahnaz, F.; Berry, M.; Pauca, V.; Plemmons, R., Document clustering using nonnegative matrix factorization, Inform. Process. Manage., 42, 2, 373-386 (2006) · Zbl 1087.68104
[56] Smilde, A.; Bro, R.; Geladi, P., Multi-way Analysis (2004), Wiley: Wiley West Sussex, England
[57] Torczon, V., On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1-25 (1997) · Zbl 0884.65053
[58] Wang, Y., Jiar, Y., Hu, C., Turk, M., 2004. Fisher non-negative matrix factorization for learning local features. In: Asian Conference on Computer Vision, Korea, January 27-30.; Wang, Y., Jiar, Y., Hu, C., Turk, M., 2004. Fisher non-negative matrix factorization for learning local features. In: Asian Conference on Computer Vision, Korea, January 27-30.
[59] Wild, S., 2002. Seeding non-negative matrix factorization with the spherical k-means clustering. Master’s Thesis, University of Colorado.; Wild, S., 2002. Seeding non-negative matrix factorization with the spherical k-means clustering. Master’s Thesis, University of Colorado.
[60] Wild, S., Curry, J., Dougherty, A., 2003. Motivating non-negative matrix factorizations. In: Proceedings of the Eighth SIAM Conference on Applied Linear Algebra, July 15-19. SIAM, Williamsburg, VA, \( \langle;\) http://www.siam.org/meetings/la03/proceedings \(\rangle;\); Wild, S., Curry, J., Dougherty, A., 2003. Motivating non-negative matrix factorizations. In: Proceedings of the Eighth SIAM Conference on Applied Linear Algebra, July 15-19. SIAM, Williamsburg, VA, \( \langle;\) http://www.siam.org/meetings/la03/proceedings \(\rangle;\)
[61] Wold, H., Nonlinear estimation by iterative least squares procedures, (David, F., Research Papers in Statistics (1966), Wiley: Wiley New York), 411-444 · Zbl 0161.15901
[62] Wold, H., Soft modelling by latent variables: nonlinear iterative partial least squares approach, (Gani, J., Perspectives in Probability and Statistics (1975), Academic Press: Academic Press London), 411-444
[63] Xu, W., Liu, X., Gong, Y., 2003. Document-clustering based on non-negative matrix factorization. In: Proceedings of SIGIR’03, July 28-August 1, Toronto, CA, pp. 267-273.; Xu, W., Liu, X., Gong, Y., 2003. Document-clustering based on non-negative matrix factorization. In: Proceedings of SIGIR’03, July 28-August 1, Toronto, CA, pp. 267-273.
[64] Zangwill, W., Minimizing a function without calculating derivatives, Comput. J., 10, 293-296 (1967) · Zbl 0189.48004
[65] Zdunek, R., Cichocki, A., 2006. Non-negative matrix factorization with quasi-newton optimization. In: Proceedings of the Eighth International Conference on Artificial Intelligence and Soft Computing, ICAISC, Zakopane, Poland, June 25-29.; Zdunek, R., Cichocki, A., 2006. Non-negative matrix factorization with quasi-newton optimization. In: Proceedings of the Eighth International Conference on Artificial Intelligence and Soft Computing, ICAISC, Zakopane, Poland, June 25-29.
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.