Abstract
We introduce an efficient algorithm for computing a low-rank nonnegative CANDECOMP/PARAFAC (NNCP) decomposition. In text mining, signal processing, and computer vision among other areas, imposing nonnegativity constraints to the low-rank factors of matrices and tensors has been shown an effective technique providing physically meaningful interpretation. A principled methodology for computing NNCP is alternating nonnegative least squares, in which the nonnegativity-constrained least squares (NNLS) problems are solved in each iteration. In this chapter, we propose to solve the NNLS problems using the block principal pivoting method. The block principal pivoting method overcomes some difficulties of the classical active method for the NNLS problems with a large number of variables. We introduce techniques to accelerate the block principal pivoting method for multiple right-hand sides, which is typical in NNCP computation. Computational experiments show the state-of-the-art performance of the proposed method.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Acar, E., Yener, B.: Unsupervised multiway data analysis: A literature survey. IEEE Trans. Knowl. Data Eng. 21(1), 6–20 (2009)
Bader, B.W., Berry, M.W., Browne, M.: Discussion tracking in Enron email using PARAFAC. In: Survey of Text Mining II: Clustering, Classification, and Retrieval, pp. 147–163. Springer, Berlin (2008)
Bertsekas, D.P.: Nonlinear Programming. Scientific, Athena (1999)
Bro, R., De Jong, S.: A fast non-negativity-constrained least squares algorithm. J. Chem. 11, 393–401 (1997)
Carroll, J.D., Chang, J.J.: Analysis of individual differences in multidimensional scaling via an N-way generalization of “Eckart-Young” decomposition. Psychometrika 35(3), 283–319 (1970)
Carroll, J.D., Soete, G.D., Pruzansky, S.: Fitting of the latent class model via iteratively reweighted least squares CANDECOMP with nonnegativity constraints. In: Multiway data analysis, pp. 463–472. North-Holland, Amsterdam (1989). http://portal.acm.org/citation.cfm?id=120565.120614
Cichocki, A., Phan, A.H.: Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E92-A(3), 708–721 (2009)
Cichocki, A., Zdunek, R., Amari, S.I.: Hierarchical ALS algorithms for nonnegative matrix and 3D tensor factorization. In: Lecture Notes in Computer Science, vol. 4666, pp. 169–176. Springer, Berlin (2007)
FitzGerald, D., Cranitch, M., Coyle, E.: Non-negative tensor factorisation for sound source separation. In: Proceedings of the Irish Signals and Systems Conference (2005)
Friedlander, M.P., Hatz, K.: Computing nonnegative tensor factorizations. Comput. Optim. Appl. 23(4), 631–647 (2008). doi:10.1080/10556780801996244
Harshman, R.A.: Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multi-modal factor analysis. In: UCLA Working Papers in Phonetics, vol. 16, pp. 1–84 (1970)
Júdice, J.J., Pires, F.M.: A block principal pivoting algorithm for large-scale strictly monotone linear complementarity problems. Comput. Oper. Res. 21(5), 587–596 (1994)
Kim, H., Park, H.: Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis. Bioinformatics 23(12), 1495–1502 (2007)
Kim, H., Park, H.: Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method. SIAM J. Matrix Anal. Appl. 30(2), 713–730 (2008). doi:10.1137/07069239X
Kim, H., Park, H., Eldén, L.: Non-negative tensor factorization based on alternating large-scale non-negativity-constrained least squares. In: Proceedings of IEEE 7th International Conference on Bioinformatics and Bioengineering (BIBE07), vol. 2, pp. 1147–1151 (2007)
Kim, J., Park, H.: Sparse nonnegative matrix factorization for clustering. Tech. rep., Georgia Institute of Technology Technical Report GT-CSE-08-01 (2008)
Kim, J., Park, H.: Toward faster nonnegative matrix factorization: A new algorithm and comparisons. In: Proceedings of the 2008 Eighth IEEE International Conference on Data Mining (ICDM), pp. 353–362 (2008)
Kim, J., Park, H.: Fast nonnegative matrix factorization: An active-set-like method and comparisons. SIAM J. Sci. Comput. 33, 3261 (2011)
Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455–500 (2009)
Lawson, C.L., Hanson, R.J.: Solving Least Squares Problems. Prentice Hall, New York (1974)
Lee, D.D., Seung, H.S.: Learning the parts of objects by non-negative matrix factorization. Nature 401(6755), 788–791 (1999)
Lee, D.D., Seung, H.S.: Algorithms for non-negative matrix factorization. In: Advances in Neural Information Processing Systems, vol. 13, pp. 556–562. MIT Press, Cambridge (2001)
Lim, L.H., Comon, P.: Nonnegative approximations of nonnegative tensors. J. Chem., 23(7–8), 432–441 (2009)
Paatero, P.: A weighted non-negative least squares algorithm for three-way PARAFAC factor analysis. Chemom. Intell. Lab. Syst. 38(2), 223–242 (1997)
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. Graph. Stat. 8, 854–888 (1999)
Paatero, P., Tapper, U.: Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. EnvironMetrics 5(1), 111–126 (1994)
Shashua, A., Hazan, T.: Non-negative tensor factorization with applications to statistics and computer vision. In: ICML ’05: Proceedings of the 22nd International Conference on Machine Learning, pp. 792–799. ACM, New York (2005). doi: http://doi.acm.org/10.1145/1102351.1102451
Van Benthem, M.H., Keenan, M.R.: Fast algorithm for the solution of large-scale non-negativity-constrained least squares problems. J. Chem. 18, 441–450 (2004). doi:10.1002/cem.889
Welling, M., Weber, M.: Positive tensor factorization. Pattern Recognit. Lett. 22(12), 1255–1261 (2001). doi:10.1016/S0167-8655(01)00070-8
Acknowledgements
The work in this chapter was supported in part by the National Science Foundation grants CCF-0732318, CCF-0808863, and CCF-0956517. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag London Limited
About this chapter
Cite this chapter
Kim, J., Park, H. (2012). Fast Nonnegative Tensor Factorization with an Active-Set-Like Method. In: Berry, M., et al. High-Performance Scientific Computing. Springer, London. https://doi.org/10.1007/978-1-4471-2437-5_16
Download citation
DOI: https://doi.org/10.1007/978-1-4471-2437-5_16
Publisher Name: Springer, London
Print ISBN: 978-1-4471-2436-8
Online ISBN: 978-1-4471-2437-5
eBook Packages: Computer ScienceComputer Science (R0)