Circulant tensors with applications to spectral hypergraph theory and stochastic process

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

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

Circulant tensors with applications to spectral hypergraph theory and stochastic process

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 & 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. doi: 10.1137/060655936. Google Scholar
[2]	K. C. Chang, K. Pearson and T. Zhang, On eigenvalue problems of real symmetric tensors,, J. Math. Anal. Appl., 350 (2009), 416. doi: 10.1016/j.jmaa.2008.09.067. Google Scholar
[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. doi: 10.1137/110843526. Google Scholar
[4]	J. Cooper and A. Dutle, Spectra of uniform hypergraphs,, Linear Algebra Appl., 436 (2012), 3268. doi: 10.1016/j.laa.2011.11.018. Google Scholar
[5]	P. Davis, Circulant Matrices,, Wiley, (1979). Google Scholar
[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. doi: 10.1016/j.cviu.2013.10.012. Google Scholar
[7]	G. Gallo, G. Longo, S. Pallottino and S. Nguyen, Directed hypergraphs and applications,, Discrete Appl. Math., 42 (1993), 177. doi: 10.1016/0166-218X(93)90045-P. Google Scholar
[8]	D. Han and X. Yuan, A note on the alternating direction method of multipliers,, J. Optim. Theory Appl., 155 (2012), 227. doi: 10.1007/s10957-012-0003-z. Google Scholar
[9]	R. Horn and C. Johnson, Matrix Ananlysis,, Cambridge University Press, (1990). Google Scholar
[10]	S. Hu, Z.-H. Huang, H.-Y. Ni and L. Qi, Positive definiteness of diffusion kurtosis imaging,, Inverse Probl. Imaging, 6 (2012), 57. doi: 10.3934/ipi.2012.6.57. Google Scholar
[11]	S. Hu and L. Qi, Algebraic connectivity of an even uniform hypergraph,, J. Comb. Optim., 24 (2012), 564. doi: 10.1007/s10878-011-9407-1. Google Scholar
[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. doi: 10.1016/j.dam.2013.12.024. Google Scholar
[13]	S. Hu and L. Qi, The Laplacian of a uniform hypergraph,, J. Comb. Optim., 29 (2015), 331. doi: 10.1007/s10878-013-9596-x. Google Scholar
[14]	S. Hu, L. Qi and J.-Y. Shao, Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues,, Linear Algebra Appl., 439 (2013), 2980. doi: 10.1016/j.laa.2013.08.028. Google Scholar
[15]	B. Jiang, S. Ma and S. Zhang, Alternating direction method of multipliers for real and complex polynomial optimization models,, Optimization, 63 (2014), 883. doi: 10.1080/02331934.2014.895901. Google Scholar
[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. doi: 10.1002/nla.1877. Google Scholar
[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. doi: 10.1016/j.ipl.2005.10.008. Google Scholar
[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. doi: 10.1007/s10898-011-9779-x. Google Scholar
[19]	K. J. Pearson and T. Zhang, On spectral hypergraph theory of the adjacency tensor,, Graphs Combin., 30 (2014), 1233. doi: 10.1007/s00373-013-1340-x. Google Scholar
[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. doi: 10.1137/S0895479800370342. Google Scholar
[21]	L. Qi, Eigenvalues of a real supersymmetric tensor,, J. Symbolic Comput., 40 (2005), 1302. doi: 10.1016/j.jsc.2005.05.007. Google Scholar
[22]	L. Qi, $H^+$-eigenvalues of Laplacian and signless Laplacian tensors,, Commun. Math. Sci., 12 (2014), 1045. doi: 10.4310/CMS.2014.v12.n6.a3. Google Scholar
[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. doi: 10.1016/j.laa.2013.11.008. Google Scholar
[24]	L. Qi and Y. Song, An even order symmetric B tensor is positive definite,, Linear Algebra Appl., 457 (2014), 303. doi: 10.1016/j.laa.2014.05.026. Google Scholar
[25]	L. Qi, G. Yu and E. X. Wu, Higher order positive semidefinite diffusion tensor imaging,, SIAM J. Imaging Sci., 3 (2010), 416. doi: 10.1137/090755138. Google Scholar
[26]	L. Qi, G. Yu and Y. Xu, Nonnegative diffusion orientation distribution function,, J. Math. Imaging Vision, 45 (2013), 103. doi: 10.1007/s10851-012-0346-y. Google Scholar
[27]	M. Rezghi and L. Eldén, Diagonalization of tensors with circulant structure,, Linear Algebra Appl., 435 (2011), 422. doi: 10.1016/j.laa.2010.03.032. Google Scholar
[28]	H. Tijms, A First Course in Stochastic Models,, John Wiley, (2003). doi: 10.1002/047001363X. Google Scholar
[29]	Wikipedia, Circulant matrix - wikipedia, the free encyclopedia, 2015,, , (). Google Scholar
[30]	J. Xie and A. Chang, H-eigenvalues of signless Laplacian tensor for an even uniform hypergraph,, Front. Math. China, 8 (2013), 107. doi: 10.1007/s11464-012-0266-6. Google Scholar
[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. doi: 10.1002/nla.1910. Google Scholar

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. doi: 10.1137/060655936. Google Scholar
[2]	K. C. Chang, K. Pearson and T. Zhang, On eigenvalue problems of real symmetric tensors,, J. Math. Anal. Appl., 350 (2009), 416. doi: 10.1016/j.jmaa.2008.09.067. Google Scholar
[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. doi: 10.1137/110843526. Google Scholar
[4]	J. Cooper and A. Dutle, Spectra of uniform hypergraphs,, Linear Algebra Appl., 436 (2012), 3268. doi: 10.1016/j.laa.2011.11.018. Google Scholar
[5]	P. Davis, Circulant Matrices,, Wiley, (1979). Google Scholar
[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. doi: 10.1016/j.cviu.2013.10.012. Google Scholar
[7]	G. Gallo, G. Longo, S. Pallottino and S. Nguyen, Directed hypergraphs and applications,, Discrete Appl. Math., 42 (1993), 177. doi: 10.1016/0166-218X(93)90045-P. Google Scholar
[8]	D. Han and X. Yuan, A note on the alternating direction method of multipliers,, J. Optim. Theory Appl., 155 (2012), 227. doi: 10.1007/s10957-012-0003-z. Google Scholar
[9]	R. Horn and C. Johnson, Matrix Ananlysis,, Cambridge University Press, (1990). Google Scholar
[10]	S. Hu, Z.-H. Huang, H.-Y. Ni and L. Qi, Positive definiteness of diffusion kurtosis imaging,, Inverse Probl. Imaging, 6 (2012), 57. doi: 10.3934/ipi.2012.6.57. Google Scholar
[11]	S. Hu and L. Qi, Algebraic connectivity of an even uniform hypergraph,, J. Comb. Optim., 24 (2012), 564. doi: 10.1007/s10878-011-9407-1. Google Scholar
[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. doi: 10.1016/j.dam.2013.12.024. Google Scholar
[13]	S. Hu and L. Qi, The Laplacian of a uniform hypergraph,, J. Comb. Optim., 29 (2015), 331. doi: 10.1007/s10878-013-9596-x. Google Scholar
[14]	S. Hu, L. Qi and J.-Y. Shao, Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues,, Linear Algebra Appl., 439 (2013), 2980. doi: 10.1016/j.laa.2013.08.028. Google Scholar
[15]	B. Jiang, S. Ma and S. Zhang, Alternating direction method of multipliers for real and complex polynomial optimization models,, Optimization, 63 (2014), 883. doi: 10.1080/02331934.2014.895901. Google Scholar
[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. doi: 10.1002/nla.1877. Google Scholar
[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. doi: 10.1016/j.ipl.2005.10.008. Google Scholar
[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. doi: 10.1007/s10898-011-9779-x. Google Scholar
[19]	K. J. Pearson and T. Zhang, On spectral hypergraph theory of the adjacency tensor,, Graphs Combin., 30 (2014), 1233. doi: 10.1007/s00373-013-1340-x. Google Scholar
[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. doi: 10.1137/S0895479800370342. Google Scholar
[21]	L. Qi, Eigenvalues of a real supersymmetric tensor,, J. Symbolic Comput., 40 (2005), 1302. doi: 10.1016/j.jsc.2005.05.007. Google Scholar
[22]	L. Qi, $H^+$-eigenvalues of Laplacian and signless Laplacian tensors,, Commun. Math. Sci., 12 (2014), 1045. doi: 10.4310/CMS.2014.v12.n6.a3. Google Scholar
[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. doi: 10.1016/j.laa.2013.11.008. Google Scholar
[24]	L. Qi and Y. Song, An even order symmetric B tensor is positive definite,, Linear Algebra Appl., 457 (2014), 303. doi: 10.1016/j.laa.2014.05.026. Google Scholar
[25]	L. Qi, G. Yu and E. X. Wu, Higher order positive semidefinite diffusion tensor imaging,, SIAM J. Imaging Sci., 3 (2010), 416. doi: 10.1137/090755138. Google Scholar
[26]	L. Qi, G. Yu and Y. Xu, Nonnegative diffusion orientation distribution function,, J. Math. Imaging Vision, 45 (2013), 103. doi: 10.1007/s10851-012-0346-y. Google Scholar
[27]	M. Rezghi and L. Eldén, Diagonalization of tensors with circulant structure,, Linear Algebra Appl., 435 (2011), 422. doi: 10.1016/j.laa.2010.03.032. Google Scholar
[28]	H. Tijms, A First Course in Stochastic Models,, John Wiley, (2003). doi: 10.1002/047001363X. Google Scholar
[29]	Wikipedia, Circulant matrix - wikipedia, the free encyclopedia, 2015,, , (). Google Scholar
[30]	J. Xie and A. Chang, H-eigenvalues of signless Laplacian tensor for an even uniform hypergraph,, Front. Math. China, 8 (2013), 107. doi: 10.1007/s11464-012-0266-6. Google Scholar
[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. doi: 10.1002/nla.1910. Google Scholar

[1]	Haibin Chen, Liqun Qi. Positive definiteness and semi-definiteness of even order symmetric Cauchy tensors. Journal of Industrial & 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 & 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 & Management Optimization, 2017, 13 (5) : 1-11. 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]	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
[8]	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
[9]	Zhen Wang, Wei Wu. Bounds for the greatest eigenvalue of positive tensors. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1031-1039. doi: 10.3934/jimo.2014.10.1031
[10]	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
[11]	Yining Gu, Wei Wu. New bounds for eigenvalues of strictly diagonally dominant tensors. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 203-210. doi: 10.3934/naco.2018012
[12]	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
[13]	Lixing Han. An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 583-599. doi: 10.3934/naco.2013.3.583
[14]	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
[15]	Juan Meng, Yisheng Song. Upper bounds for Z$ _1 $-eigenvalues of generalized Hilbert tensors. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-8. doi: 10.3934/jimo.2018184
[16]	Li Li, Xinzhen Zhang, Zheng-Hai Huang, Liqun Qi. Test of copositive tensors. Journal of Industrial & Management Optimization, 2019, 15 (2) : 881-891. doi: 10.3934/jimo.2018075
[17]	Yining Gu, Wei Wu. Partially symmetric nonnegative rectangular tensors and copositive rectangular tensors. Journal of Industrial & Management Optimization, 2019, 15 (2) : 775-789. doi: 10.3934/jimo.2018070
[18]	Shenglong Hu, Zheng-Hai Huang, Hong-Yan Ni, Liqun Qi. Positive definiteness of Diffusion Kurtosis Imaging. Inverse Problems & Imaging, 2012, 6 (1) : 57-75. doi: 10.3934/ipi.2012.6.57
[19]	Chaoqian Li, Yaqiang Wang, Jieyi Yi, Yaotang Li. Bounds for the spectral radius of nonnegative tensors. Journal of Industrial & Management Optimization, 2016, 12 (3) : 975-990. doi: 10.3934/jimo.2016.12.975
[20]	Géry de Saxcé, Claude Vallée. Structure of the space of 2D elasticity tensors. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1525-1537. doi: 10.3934/dcdss.2013.6.1525

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences