Regularized nonnegative matrix factorization: Geometrical interpretation and application to spectral unmixing

• Autorzy: Zdunek R.

Identyfikatory

DOI

10.2478/amcs-2014-0017

• Języki publikacji: EN

Abstrakty

EN

Nonnegative Matrix Factorization (NMF) is an important tool in data spectral analysis. However, when a mixing matrix or sources are not sufficiently sparse, NMF of an observation matrix is not unique. Many numerical optimization algorithms, which assure fast convergence for specific problems, may easily get stuck into unfavorable local minima of an objective function, resulting in very low performance. In this paper, we discuss the Tikhonov regularized version of the Fast Combinatorial NonNegative Least Squares (FC-NNLS) algorithm (proposed by Benthem and Keenan in 2004), where the regularization parameter starts from a large value and decreases gradually with iterations. A geometrical analysis and justification of this approach are presented. The numerical experiments, carried out for various benchmarks of spectral signals, demonstrate that this kind of regularization, when applied to the FC-NNLS algorithm, is essential to obtain good performance.

Słowa kluczowe

EN

blind source separation; nonnegative matrix factorization; active set algorithm; regularized NMF; polytope approximation

PL

ślepa separacja sygnału; nieujemna faktoryzacja macierzy

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2014
• Tom: Vol. 24, no. 2
• Strony: 233--247
• Opis fizyczny: Bibliogr. 60 poz., tab., wykr.

Twórcy

autor

Zdunek R.

• Department of Electronics, Wrocław University of Technology, ul. Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• [1] Benthem, M.H.V. and Keenan, M.R. (2004). Fast algorithm for the solution of large-scale non-negativity-constrained least squares problems, Journal of Chemometrics 18(10): 441–450.
• [2] Berry, M., Browne, M., Langville, A.N., Pauca, P. and Plemmons, R.J. (2007). Algorithms and applications for approximate nonnegative matrix factorization, Computational Statistics and Data Analysis 52(1): 155–173.
• [3] Bioucas-Dias, J.M. (2009). A variable splitting augmented Lagrangian approach to linear spectral unmixing, Proceedings of the 1st IEEE GRSS Workshop on Hyperspectral Image and Signal Processing, WHISPERS, Grenoble, France.
• [4] Bioucas-Dias, J.M. and Figueiredo, M. (2010). Alternating direction algorithms for constrained sparse regression: Application to hyperspectral unmixing, Proceedings of the 2nd IEEE GRSS Workshop on Hyperspectral Image and Signal Processing, WHISPERS, Raykjavik, Iceland.
• [5] Bioucas-Dias, J.M., Plaza, A., Dobigeon, N., Parente, M., Du, Q., Gader, P. and Chanussot, J. (2012). Hyperspectral unmixing overview: Geometrical, statistical, and sparse regression-based approaches, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing 5(2): 354–379.
• [6] Bro, R. and Jong, S.D. (1997). A fast non-negativity-constrained least squares algorithm, Journal of Chemometrics 11(5): 393–401.
• [7] Calvetti, D., Lewis, B. and Reichel, L. (2001). On the choice of subspace for iterative methods for linear discrete ill-posed problems, International Journal of Applied Mathematics and Computer Science 11(5): 1069–1092.
• [8] Chan, T.-H., Ma, W.-K., Ambikapathi, A.-M. and Chi, C.-Y. (2011). A simplex volume maximization framework for hyperspectral endmember extraction, IEEE Transactions on Geoscience and Remote Sensing 49(11): 4177–4193.
• [9] Chen, D. and Plemmons, R.J. (2009). Nonnegativity constraints in numerical analysis, in A. Bultheel and R. Cools (Eds.), The Birth of Numerical Analysis, World Scientific, Singapore, pp. 109–139.
• [10] Chu, M.T. and Lin, M. M. (2008). Low dimensional polytype approximation and its applications to nonnegative matrix factorization, SIAM Journal of Scientific Computing 30(3): 1131–1151.
• [11] Cichocki, A., Zdunek, R., Phan, A.H. and Amari, S.-I. (2009). Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation, Wiley and Sons, Chichester.
• [12] Dabrowski, A. and Cetnarowicz, D. (2008). Iterative SVD algorithm as a BSS solution, Proceedings of the International Conference on Signals and Electronic Systems, ICSES 2008, Cracow, Poland, pp. 401–404.
• [13] Donoho, D. and Stodden, V. (2004). When does non-negative matrix factorization give a correct decomposition into parts?, in S. Thrun, L. Saul and B. Sch¨olkopf (Eds.), Advances in Neural Information Processing Systems (NIPS), Vol. 16, MIT Press, Cambridge, MA, pp. 1141–1148.
• [14] Elden, L. (1977). Algorithms for the regularization of ill-conditioned least squares problems, BIT 17(2): 134–145.
• [15] Garda, B. and Galias, Z. (2012). Non-negative least squares and the Tikhonov regularization methods for coil design problems, Proceedings of the International Conference on Signals and Electronic Systems, ICSES’12, Wrocław, Poland.
• [16] Gobinet, C., Perrin, E. and Huez, R. (2004). Application of nonnegative matrix factorization to fluorescence spectroscopy, Proceedings of the European Signal Processing Conference, EUSIPCO 2004, Vienna, Austria, pp. 1095–1098.
• [17] Górecki, T. and Łuczak, M. (2013). Linear discriminant analysis with a generalization of the Moore–Penrose pseudoinverse, International Journal of Applied Mathematics and Computer Science 23(2): 463–471, DOI: 10.2478/amcs-2013-0035.
• [18] Guo, Z., Wittman, T. and Osher, S. (2009). L1 unmixing and its application to hyperspectral image enhancement, in S.S. Shen and P.E. Lewis (Eds.), Algorithms and Technologies for Multispectral, Hyperspectral, and Ultraspectral Imagery XV, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 7334, International Society for Optical Engineering, Orlando, FL, p. 73341M+.
• [19] Hamza, A. and Brady, D. (2006). Reconstruction of reflectance spectra using robust nonnegative matrix factorization, IEEE Transactions on Signal Processing 54(9): 3637–3642.
• [20] Hancewicz, T.M. and Wang, J.-H. (2005). Discriminant image resolution: A novel multivariate image analysis method utilizing a spatial classification constraint in addition to bilinear nonnegativity, Chemometrics and Intelligent Laboratory Systems 77(1–2): 18–31.
• [21] Hansen, P.C. (1998). Rank-Deficient and Discrete Ill-Posed Problems, SIAM, Philadelphia, PA.
• [22] Heylen, R., Burazerovic, D. and Scheunders, P. (2011). Fully constrained least squares spectral unmixing by simplex projection, IEEE Transactions on Geoscience and Remote Sensing 49(11): 4112–4122.
• [23] Huck, A., Guillaume, M. and Blanc-Talon, J. (2010). Minimum dispersion constrained nonnegative matrix factorization to unmix hyperspectral data, IEEE Transactions on Geoscience and Remote Sensing 48(6): 2590–2602.
• [24] Hyvrinen, A., Karhunen, J. and Oja, E. (2001). Independent Component Analysis, John Wiley, New York, NY.
• [25] Igual, J. and Llinares, R. (2008). Nonnegative matrix factorization of laboratory astrophysical ice mixtures, IEEE Journal of Selected Topics in Signal Processing 2(5): 697–706.
• [26] Igual, J., Llinares, R. and Salazar, A. (2006). Source separation of astrophysical ice mixtures, Proceedings of the 6th International Conference on Independent Component Analysis and Blind Signal Separation, Charleston, IL, USA, pp. 368–375.
• [27] Iordache, M., Dias, J. and Plaza, A. (2011). Sparse unmixing of hyperspectral data, IEEE Transactions on on Geoscience and Remote Sensing 49(2): 2014–2039.
• [28] Iordache, M., Dias, J. and Plaza, A. (2012). Total variation spatial regularization for sparse hyperspectral unmixing, IEEE Transactions on Geoscience and Remote Sensing 50(11): 4484–4502.
• [29] Jia, S. and Qian, Y. (2009). Constrained nonnegative matrix factorization for hyperspectral unmixing, IEEE Transactions on Geoscience and Remote Sensing 47(1): 161–173.
• [30] Kim, D., Sra, S. and Dhillon, I.S. (2007). Fast Newton-type methods for the least squares nonnegative matrix approximation problem, Proceedings of the 6th SIAM International Conference on Data Mining, Minneapolis, MN, USA, pp. 343–354.
• [31] Kim, H. and Park, H. (2008). Non-negative matrix factorization based on alternating non-negativity constrained least squares and active set method, SIAM Journal on Matrix Analysis and Applications 30(2): 713–730.
• [32] Kim, J. and Park, H. (2011). Fast nonnegative matrix factorization: An active-set-like method and comparisons, SIAM Journal on Scientific Computing 33(6): 3261–3281.
• [33] Krawczyk-Stańdo, D. and Rudnicki, M. (2007). Regularization parameter selection in discrete ill-posed problems—The use of the U-curve, International Journal of Applied Mathematics and Computer Science 17(2): 157–164, DOI: 10.2478/v10006-007-0014-3.
• [34] Kulczycki, P. and Charytanowicz, M. (2010). A complete gradient clustering algorithm formed with kernel estimators, International Journal of Applied Mathematics and Computer Science 20(1): 123–134, DOI: 10.2478/v10006-010-0009-3.
• [35] Lawson, C.L. and Hanson, R.J. (1974). Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, NJ.
• [36] Lee, D.D. and Seung, H.S. (1999). Learning the parts of objects by non-negative matrix factorization, Nature 401(6755): 788–791.
• [37] Li, H., Adali, T., Wang, W., Emge, D. and Cichocki, A. (2007). Non-negative matrix factorization with orthogonality constraints and its application to Raman spectroscopy, The Journal of VLSI Signal Processing 48(1–2): 83–97.
• [38] Li, J. and Bioucas-Dias, J.M. (2008). Minimum volume simplex analysis: A fast algorithm to unmix hyperspectral data, Proceedings of the IEEE International Geoscience and Remote Sensing Symposium, IGARSS 2008, Boston, MA, USA, Vol. 3, pp. 250–253.
• [39] Likic, V.A. (2009). Extraction of pure components from over-lapped signals in gas chromatography-mass spectrometry (GC-MS), BioData Mining 2(6): 1–11.
• [40] Lin, C.-J. (2007). Projected gradient methods for non-negative matrix factorization, Neural Computation 19(10): 2756–2779.
• [41] Llinares, R., Igual, J., Miró-Borrás, J. and Camacho, A. (2010). Analysis of astrophysical ice analogs using regularized alternating least squares, Proceedings of the 20th International Conference on Artificial Neural Networks, ICANN 2010, Thessaloniki, Greece, pp. 199–204.
• [42] Makowski, R. (2003). Source pulse estimation of mine shocks by blind deconvolution, Pure and Applied Geophysics 160(7): 1191–1205.
• [43] Miao, L. and Qi, H. (2007). Endmember extraction from highly mixed data using minimum volume constrained nonnegative matrix factorization, IEEE Transactions on Geoscience and Remote Sensing 45(3): 765–777.
• [44] Miron, S., Dossot, M., Carteret, C., Margueron, S. and Brie, D. (2011). Joint processing of the parallel and crossed polarized Raman spectra and uniqueness in blind nonnegative source separation, Chemometrics and Intelligent Laboratory Systems 105(1): 7–18.
• [45] Nascimento, J.M.P. and Bioucas-Dias, J.M. (2005). Vertex component analysis: A fast algorithm to unmix hyperspectral data, IEEE Transactions on Geoscience and Remote Sensing 43(4): 898–910.
• [46] Pauca, V.P., Pipera, J. and Plemmons, R.J. (2006). Nonnegative matrix factorization for spectral data analysis, Linear Algebra and Its Applications 416(1): 29–47.
• [47] Pengo, T., Munoz-Barrutia, A. and de Solorzano, C.O. (2010). Spectral unmixing of multiply stained fluorescence samples, in A. Mendez-Vilas and J. Diaz (Eds.), Microscopy: Science, Technology, Applications and Education, Microscopy Book Series, No. 4, Formatex Research Center, Badajoz, pp. 2079–2087.
• [48] Plaza, J., Hendrix, E.M.T., García, I., Martin, G. and Plaza, A. (2012). On endmember identification in hyperspectral images without pure pixels: A comparison of algorithms, Journal of Mathematical Imaging and Vision 42(2–3): 163–175.
• [49] Qian, Y., Jia, S., Zhou, J. and Robles-Kelly, A. (2011). Hyperspectral unmixing via l1/2 sparsity-constrained nonnegative matrix factorization, IEEE Transactions on Geoscience and Remote Sensing 49(11): 4282–4297.
• [50] Rojas, M. and Steihaug, T. (2002). An interior-point trustregion-based method for large-scale non-negative regularization, Inverse Problems 18(5): 1291–1307.
• [51] Sajda, P., Du, S., Brown, T., Parra, L. and Stoyanova, R. (2003). Recovery of constituent spectra in 3D chemical shift imaging using nonnegative matrix factorization, Proceedings of the 4th International Symposium on Independent Component Analysis and Blind Signal Separation, Nara, Japan, pp. 71–76.
• [52] Sajda, P., Du, S., Brown, T.R., Stoyanova, R., Shungu, D.C., Mao, X. and Parra, L.C. (2004). Nonnegative matrix factorization for rapid recovery of constituent spectra in magnetic resonance chemical shift imaging of the brain, IEEE Transactions on Medical Imaging 23(12): 1453–1465.
• [53] Siwek, K., Osowski, S. and Szupiluk, R. (2009). Ensemble neural network approach for accurate load forecasting in a power system, International Journal of Applied Mathematics and Computer Science 19(2): 303–315, DOI: 10.2478/v10006-009-0026-2.
• [54] Tong, L., van der Veen, A.-J., Dewilde, P. and Sung, Y. (2003). Blind decorrelating RAKE receivers for longcode WCDMA, IEEE Transactions on Signal Processing 51(6): 1642–1655.
• [55] Woźniak, M. and Krawczyk, B. (2012). Combined classifier based on feature space partitioning, International Journal of Applied Mathematics and Computer Science 22(4): 855–866, DOI: 10.2478/v10006-012-0063-0.
• [56] Zdunek, R. (2011). Regularized active set least squares algorithm for nonnegative matrix factorization in application to Raman spectra separation, in J. Cabestany, I. Rojas and G. Joya (Eds.), Advances in Computational Intelligence, Lecture Notes in Computer Science, Vol. 6692, Springer, Berlin/Heidelberg, pp. 492–499.
• [57] Zdunek, R. (2012). Hyperspectral image unmixing with nonnegative matrix factorization, Proceedings of the IEEE International Conference on Signals and Electronic Systems, ICSES 2012, Wrocław, Poland.
• [58] Zdunek, R. and Cichocki, A. (2007). Nonnegative matrix factorization with constrained second-order optimization, Signal Processing 87(8): 1904–1916.
• [59] Zhang, J., Rivard, B. and Rogge, D.M. (2008). The successive projection algorithm (SPA), an algorithm with a spatial constraint for the automatic search of endmembers in hyperspectral data, Sensors 8(2): 1321–1342.
• [60] Zymnis, A., Kim, S.-J., Skaf, J., Parente, M. and Boyd, S. (2007). Hyperspectral image unmixing via alternating projected subgradients, Proceedings of the 41st Asilomar Conference on Signals, Systems and Computers, ACSSC 2007, Pacific Grove, CA, USA, pp. 1164–1168.