Circulant tensors with applications to spectral hypergraph theory and stochastic process

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

October 2016, 12(4): 1227-1247. doi: 10.3934/jimo.2016.12.1227

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, China
2.	Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

Received November 2014 Revised October 2015 Published January 2016

Abstract
Related Papers

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: eigenvalues of tensors, Circulant tensors, directed circulant hypergraphs, circulant hypergraphs, positive semi-definiteness..

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

Citation: Zhongming Chen, Liqun Qi. Circulant tensors with applications to spectral hypergraph theory and stochastic process. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1227-1247. doi: 10.3934/jimo.2016.12.1227

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.

show all references

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.

[1]	Haibin Chen, Liqun Qi. Positive definiteness and semi-definiteness of even order symmetric Cauchy tensors. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1263-1274. doi: 10.3934/jimo.2015.11.1263
[2]	Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems and Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901
[3]	Yi Xu, Jinjie Liu, Liqun Qi. A new class of positive semi-definite tensors. Journal of Industrial and Management Optimization, 2020, 16 (2) : 933-943. doi: 10.3934/jimo.2018186
[4]	T. Aaron Gulliver, Masaaki Harada. On the performance of optimal double circulant even codes. Advances in Mathematics of Communications, 2017, 11 (4) : 767-775. doi: 10.3934/amc.2017056
[5]	Suat Karadeniz, Bahattin Yildiz. Double-circulant and bordered-double-circulant constructions for self-dual codes over $R_2$. Advances in Mathematics of Communications, 2012, 6 (2) : 193-202. doi: 10.3934/amc.2012.6.193
[6]	Steven T. Dougherty, Jon-Lark Kim, Patrick Solé. Double circulant codes from two class association schemes. Advances in Mathematics of Communications, 2007, 1 (1) : 45-64. doi: 10.3934/amc.2007.1.45
[7]	Minjia Shi, Daitao Huang, Lin Sok, Patrick Solé. Double circulant self-dual and LCD codes over Galois rings. Advances in Mathematics of Communications, 2019, 13 (1) : 171-183. doi: 10.3934/amc.2019011
[8]	Samuel T. Blake, Andrew Z. Tirkel. A multi-dimensional block-circulant perfect array construction. Advances in Mathematics of Communications, 2017, 11 (2) : 367-371. doi: 10.3934/amc.2017030
[9]	Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[10]	Zhen Wang, Wei Wu. Bounds for the greatest eigenvalue of positive tensors. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1031-1039. doi: 10.3934/jimo.2014.10.1031
[11]	Yining Gu, Wei Wu. New bounds for eigenvalues of strictly diagonally dominant tensors. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 203-210. doi: 10.3934/naco.2018012
[12]	Yannan Chen, Jingya Chang. A trust region algorithm for computing extreme eigenvalues of tensors. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 475-485. doi: 10.3934/naco.2020046
[13]	Ken Saito. Self-dual additive $ \mathbb{F}_4 $-codes of lengths up to 40 represented by circulant graphs. Advances in Mathematics of Communications, 2019, 13 (2) : 213-220. doi: 10.3934/amc.2019014
[14]	Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077
[15]	Joe Gildea, Abidin Kaya, Adam Michael Roberts, Rhian Taylor, Alexander Tylyshchak. New self-dual codes from $ 2 \times 2 $ block circulant matrices, group rings and neighbours of neighbours. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021039
[16]	Christopher Griffin, James Fan. Control problems with vanishing Lie Bracket arising from complete odd circulant evolutionary games. Journal of Dynamics and Games, 2022, 9 (2) : 165-189. doi: 10.3934/jdg.2022002
[17]	Lixing Han. An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 583-599. doi: 10.3934/naco.2013.3.583
[18]	T. Aaron Gulliver, Masaaki Harada, Hiroki Miyabayashi. Double circulant and quasi-twisted self-dual codes over $\mathbb F_5$ and $\mathbb F_7$. Advances in Mathematics of Communications, 2007, 1 (2) : 223-238. doi: 10.3934/amc.2007.1.223
[19]	Juan Meng, Yisheng Song. Upper bounds for Z$ _1 $-eigenvalues of generalized Hilbert tensors. Journal of Industrial and Management Optimization, 2020, 16 (2) : 911-918. doi: 10.3934/jimo.2018184
[20]	Li Li, Xinzhen Zhang, Zheng-Hai Huang, Liqun Qi. Test of copositive tensors. Journal of Industrial and Management Optimization, 2019, 15 (2) : 881-891. doi: 10.3934/jimo.2018075

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Zhongming Chen Liqun Qi
on Google Scholar
Zhongming Chen Liqun Qi

[Back to Top]