Solving sparse non-negative tensor equations: algorithms and applications

doi:10.1007/s11464-014-0377-3

Front. Math. China

2015, Vol. 10

Issue (3) : 649-680 https://doi.org/10.1007/s11464-014-0377-3

RESEARCH ARTICLE

Solving sparse non-negative tensor equations: algorithms and applications

Xutao LI¹, Michael K. NG²(

)

¹. School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore
². Centre for Mathematical Imaging and Vision, and Department of Mathematics, Hong Kong Baptist University, Hong Kong, China

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

Abstract

We study iterative methods for solving a set of sparse non-negative tensor equations (multivariate polynomial systems) arising from data mining applications such as information retrieval by query search and community discovery in multi-dimensional networks. By making use of sparse and non-negative tensor structure, we develop Jacobi and Gauss-Seidel methods for solving tensor equations. The multiplication of tensors with vectors are required at each iteration of these iterative methods, the cost per iteration depends on the number of non-zeros in the sparse tensors. We show linear convergence of the Jacobi and Gauss-Seidel methods under suitable conditions, and therefore, the set of sparse non-negative tensor equations can be solved very efficiently. Experimental results on information retrieval by query search and community discovery in multi-dimensional networks are presented to illustrate the application of tensor equations and the effectiveness of the proposed methods.

Keywords Nonnegative tensor multi-dimensional network information retrieval community iterative method multivariate polynomial equation

Corresponding Author(s): Michael K. NG

Issue Date: 01 April 2015

Cite this article:

Xutao LI,Michael K. NG. Solving sparse non-negative tensor equations: algorithms and applications[J]. Front. Math. China, 2015, 10(3): 649-680.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-014-0377-3
https://academic.hep.com.cn/fmc/EN/Y2015/V10/I3/649

1	B Buchberger. Gröbner basis: an algorithmic method in polynomial ideal theory. In: N K Bose, ed. Multidimensional System Theory. Dordrecht, Boston, Lancaster: D Reidel Publishing Company, 1985, 184−232 https://doi.org/10.1007/978-94-009-5225-6_6
2	D Cai, X He, J Han. Tensor space model for document analysis. In: International Conference on Research and Development in Information Retrieval. 2006, 625−626 https://doi.org/10.1145/1148170.1148287
3	K Chang, K Pearson, T Zhang. Perron-Frobenius theorem for nonnegative tensors. Commun Math Sci, 2008, 6: 507−520 https://doi.org/10.4310/CMS.2008.v6.n2.a12
4	K Chang, T Zhang. On the uniqueness and non-uniqueness of the Z-eigenvector for transition probability tensors. J Math Anal Appl, 2013, 408: 525−540 https://doi.org/10.1016/j.jmaa.2013.04.019
5	A Clauset. Finding local community structure in networks. Phys Rev E, 2005, 72: 026132 https://doi.org/10.1103/PhysRevE.72.026132
6	P Comon, X Luciani, A De Almeida. Tensor decompositions, alternating least squares and other tales. J Chemometrics, 2009, 23(7−8): 393−405 https://doi.org/10.1002/cem.1236
7	F Drexler. Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen. Numer Math, 1977, 29(1): 45−58 https://doi.org/10.1007/BF01389312
8	C Garcia, W Zangwill. Finding all solutions to polynomial systems and other systems of equations. Math Program, 1979, 16(1): 159−176 https://doi.org/10.1007/BF01582106
9	T Haveliwala. Topic-sensitive PageRank. In: Proceedings of the 11th International World Wide Web Conference, 2002 https://doi.org/10.1145/511511.511513
10	S Hu, L Qi. Convergence of a second order Markov chain.
11	V Istratescu. Fixed Point Theory: An Introduction. Dordrecht: D Reidel Publishing Company, 1981 https://doi.org/10.1007/978-94-009-8177-5
12	R Kellogg. Uniqueness in the Schauder fixed point theorem. Proc Amer Math Soc, 1976, 60(1): 207−210 https://doi.org/10.1090/S0002-9939-1976-0423137-6
13	J Kleinberg. Authoritative sources in a hyperlinked environment. J ACM, 1999, 46(5): 604−632 https://doi.org/10.1145/324133.324140
14	T Kolda, B Bader. The TOPHITS model for higher-order web link analysis. In: Workshop on Link Analysis, Counterterrorism and Security. 2006, 26−29
15	T Kolda, B Bader. Tensor decompositions and applications. SIAM Rev, 2009, 51: 455−500 https://doi.org/10.1137/07070111X
16	T Kolda, B Bader, J Kenny. Higher-order web link analysis using multilinear algebra. In: Proceedings of the 5th International Conference on Data Mining. 2005 https://doi.org/10.1109/ICDM.2005.77
17	L Lathauwer, B Moor, J Vandewalle. A multilinear singular value decomposition. SIAM J Matrix Anal Appl, 2000, 21: 1253−1278 https://doi.org/10.1137/S0895479896305696
18	Q Li, X Shi, D Schonfeld. A general framework for robust HOSVD-based indexing and retrieval with high-order tensor data. ICASSP, 2011, 873−876 https://doi.org/10.1109/ICASSP.2011.5946543
19	T Li. Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta Numer, 1997, 6: 399−436 https://doi.org/10.1017/S0962492900002749
20	T Li, C Ding, F Wang. Guest editorial: special issue on data mining with matrices, graphs and tensors. Data Min Knowl Discov, 2011, 22(3): 337−339 https://doi.org/10.1007/s10618-011-0214-1
21	W Li, M Ng. On the limiting probability distribution of a transition probability tensor. Linear Multilinear Algebra, 2013, 20: 985−1000 https://doi.org/10.1002/nla.1886
22	X Li, M Ng, Y Ye. Har: hub, authority and relevance scores in multi-relational data for query search. In: Proceedings of the 12th SIAM International Conference on Data Mining. 2012, 141−152 https://doi.org/10.1137/1.9781611972825.13
23	X Li, M Ng, Y Ye. MultiComm: finding community structures in multi-dimensional networks. IEEE Trans Knowl Data Engineering, 2014, 26(4): 929−941 https://doi.org/10.1109/TKDE.2013.48
24	Y Lin, J Sun, P Castro, R Konuru, H Sundaram, A Kelliher. MetaFac: community discovery via relational hypergraph factorization. In: Proceedings of the 15th ACM SIGKDD on Knowledge Discovery and Data Mining. 2009, 527−536 https://doi.org/10.1145/1557019.1557080
25	N Liu, B Zhang, J Yan, Z Chen, W Liu, F Bai, L Chien. Text representation: from vector to tensor. In: Proceedings of the Fifth IEEE International Conference on Data Mining. 2005
26	K Maruhashi, F Guo, C Faloutsos. MultiAspectForensics: pattern mining on largescale heterogeneous networks with tensor analysis. In: International Conference on Advances in Social Networks Analysis and Mining. 2011, 203−210 https://doi.org/10.1109/ASONAM.2011.80
27	M Newman. The structure and function of complex networks. SIAM Rev, 2003, 45: 167−256 https://doi.org/10.1137/S003614450342480
28	M Ng, X Li, Y Ye. MultiRank: co-ranking scheme for objects and relations in multi-dimensional data. In: Proceedings of the 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2011, 1217−1225
29	S E Robertson, S Walker. Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval. In: Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 1994, 232−241 https://doi.org/10.1007/978-1-4471-2099-5_24
30	B Savas, L Eldén. Krylov subspace methods for tensor computations. LITH-MAT-R-2009-02-SE, Preprint
31	J Sun, S Papadimitriou, C Lin, N Cao, S Liu, W Qian. Multivis: Content-based social network exploration through multi-way visual analysis. In: Proceedings of the 9th SIAM International Conference on Data Mining. 2009, 1063−1074 https://doi.org/10.1137/1.9781611972795.91
32	J Sun, D Tao, C Faloutsos. Beyond streams and graphs: dynamic tensor analysis. In: Proceedings of the 12th ACM SIGKDD on Knowledge Discovery and Data Mining. 2006, 374−383 https://doi.org/10.1145/1150402.1150445
33	J Sun, D Tao, S Papadimitriou, P Yu, C Faloutsos. Incremental tensor analysis: theory and applications. ACM Trans Knowl Discov from Data, 2008, 2(3): 1−37 https://doi.org/10.1145/1409620.1409621
34	J Sun, H Zeng, H Liu, Y Lu, Z Chen. CubeSVD: A novel approach to personalized web search. In: International Conference on WWW. 2005, 382−390
35	D Tao, X Li, X Wu, S Maybank. General tensor discriminant analysis and Gabor features for gait recognition. IEEE Trans Pattern Anal Machine Intelligence, 2007, 29: 1700−1715 https://doi.org/10.1109/TPAMI.2007.1096
36	H Tong, C Faloutsos, J Pan. Random walk with restart: fast solutions and applications. Knowledge and Information Systems, 2008, 14(3): 327−346 https://doi.org/10.1007/s10115-007-0094-2
37	J Verschelde, P Verlinden, R Cools. Homotopies exploiting Newton polytopes for solving sparse polynomial systems. SIAM J Numer Anal, 1994, 31(3): 915−930 https://doi.org/10.1137/0731049
38	E Voorhees, D Harman. TREC: Experiment and Evaluation in Information Retrieval. Cambridge: MIT Press, 2005
39	H Wermser, A Rettinger, V Tresp. Modeling and learning context-aware recommendation scenarios using tensor decomposition. In: International Conference on Advances in Social Networks Analysis and Mining. 2011, 137−144 https://doi.org/10.1109/ASONAM.2011.56

[1]	Gang WANG, Yuan ZHANG, YijuWANG WANG. Brauer-type bounds for Hadamard product of nonnegative tensors[J]. Front. Math. China, 2020, 15(3): 555-570.
[2]	Haibin CHEN, Yiju WANG. On computing minimal H-eigenvalue of sign-structured tensors[J]. Front. Math. China, 2017, 12(6): 1289-1302.
[3]	Yisheng SONG, Liqun QI. Positive eigenvalue-eigenvector of nonlinear positive mappings[J]. Front Math Chin, 2014, 9(1): 181-199.
[4]	Liping ZHANG. Linear convergence of an algorithm for largest singular value of a nonnegative rectangular tensor[J]. Front Math Chin, 2013, 8(1): 141-153.
[5]	Guanglu ZHOU, Liqun QI, Soon-Yi WU. Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor[J]. Front Math Chin, 2013, 8(1): 155-168.
[6]	JIANG Erxiong. Algorithm for solving shifted skew-symmetric linear system[J]. Front. Math. China, 2007, 2(2): 227-242.

Viewed

Full text

Abstract

Cited

Shared

Discussed