Circulant tensors with applications to spectral hypergraph theory and stochastic process

Zhongming  Chen; Liqun Qi

doi:10.3934/jimo.2016.12.1227

Article Contents

2016, Volume 12, Issue 4: 1227-1247. Doi: 10.3934/jimo.2016.12.1227

This issue Previous Article Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem Next Article Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrix

Circulant tensors with applications to spectral hypergraph theory and stochastic process

Zhongming Chen^1, and
Liqun Qi^2,

1.
School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071
2.
Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

Received: October 31, 2014

Revised: September 30, 2015

Published: September 2016

Abstract Related Papers Cited by

Abstract

Circulant tensors naturally arise from stochastic process and spectral hypergraph theory. The joint moments of stochastic processes are symmetric circulant tensors. The adjacency, Laplacian and signless Laplacian tensors of circulant hypergraphs are also symmetric circulant tensors. The adjacency, Laplacian and signless Laplacian tensors of directed circulant hypergraphs are circulant tensors, but they are not symmetric in general. In this paper, we study spectral properties of circulant tensors and their applications in spectral hypergraph theory and stochastic process. We show that in certain cases, the largest H-eigenvalue of a circulant tensor can be explicitly identified. In particular, the largest H-eigenvalue of a nonnegative circulant tensor can be explicitly identified. This confirms the results in circulant hypergraphs and directed circulant hypergraphs. We prove that an even order circulant B$_0$ tensor is always positive semi-definite. This shows that the Laplacian tensor and the signless Laplacian tensor of a directed circulant even-uniform hypergraph are positive semi-definite. If a stochastic process is $m$th order stationary, where $m$ is even, then its $m$th order moment, which is a circulant tensor, must be positive semi-definite. In this paper, we give various conditions for an even order circulant tensor to be positive semi-definite.

Keywords:

Mathematics Subject Classification: Primary: 15A18, 15A69.

Citation:

Related Papers

Cited by

References

[1]	R. Badeau and R. Boyer, Fast multilinear singular value decomposition for structured tensors, SIAM J. Matrix Anal. Appl., 30 (2008), 1008-1021.doi: 10.1137/060655936.
[2]	K. C. Chang, K. Pearson and T. Zhang, On eigenvalue problems of real symmetric tensors, J. Math. Anal. Appl., 350 (2009), 416-422.doi: 10.1016/j.jmaa.2008.09.067.
[3]	Y. Chen, Y. Dai, D. Han and W. Sun, Positive semidefinite generalized diffusion tensor imaging via quadratic semidefinite programming, SIAM J. Imaging Sci., 6 (2013), 1531-1552.doi: 10.1137/110843526.
[4]	J. Cooper and A. Dutle, Spectra of uniform hypergraphs, Linear Algebra Appl., 436 (2012), 3268-3292.doi: 10.1016/j.laa.2011.11.018.
[5]	P. Davis, Circulant Matrices, Wiley, New York, 1979.
[6]	A. Ducournau and A. Bretto, Random walks in directed hypergraphs and application to semi-supervised image segmentation, Computer Vision and Image Understanding, 120 (2014), 91-102.doi: 10.1016/j.cviu.2013.10.012.
[7]	G. Gallo, G. Longo, S. Pallottino and S. Nguyen, Directed hypergraphs and applications, Discrete Appl. Math., 42 (1993), 177-201.doi: 10.1016/0166-218X(93)90045-P.
[8]	D. Han and X. Yuan, A note on the alternating direction method of multipliers, J. Optim. Theory Appl., 155 (2012), 227-238.doi: 10.1007/s10957-012-0003-z.
[9]	R. Horn and C. Johnson, Matrix Ananlysis, Cambridge University Press, Cambridge, UK, 1990.
[10]	S. Hu, Z.-H. Huang, H.-Y. Ni and L. Qi, Positive definiteness of diffusion kurtosis imaging, Inverse Probl. Imaging, 6 (2012), 57-75.doi: 10.3934/ipi.2012.6.57.
[11]	S. Hu and L. Qi, Algebraic connectivity of an even uniform hypergraph, J. Comb. Optim., 24 (2012), 564-579.doi: 10.1007/s10878-011-9407-1.
[12]	S. Hu and L. Qi, The eigenvectors associated with the zero eigenvalues of the Laplacian and signless Laplacian tensors of a uniform hypergraph, Discrete Appl. Math., 169 (2014), 140-151.doi: 10.1016/j.dam.2013.12.024.
[13]	S. Hu and L. Qi, The Laplacian of a uniform hypergraph, J. Comb. Optim., 29 (2015), 331-366.doi: 10.1007/s10878-013-9596-x.
[14]	S. Hu, L. Qi and J.-Y. Shao, Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues, Linear Algebra Appl., 439 (2013), 2980-2998.doi: 10.1016/j.laa.2013.08.028.
[15]	B. Jiang, S. Ma and S. Zhang, Alternating direction method of multipliers for real and complex polynomial optimization models, Optimization, 63 (2014), 883-898.doi: 10.1080/02331934.2014.895901.
[16]	G. Li, L. Qi and G. Yu, The $Z$-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory, Numer. Linear Algebra Appl., 20 (2013), 1001-1029.doi: 10.1002/nla.1877.
[17]	K. Li and L. Wang, A polynomial time approximation scheme for embedding a directed hypergraph on a ring, Inform. Process. Lett., 97 (2006), 203-207.doi: 10.1016/j.ipl.2005.10.008.
[18]	H. Z. Luo, H. X. Wu and G. T. Chen, On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming, J. Global Optim., 54 (2012), 599-618.doi: 10.1007/s10898-011-9779-x.
[19]	K. J. Pearson and T. Zhang, On spectral hypergraph theory of the adjacency tensor, Graphs Combin., 30 (2014), 1233-1248.doi: 10.1007/s00373-013-1340-x.
[20]	J. M. Peña, A class of $P$-matrices with applications to the localization of the eigenvalues of a real matrix, SIAM J. Matrix Anal. Appl., 22 (2001), 1027-1037 (electronic).doi: 10.1137/S0895479800370342.
[21]	L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324.doi: 10.1016/j.jsc.2005.05.007.
[22]	L. Qi, $H^+$-eigenvalues of Laplacian and signless Laplacian tensors, Commun. Math. Sci., 12 (2014), 1045-1064.doi: 10.4310/CMS.2014.v12.n6.a3.
[23]	L. Qi, J.-Y. Shao and Q. Wang, Regular uniform hypergraphs, $s$-cycles, $s$-paths and their largest Laplacian H-eigenvalues, Linear Algebra Appl., 443 (2014), 215-227.doi: 10.1016/j.laa.2013.11.008.
[24]	L. Qi and Y. Song, An even order symmetric B tensor is positive definite, Linear Algebra Appl., 457 (2014), 303-312.doi: 10.1016/j.laa.2014.05.026.
[25]	L. Qi, G. Yu and E. X. Wu, Higher order positive semidefinite diffusion tensor imaging, SIAM J. Imaging Sci., 3 (2010), 416-433.doi: 10.1137/090755138.
[26]	L. Qi, G. Yu and Y. Xu, Nonnegative diffusion orientation distribution function, J. Math. Imaging Vision, 45 (2013), 103-113.doi: 10.1007/s10851-012-0346-y.
[27]	M. Rezghi and L. Eldén, Diagonalization of tensors with circulant structure, Linear Algebra Appl., 435 (2011), 422-447.doi: 10.1016/j.laa.2010.03.032.
[28]	H. Tijms, A First Course in Stochastic Models, John Wiley, New York, 2003.doi: 10.1002/047001363X.
[29]	Wikipedia, Circulant matrix - wikipedia, the free encyclopedia, 2015, https://en.wikipedia.org/wiki/Circulant_matrix, [Online; accessed 19-July-2015].
[30]	J. Xie and A. Chang, H-eigenvalues of signless Laplacian tensor for an even uniform hypergraph, Front. Math. China, 8 (2013), 107-127.doi: 10.1007/s11464-012-0266-6.
[31]	J. Xie and A. Chang, On the Z-eigenvalues of the signless Laplacian tensor for an even uniform hypergraph, Numer. Linear Algebra Appl., 20 (2013), 1030-1045.doi: 10.1002/nla.1910.