×

Nonnegative tensor factorizations using an alternating direction method. (English) Zbl 1263.15026

Summary: The nonnegative tensor (matrix) factorization finds more and more applications in various disciplines including machine learning, data mining, and blind source separation, etc. In computation, the optimization problem involved is solved by alternatively minimizing one factor while the others are fixed. To solve the subproblem efficiently, we first exploit a variable regularization term which makes the subproblem far from ill-condition. Second, an augmented Lagrangian alternating direction method is employed to solve this convex and well-conditioned regularized subproblem, and two accelerating skills are also implemented. Some preliminary numerical experiments are performed to show the improvements of the new method.

MSC:

15A69 Multilinear algebra, tensor calculus
15A23 Factorization of matrices
65F30 Other matrix algorithms (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Acar E, Dunlavy D M, Kolda T G. A scalable optimization approach for fitting canonical tensor decompositions. J Chemometrics, 2011, 25(2): 67–86 · doi:10.1002/cem.1335
[2] Bader B W, Kolda T G. Algorithm 862: MATLAB tensor classes for fast algorithm prototyping. ACM Trans Math Software, 2006, 32(4): 635–653 · Zbl 1230.65054 · doi:10.1145/1186785.1186794
[3] Bader B W, Kolda T G. Efficient MATLAB computations with sparse and factored tensors. SIAM J Sci Comput, 2007, 30(1): 205–231 · Zbl 1159.65323 · doi:10.1137/060676489
[4] Benetos E, Kotropoulos C. Non-negative tensor factorization applied to music genre classification. IEEE Trans Audio, Speech, Language Processing, 2010, 18(8): 1955–1967 · doi:10.1109/TASL.2010.2040784
[5] Benthem M H Van, Keenan M R. Fast algorithm for the solution of large-scale nonnegativity-constrained least squares problems. J Chemometrics, 2004, 18(10): 441–450 · doi:10.1002/cem.889
[6] Berry M W, Browne M. Email surveillance using non-negative matrix factorization. Comput Math Organization Theory, 2005, 11(3): 249–264 · Zbl 1086.68502 · doi:10.1007/s10588-005-5380-5
[7] Berry M W, Browne M, Langville A N, Pauca V P, Plemmons R J. Algorithms and applications for approximate nonnegative matrix factorization. Comput Statist Data Anal, 2007, 52(1): 155–173 · Zbl 1452.90298 · doi:10.1016/j.csda.2006.11.006
[8] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. In: Jordan M, ed. Foundations and Trends in Machine Learning, Vol 3. 2011, 1–122 http://www.stanford.edu/\(\sim\)boyd/papers/admm_distr_stats.html · Zbl 1229.90122
[9] Bro R, Jong S De. A fast non-negativity-constrained least squares algorithm. J Chemometrics, 1997, 11(5): 393–401 · doi:10.1002/(SICI)1099-128X(199709/10)11:5<393::AID-CEM483>3.0.CO;2-L
[10] Chen Y, Wang X, Shi C, Lua E K, Fu X M, Deng B X, Li X. Phoenix: a weight-based network coordinate system using matrix factorization. IEEE Trans Network Service Management, 2011, 8(4): 334–347 · doi:10.1109/TNSM.2011.110911.100079
[11] Cichocki A, Zdunek R, Phan A H, Amari S. Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. New York: Wiley, 2009
[12] Georghiades A S, Belhumeur P N, Kriegman D J. From few to many: illumination cone models for face recognition under variable lighting and pose. IEEE Trans Pattern Anal Machine Intelligence, 2001, 23(6): 643–660 · Zbl 05111520 · doi:10.1109/34.927464
[13] Han D R, Xu W, Yang H. An operator splitting method for variational inequalities with partially unknown mappings. Numer Math, 2008, 111(2): 207–237 · Zbl 1159.65069 · doi:10.1007/s00211-008-0181-7
[14] He B S, Liao L Z, Han D R, Yang H. A new inexact alternating directions method for monotone variational inequalities. Math Program, 2002, 92(1): 103–118 · Zbl 1009.90108 · doi:10.1007/s101070100280
[15] He B S, Yang H. Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities. Oper Res Lett, 1998, 23(3–5): 151–161 · Zbl 0963.49006 · doi:10.1016/S0167-6377(98)00044-3
[16] He B S, Yang H, Wang S L. Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J Optim Theory Appl, 2000, 106(2): 337–356 · Zbl 0997.49008 · doi:10.1023/A:1004603514434
[17] Kim H, Park H. Sparse non-negative matrix factorizations via alternating nonnegativity-constrained least squares for microarray data analysis. Bioinformatics, 2007, 23(12): 1495–1502 · doi:10.1093/bioinformatics/btm134
[18] Kim H, Park H. Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method. SIAM J Matrix Anal Appl, 2008, 30(2): 713–730 · Zbl 1162.65354 · doi:10.1137/07069239X
[19] Kim J, Park H. Fast nonnegative matrix factorization: an active-set-like method and comparisons. SIAM J Sci Comput, 2011, 33(6): 3261–3281 · Zbl 1232.65068 · doi:10.1137/110821172
[20] Lawson C L, Hanson R J. Solving Least Squares Problems. Philadelphia: SIAM, 1995 · Zbl 0860.65029
[21] Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization. Nature, 1999, 401: 788–791 · Zbl 1369.68285 · doi:10.1038/44565
[22] Lee D D, Seung H S. Algorithms for non-negative matrix factorization. Adv Neural Inf Process Syst, 2001, 13: 556–562
[23] Lee K-C, Ho J, Kriegman D J. Acquiring linear subspaces for face recognition under variable lighting. IEEE Trans Pattern Anal Machine Intelligence, 2005, 27(5): 684–698 · Zbl 05111315 · doi:10.1109/TPAMI.2005.92
[24] Lim L -H, Comon P. Nonnegative approximations of nonnegative tensors. J Chemometrics, 2009, 23(7–8): 432–441 · doi:10.1002/cem.1244
[25] Lin C -J. Projected gradient methods for non-negative matrix factorization. Neural Comput, 2007, 19(10): 2756–2779. http://www.csie.ntu.edu.tw/\(\sim\)cjlin/nmf/index.html · Zbl 1173.90583 · doi:10.1162/neco.2007.19.10.2756
[26] Mao Y, Saul L K, Smith J M. IDES: an internet distance estimation service for large networks. IEEE J Selected Areas Communications, 2006, 24(12): 2273–2284 · doi:10.1109/JSAC.2006.884026
[27] Nielsen F A, Balslev D, Hansen L K. Mining the posterior cingulate: segregation between memory and pain components. NeuroImage, 2005, 27(3): 520–532 · doi:10.1016/j.neuroimage.2005.04.034
[28] Paatero P, Tapper U. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmatrics, 1994, 5(2): 111–126 · doi:10.1002/env.3170050203
[29] Schmidt M N, Mohamed S. Probabilistic non-negative tensor factorisation using markov chain monte carlo. In: European Signal Processing Conference. 2009, 1918–1922
[30] Shashua A, Hazan T. Non-negative tensor factorization with applications to statistics and computer vision. In: Proceedings of the 22nd International Conference on Machine Learning (ICML’ 05). 2005, 792–799
[31] Smilde A, Bro R, Geladi P. Multi-way Analysis: Applications in the Chemical Sciences. New York: John Wiley &amp; Sons, 2004
[32] Vavasis S A. On the complexity of nonnegative matrix factorization. SIAM J Optim, 2009, 20(3): 1364–1377 · Zbl 1206.65130 · doi:10.1137/070709967
[33] Zhang Q, Wang H, Plemmons R, Pauca V P. Spectral unmixing using nonnegative tensor factorization. In: ACM Southeast Regional Conference. New York: ACM, 2007, 531–532
[34] Zhang Y. Theory of compressive sensing via l 1-minimizatIon: a non-RIP analysis and extensions. Technical Report TR08-11, revised. Department of Computational and Applied Mathematics, Rice University, Houston, Texas. 2008. http://www.caam.rice.edu/\(\sim\)zhang/reports/tr0811_revised.pdf
[35] Zhang Y. An alternating direction algorithm for nonnegative matrix factorization. Technical Report TR10-03. Department of Computational and Applied Mathematics, Rice University, Houston, Texas. 2010. http://www.caam.rice.edu/?zhang/reports/tr1003.pdf
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.