Circulant tensors with applications to spectral hypergraph theory and stochastic process

Zhongming  Chen; Liqun Qi

doi:10.3934/jimo.2016.12.1227

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 & 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]	Chaoqian Li, Yajun Liu, Yaotang Li. Note on $ Z $-eigenvalue inclusion theorems for tensors. Journal of Industrial & Management Optimization, 2021, 17 (2) : 687-693. doi: 10.3934/jimo.2019129
[2]	Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617
[3]	Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021035
[4]	Horst R. Thieme. Remarks on resolvent positive operators and their perturbation. Discrete & Continuous Dynamical Systems - A, 1998, 4 (1) : 73-90. doi: 10.3934/dcds.1998.4.73
[5]	Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810
[6]	Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109
[7]	Zaihong Wang, Jin Li, Tiantian Ma. An erratum note on the paper: Positive periodic solution for Brillouin electron beam focusing system. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1995-1997. doi: 10.3934/dcdsb.2013.18.1995
[8]	Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

2019 Impact Factor: 1.366

American Institute of Mathematical Sciences

Circulant tensors with applications to spectral hypergraph theory and stochastic process

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Circulant tensors with applications to spectral hypergraph theory and stochastic process

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors