Nonnegative tensor factorizations using an alternating direction method

doi:10.1007/s11464-012-0264-8

Front Math Chin

0, Vol.

Issue () : 3-18 https://doi.org/10.1007/s11464-012-0264-8

RESEARCH ARTICLE

Nonnegative tensor factorizations using an alternating direction method

Xingju CAI¹, Yannan CHEN^1,2, Deren HAN¹(

)

1. School of Mathematical Sciences, Key Laboratory for NSLSCS of Jiangsu Province, Nanjing Normal University, Nanjing 210023, China; 2. College of Science, Nanjing Forestry University, Nanjing 210037, China

Download: PDF(752 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

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.

Keywords Nonnegative matrix factorization nonnegative tensor factorization nonnegative least squares alternating direction method

Corresponding Author(s): HAN Deren,Email:handeren@njnu.edu.cn

Issue Date: 01 February 2013

Cite this article:

Xingju CAI,Yannan CHEN,Deren HAN. Nonnegative tensor factorizations using an alternating direction method[J]. Front Math Chin, 0, (): 3-18.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-012-0264-8
https://academic.hep.com.cn/fmc/EN/Y0/V/I/3

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 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 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 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 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/&tilde;boyd/papers/admm distr stats.html
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 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 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 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 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 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 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): -3281 doi: 10.1137/110821172
20	Lawson C L, Hanson R J. Solving Least Squares Problems. Philadelphia: SIAM , 1995 doi: 10.1137/1.9781611971217
21	Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization. Nature , 1999, 401: 788-791 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 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/&tilde;cjlin/nmf/index.html 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 doi: 10.1145/1102351.1102451
31	Smilde A, Bro R, Geladi P. Multi-way Analysis: Applications in the Chemical Sciences. New York: John Wiley & Sons, 2004 doi: 10.1002/0470012110
32	Vavasis S A. On the complexity of nonnegative matrix factorization. SIAM J Optim , 2009, 20(3): 1364-1377 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 l1-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/&tilde;zhang/reports/tr0811 revised.pdf
35	Zhang Y. An alternating direction algorithm for nonnegative matrix factorization. Techxnical Report TR10-03. Department of Computational and Applied Mathematics, Rice University, Houston, Texas . 2010. http://www.caam.rice.edu/&tilde;zhang/reports/tr1003.pdf

[1]	Ke GUO, Deren HAN, David Z. W. WANG, Tingting WU. Convergence of ADMM for multi-block nonconvex separable optimization models[J]. Front. Math. China, 2017, 12(5): 1139-1162.
[2]	Yangyang XU, Wotao YIN, Zaiwen WEN, Yin ZHANG. An alternating direction algorithm for matrix completion with nonnegative factors[J]. Front Math Chin, 2012, 7(2): 365-384.

Viewed

Full text

Abstract

Cited

Shared

Discussed