BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Liqun Qi

Liqun Qi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.SPmath.OCmath.NAmath.CONumerical Analysismath-phmath.MPquant-phComputer Visionmath.RAeess.IVmath.CVmath.GMSystems and Control

Catalog footprint

What is connected

85works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

85 published item(s)

preprint2022arXiv

"Sparse + Low-Rank'' Tensor Completion Approach for Recovering Images and Videos

Recovering color images and videos from highly undersampled data is a fundamental and challenging task in face recognition and computer vision. By the multi-dimensional nature of color images and videos, in this paper, we propose a novel tensor completion approach, which is able to efficiently explore the sparsity of tensor data under the discrete cosine transform (DCT). Specifically, we introduce two ``sparse + low-rank'' tensor completion models as well as two implementable algorithms for finding their solutions. The first one is a DCT-based sparse plus weighted nuclear norm induced low-rank minimization model. The second one is a DCT-based sparse plus $p$-shrinking mapping induced low-rank optimization model. Moreover, we accordingly propose two implementable augmented Lagrangian-based algorithms for solving the underlying optimization models. A series of numerical experiments including color image inpainting and video data recovery demonstrate that our proposed approach performs better than many existing state-of-the-art tensor completion methods, especially for the case when the ratio of missing data is high.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Low Rank Approximation of Dual Complex Matrices

Dual complex numbers can represent rigid body motion in 2D spaces. Dual complex matrices are linked with screw theory, and have potential applications in various areas. In this paper, we study low rank approximation of dual complex matrices. We define $2$-norm for dual complex vectors, and Frobenius norm for dual complex matrices. These norms are nonnegative dual numbers. We establish the unitary invariance property of dual complex matrices. We study eigenvalues of square dual complex matrices, and show that an $n \times n$ dual complex Hermitian matrix has exactly $n$ eigenvalues, which are dual numbers. We present a singular value decomposition (SVD) theorem for dual complex matrices, define ranks and appreciable ranks for dual complex matrices, and study their properties. We establish an Eckart-Young like theorem for dual complex matrices, and present an algorithm framework for low rank approximation of dual complex matrices via truncated SVD. The SVD of dual complex matrices also provides a basic tool for Principal Component Analysis (PCA) via these matrices. Numerical experiments are reported.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-mode Tensor Train Factorization with Spatial-spectral Regularization for Remote Sensing Images Recovery

Tensor train (TT) factorization and corresponding TT rank, which can well express the low-rankness and mode correlations of higher-order tensors, have attracted much attention in recent years. However, TT factorization based methods are generally not sufficient to characterize low-rankness along each mode of third-order tensor. Inspired by this, we generalize the tensor train factorization to the mode-k tensor train factorization and introduce a corresponding multi-mode tensor train (MTT) rank. Then, we proposed a novel low-MTT-rank tensor completion model via multi-mode TT factorization and spatial-spectral smoothness regularization. To tackle the proposed model, we develop an efficient proximal alternating minimization (PAM) algorithm. Extensive numerical experiment results on visual data demonstrate that the proposed MTTD3R method outperforms compared methods in terms of visual and quantitative measures.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Standard Dual Quaternion Optimization and Its Applications in Hand-Eye Calibration and SLAM

Several common dual quaternion functions, such as the power function, the magnitude function, the $2$-norm function and the $k$th largest eigenvalue of a dual quaternion Hermitian matrix, are standard dual quaternion functions, i.e., the standard parts of their function values depend upon only the standard parts of their dual quaternion variables. Furthermore, the sum, product, minimum, maximum and composite functions of two standard dual functions, the logarithm and the exponential of standard unit dual quaternion functions, are still standard dual quaternion functions. On the other hand, the dual quaternion optimization problem, where objective and constraint function values are dual numbers but variables are dual quaternions, naturally arises from applications. We show that to solve an equality constrained dual quaternion optimization problem, we only need to solve two quaternion optimization problems. If the involved dual quaternion functions are all standard, the optimization problem is called a standard dual quaternion optimization problem, and some better results hold. Then, we show that the dual quaternion optimization problems arising from the hand-eye calibration problem and the simultaneous localization and mapping (SLAM) problem are equality constrained standard dual quaternion optimization problems.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

T-Quadratic Forms and Spectral Analysis of T-Symmetric Tensors

An $n \times n \times p$ tensor is called a T-square tensor. It arises from many applications, such as the image feature extraction problem and the multi-view clustering problem. We may symmetrize a T-square tensor to a T-symmetric tensor. For each T-square tensor, we define a T-quadratic form, whose variable is an $n \times p$ matrix, and whose value is a $p$-dimensional vector. We define eigentuples and eigenmatrices for T-square tensors. We show that a T-symmetric tensor has unique largest and smallest eigentuples, and a T-quadratic form is positive semi-definite (definite) if and only if its smallest eigentuple is nonnegative (positive). The relation between the eigen-decomposition of T-symmetric tensors, and the TSVD of general third order tensors are also studied.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

T-Singular Values and T-Sketching for Third Order Tensors

Based upon the T-SVD (tensor SVD) of third order tensors, introduced by Kilmer and her collaborators, we define T-singular values of third order tensors. T-singular values of third order tensors are nonnegative scalars. The number of nonzero T-singular values is the tensor tubal rank of the tensor. We then use T-singular values to define the tail energy of a third order tensor, and apply it to the error estimation of a tensor sketching algorithm for low rank tensor approximation. Numerical experiments on real world data show that our algorithm is efficient.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Parallelizable Method for Missing Internet Traffic Tensor Data

Recovery of internet network traffic data from incomplete observed data is an important issue in internet network engineering and management. In this paper, by fully combining the temporal stability and periodicity features in internet traffic data, a new separable optimization model for internet data recovery is proposed, which is based upon the t-product and the rapid discrete Fourier transform of tensors. Moreover, by using generalized inverse matrices, an easy-to-operate and effective algorithm is proposed. In theory, we prove that under suitable conditions, every accumulation point of the sequence generated by the proposed algorithm is a stationary point of the established model. Numerical simulation results carried on the widely used real-world internet network datasets, show good performance of the proposed method. In the case of moderate sampling rates, the proposed method works very well, its effect is better than that of some existing internet traffic data recovery methods in the literature. The separable structural features presented in the optimization model provide the possibility to design more efficient parallel algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Polynomially Irreducible Functional Basis of Elasticity Tensors

Tensor function representation theory is an essential topic in both theoretical and applied mechanics. For the elasticity tensor, Olive, Kolev and Auffray (2017) proposed a minimal integrity basis of 297 isotropic invariants, which is also a functional basis. Inspired by Smith's and Zheng's works, we use a novel method in this article to seek a functional basis of the elasticity tensor, that contains less number of isotropic invariants. We achieve this goal by constructing 22 intermediate tensors consisting of 11 second order symmetrical tensors and 11 scalars via the irreducible decomposition of the elasticity tensor. Based on such intermediate tensors, we further generate 429 isotropic invariants which form a functional basis of the elasticity tensor. After eliminating all the invariants that are zeros or polynomials in the others, we finally obtain a functional basis of 251 isotropic invariants for the elasticity tensor.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Tensor Rank Theory and Maximum Full Rank Subtensors

A matrix always has a full rank submatrix such that the rank of this matrix is equal to the rank of that submatrix. This property is one of the corner stones of the matrix rank theory. We call this property the max-full-rank-submatrix property. Tensor ranks play a crucial role in low rank tensor approximation, tensor completion and tensor recovery. However, their theory is still not matured yet. Can we set an axiom system for tensor ranks? Can we extend the max-full-rank-submatrix property to tensors? We explore these in this paper. We first propose some axioms for tensor rank functions. Then we introduce proper tensor rank functions. The CP rank is a tensor rank function, but is not proper. There are two proper tensor rank functions, the max-Tucker rank and the submax-Tucker rank, which are associated with the Tucker decomposition. We define a partial order among tensor rank functions and show that there exists a unique smallest tensor rank function. We introduce the full rank tensor concept, and define the max-full-rank-subtensor property. We show the max-Tucker tensor rank function and the smallest tensor rank function have this property. We define the closure for an arbitrary proper tensor rank function, and show that it is still a proper tensor rank function and has the max-full-rank-subtensor property. An application of the submax-Tucker rank is also presented.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Copositivity of Three-Dimensional Symmetric Tensors

In this paper, we seek analytically checkable necessary and sufficient condition for copositivity of a three-dimensional symmetric tensor. We first show that for a general third order three-dimensional symmetric tensor, this means to solve a quartic equation and some quadratic equations. All of them can be solved analytically. Thus, we present an analytical way to check copositivity of a third order three dimensional symmetric tensor. Then, we consider a model of vacuum stability for $\mathbb{Z}_3$ scalar dark matter. This is a special fourth order three-dimensional symmetric tensor. We show that an analytically expressed necessary and sufficient condition for this model bounded from below can be given, by using a result given by Ulrich and Watson in 1994.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Positivity Conditions for Cubic, Quartic and Quintic Polynomials

We present a necessary and sufficient condition for a cubic polynomial to be positive for all positive reals. We identify the set where the cubic polynomial is nonnegative but not all positive for all positive reals, and explicitly give the points where the cubic polynomial attains zero. We then reformulate a necessary and sufficient condition for a quartic polynomial to be nonnegative for all positive reals. From this, we derive a necessary and sufficient condition for a quartic polynomial to be nonnegative and positive for all reals. Our condition explicitly exhibits the scope and role of some coefficients, and has strong geometrical meaning. In the interior of the nonnegativity region for all reals, there is an appendix curve. The discriminant is zero at the appendix, and positive in the other part of the interior of the nonnegativity region. By using the Sturm sequences, we present a necessary and sufficient condition for a quintic polynomial to be positive and nonnegative for all positive reals. We show that for polynomials of a fixed even degree higher than or equal to four, if they have no real roots, then their discriminants take the same sign, which depends upon that degree only, except on an appendix set of dimension lower by two, where the discriminants attain zero.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Triple Decomposition and Tensor Recovery of Third Order Tensors

In this paper, we introduce a new tensor decomposition for third order tensors, which decomposes a third order tensor to three third order low rank tensors in a balanced way. We call such a decomposition the triple decomposition, and the corresponding rank the triple rank. For a third order tensor, its CP decomposition can be regarded as a special case of its triple decomposition. The triple rank of a third order tensor is not greater than the middle value of the Tucker rank, and is strictly less than the middle value of the Tucker rank for an essential class of examples. These indicate that practical data can be approximated by low rank triple decomposition as long as it can be approximated by low rank CP or Tucker decomposition. This theoretical discovery is confirmed numerically. Numerical tests show that third order tensor data from practical applications such as internet traffic and video image are of low triple ranks. A tensor recovery method based on low rank triple decomposition is proposed. Its convergence and convergence rate are established. Numerical experiments confirm the efficiency of this method.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Analytical expressions of copositivity for 4th order symmetric tensors and applications

In particle physics, scalar potentials have to be bounded from below in order for the physics to make sense. The precise expressions of checking lower bound of scalar potentials are essential, which is an analytical expression of checking copositivity and positive definiteness of tensors given by such scalar potentials. Because the tensors given by general scalar potential are 4th order and symmetric, our work mainly focuses on finding precise expressions to test copositivity and positive definiteness of 4th order tensors in this paper. First of all, an analytically sufficient and necessary condition of positive definiteness is provided for 4th order 2 dimensional symmetric tensors. For 4th order 3 dimensional symmetric tensors, we give two analytically sufficient conditions of (strictly) cpositivity by using proof technique of reducing orders or dimensions of such a tensor. Furthermore, an analytically sufficient and necessary condition of copositivity is showed for 4th order 2 dimensional symmetric tensors. We also give several distinctly analytically sufficient conditions of (strict) copositivity for 4th order 2 dimensional symmetric tensors. Finally, we apply these results to check lower bound of scalar potentials, and to present analytical vacuum stability conditions for potentials of two real scalar fields and the Higgs boson.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Strictly semi-positive tensors and the boundedness of tensor complementarity problems

In this paper, we prove that all H$^+$(Z$^+$)-eigenvalues of each principal sub-tensor of a strictly semi-positive tensor are positive. We define two new constants associated with H$^+$(Z$^+$)eigenvalues of a strictly semi-positive tensor. With the help of these two constants, we establish upper bounds of an important quantity whose positivity is a necessary and sufficient condition for a general tensor to be a strictly semi-positive tensor. The monotonicity and boundedness of such a quantity are established too. Furthermore, we present global error bound analysis for a class of the nonlinear complementarity problem defined by a strictly semi-positive tensor.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computing Eigenvalues of Large Scale Sparse Tensors Arising from a Hypergraph

The spectral theory of higher-order symmetric tensors is an important tool to reveal some important properties of a hypergraph via its adjacency tensor, Laplacian tensor, and signless Laplacian tensor. Owing to the sparsity of these tensors, we propose an efficient approach to calculate products of these tensors and any vectors. Using the state-of-the-art L-BFGS approach, we develop a first-order optimization algorithm for computing H- and Z-eigenvalues of these large scale sparse tensors (CEST). With the aid of the Kurdyka-Łojasiewicz property, we prove that the sequence of iterates generated by CEST converges to an eigenvector of the tensor.When CEST is started from multiple randomly initial points, the resulting best eigenvalue could touch the extreme eigenvalue with a high probability. Finally, numerical experiments on small hypergraphs show that CEST is efficient and promising. Moreover, CEST is capable of computing eigenvalues of tensors corresponding to a hypergraph with millions of vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computing The Analytic Connectivity of A Uniform Hypergraph

The analytic connectivity, proposed as a substitute of the algebraic connectivity in the setting of hypergraphs, is an important quantity in spectral hypergraph theory. The definition of the analytic connectivity for a uniform hypergraph involves a series of optimization problems (POPs) associated with the Laplacian tensor of the hypergraph with nonnegativity constraints and a sphere constraint, which poses difficulties in computation. To reduce the involved computation, properties on the algebraic connectivity are further exploited, and several important structured uniform hypergraphs are shown to attain their analytic connectivities at vertices of the minimum degrees, hence admit a relatively less computation by solving a small number of POPs. To efficiently solve each involved POP, we propose a feasible trust region algorithm ({\tt FTR}) by exploiting their special structures. The global convergence of {\tt FTR} to the second-order necessary conditions points is established, and numerical results for both small and large size examples with comparison to other existing algorithms for POPs are reported to demonstrate the efficiency of our proposed algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Copositive Tensor Detection and Its Applications in Physics and Hypergraphs

Copositivity of tensors plays an important role in vacuum stability of a general scalar potential, polynomial optimization, tensor complementarity problem and tensor generalized eigenvalue complementarity problem. In this paper, we propose a new algorithm for testing copositivity of high order tensors, and then present applications of the algorithm in physics and hypergraphs. For this purpose, we first give several new conditions for copositivity of tensors based on the representative matrix of a simplex. Then a new algorithm is proposed with the help of a proper convex subcone of the copositive tensor cone, which is defined via the copositivity of Z-tensors. Furthermore, by considering a sum-of-squares program problem, we define two new subsets of the copositive tensor cone and discuss their convexity. As an application of the proposed algorithm, we prove that the coclique number of a uniform hypergraph is equivalent with an optimization problem over the completely positive tensor cone, which implies that the proposed algorithm can be applied to compute an upper bound of the coclique number of a uniform hypergraph. Then we study another application of the proposed algorithm on particle physics in testing copositivity of some potential fields. At last, various numerical examples are given to show the performance of the algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Copositivity Detection of Tensors: Theory and Algorithm

A symmetric tensor is called copositive if it generates a multivariate form taking nonnegative values over the nonnegative orthant. Copositive tensors have found important applications in polynomial optimization and tensor complementarity problems. In this paper, we consider copositivity detection of tensors both from theoretical and computational points of view. After giving several necessary conditions for copositive tensors, we propose several new criteria for copositive tensors based on the representation of the multivariate form in barycentric coordinates with respect to the standard simplex and simplicial partitions. It is verified that, as the partition gets finer and finer, the concerned conditions eventually capture all strictly copositive tensors. Based on the obtained theoretical results with the help of simplicial partitions, we propose a numerical method to judge whether a tensor is copositive or not. The preliminary numerical results confirm our theoretical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Finding the maximum eigenvalue of a class of tensors with applications in copositivity test and hypergraphs

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. This paper is devoted to a semi-definite program algorithm for computing the maximum $H$-eigenvalue of a class of tensors with sign structure called $W$-tensors. The class of $W$-tensors extends the well-studied nonnegative tensors and essentially nonnegative tensors, and covers some important tensors arising naturally from spectral hypergraph theory. Our algorithm is based on a new structured sums-of-squares (SOS) decomposition result for a nonnegative homogeneous polynomial induced by a $W$-tensor. This SOS decomposition enables us to show that computing the maximum $H$-eigenvalue of an even order symmetric $W$-tensor is equivalent to solving a semi-definite program, and hence can be accomplished in polynomial time. Numerical examples are given to illustrate that the proposed algorithm can be used to find maximum $H$-eigenvalue of an even order symmetric $W$-tensor with dimension up to $10,000$. We present two applications for our proposed algorithm: we first provide a polynomial time algorithm for computing the maximum $H$-eigenvalues of large size Laplacian tensors of hyper-stars and hyper-trees; second, we show that the proposed SOS algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended $Z$-tensors, whose order may be even or odd. Numerical experiments illustrate that our structured semi-definite program algorithm is effective and promising.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Formulating an $n$-person noncooperative game as a tensor complementarity problem

In this paper, we consider a class of $n$-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Infinite dimensional Hilbert tensors on spaces of analytic functions

In this paper, the $m-$order infinite dimensional Hilbert tensor (hypermatrix) is intrduced to define an $(m-1)$-homogeneous operator on the spaces of analytic functions, which is called Hilbert tensor operator. The boundedness of Hilbert tensor operator is presented on Bergman spaces $A^p$ ($p>2(m-1)$). On the base of the boundedness, two positively homogeneous operators are introduced to the spaces of analytic functions, and hence the upper bounds of norm of such two operators are found on Bergman spaces $A^p$ ($p>2(m-1)$). In particular, the norms of such two operators on Bergman spaces $A^{4(m-1)}$ are smaller than or equal to $π$ and $π^\frac1{m-1}$, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

New Classes of Positive Semi-Definite Hankel Tensors

A Hankel tensor is called a strong Hankel tensor if the Hankel matrix generated by its generating vector is positive semi-definite. It is known that an even order strong Hankel tensor is a sum-of-squares tensor, and thus a positive semi-definite tensor. The SOS decomposition of strong Hankel tensors has been well-studied by Ding, Qi and Wei \cite{DQW1}. On the other hand, very little is known for positive semi-definite Hankel tensors which are not strong Hankel tensors. In this paper, we study some classes of positive semi-definite Hankel tensors which are not strong Hankel tensors. These include truncated Hankel tensors and quasi-truncated Hankel tensors. Then we show that a strong Hankel tensor generated by an absoluate integrable function is always completely decomposable, and give a class of SOS Hankel tensors which are not completely decomposable.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Some properties and applications of odd-colorable $r$-hypergraphs

Let $r\geq2$ and $r$ be even. An $r$-hypergraph $G$ on $n$ vertices is called odd-colorable if there exists a map $φ:[n]\rightarrow\lbrack r]$ such that for any edge $\{j_{1},j_{2},\cdots,j_{r}\}$ of $G$, we have $φ(j_{1})+φ(j_{2})+\cdot\cdot\cdot+φ(j_{r})\equiv r/2(\operatorname{mod}r).$ In this paper, we first determine that, if $r=2^{q}(2t+1)$ and $n\ge 2^{q}(2^{q}-1)r$, then the maximum chromatic number in the class of the odd-colorable $r$-hypergraphs on $n$ vertices is $2^q$, which answers a question raised by V. Nikiforov recently in [V. Nikiforov, Hypergraphs and hypermatrices with symmetric spectrum. Prinprint available in arXiv:1605.00709v2, 10 May, 2016]. We also study some applications of the symmetric spectral property of the odd-colorable $r$-graphs given in that same paper by V. Nikiforov. We show that the Laplacian spectrum and the signless Laplacian spectrum of an $r$-hypergraph $G$ are equal if and only if $G$ is odd-colorable, and then study some further applications of these spectral properties.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The first few unicyclic and bicyclic hypergraphs with larger spectral radii

A connected $k$-uniform hypergraph with $n$ vertices and $m$ edges is called $r$-cyclic if $n=m(k-1)-r+1$. For $r=1$ or $2$, the hypergraph is simply called unicyclic or bicyclic. In this paper we investigate hypergraphs that attain larger spectral radii among all simple connected $k$-uniform unicyclic and bicyclic hypergraphs. Specifically, by using some edge operations, the formula on power hypergraph eigenvalues, the weighted incidence matrix and a result on linear unicyclic hypergraphs, we determined the first five hypergraphs with larger spectral radius among all unicyclic hypergraphs and the first three over all bicyclic hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Z-tensors and complementarity problems

Tensors are multidimensional analogs of matrices. In this paper, based on degree-theoretic ideas, we study homogeneous nonlinear complementarity problems induced by tensors. By specializing this to $Z$-tensors (which are tensors with non-positive off-diagonal entries), we describe various equivalent conditions for a $Z$-tensor to have the global solvability property. We show by an example that the global solvability need not imply unique solvability and provide a sufficient and easily checkable condition for unique solvability.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Necessary and Sufficient Condition for Existence of a Positive Perron Vector

In 1907, Oskar Perron showed that a positive square matrix has a unique largest positive eigenvalue with a positive eigenvector. This result was extended to irreducible nonnegative matrices by Geog Frobenius in 1912, and to irreducible nonnegative tensors and weakly irreducible nonnegative tensors recently. This result is a fundamental result in matrix theory and has found wide applications in probability theory, internet search engines, spectral graph and hypergraph theory, etc. In this paper, we give a necessary and sufficient condition for the existence of such a positive eigenvector, i.e., a positive Perron vector, for a nonnegative tensor. We show that every nonnegative tensor has a canonical nonnegative partition form, from which we introduce strongly nonnegative tensors. A tensor is called strongly nonnegative, if the spectral radius of each genuine weakly irreducible block is equal to the spectral radius of the tensor, which is strictly larger than the spectral radius of any other block. We prove that a nonnegative tensor has a positive Perron vector if and only if it is strongly nonnegative. The proof is nontrivial. Numerical results for finding a positive Perron vector are reported.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Semismooth Newton Method for Tensor Eigenvalue Complementarity Problem

In this paper, we consider the tensor eigenvalue complementarity problem which is closely related to the optimality conditions for polynomial optimization, as well as a class of differential inclusions with nonconvex processes. By introducing an NCP-function, we reformulate the tensor eigenvalue complementarity problem as a system of nonlinear equations. We show that this function is strongly semismooth but not differentiable, in which case the classical smoothing methods cannot apply. Furthermore, we propose a damped semismooth Newton method for tensor eigenvalue complementarity problem. A new procedure to evaluate an element of the generalized Jocobian is given, which turns out to be an element of the B-subdifferential under mild assumptions. As a result, the convergence of the damped semismooth Newton method is guaranteed by existing results. The numerical experiments also show that our method is efficient and promising.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Characterization Tensors of Balanced Incomplete Block Designs

Balanced incomplete block designs (BIBDs) have wide applications in engineering, business and sciences. In this paper, for each (v, k, λ)-BIBD, we construct a strongly symmetric k-th order v-dimensional tensor. We call such a strongly symmetric tensor the characterization tensor of that BIBD, and the absolute value tensor of the characterization tensor the signless characterization tensor of that BIBD. We study some spectral properties of such characterization tensors and signless characterization tensors. In this way, we provide a new tool to study BIBDs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Completely Positive Tensors and Multi-Hypergraphs

Completely positive graphs have been employed to associate with completely positive matrices for characterizing the intrinsic zero patterns. As tensors have been widely recognized as a higher-order extension of matrices, the multi-hypergraph, regarded as a generalization of graphs, is then introduced to associate with tensors for the study of complete positivity. To describe the dependence of the corresponding zero pattern for a special type of completely positive tensors--the $\{0,1\}$ completely positive tensors, the completely positive multi-hypergraph is defined. By characterizing properties of the associated multi-hypergraph, we provide necessary and sufficient conditions for any $(0,1)$ associated tensor to be $\{0,1\}$ completely positive. Furthermore, a necessary and sufficient condition for a uniform multi-hypergraph to be completely positive multi-hypergraph is proposed as well.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing Eigenvalues of Large Scale Hankel Tensors

Large scale tensors, including large scale Hankel tensors, have many applications in science and engineering. In this paper, we propose an inexact curvilinear search optimization method to compute Z- and H-eigenvalues of $m$th order $n$ dimensional Hankel tensors, where $n$ is large. Owing to the fast Fourier transform, the computational cost of each iteration of the new method is about $\mathcal{O}(mn\log(mn))$. Using the Cayley transform, we obtain an effective curvilinear search scheme. Then, we show that every limiting point of iterates generated by the new algorithm is an eigen-pair of Hankel tensors. Without the assumption of a second-order sufficient condition, we analyze the linear convergence rate of iterate sequence by the Kurdyka-Łojasiewicz property. Finally, numerical experiments for Hankel tensors, whose dimension may up to one million, are reported to show the efficiency of the proposed curvilinear search method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Doubly Nonnegative Tensors, Completely Positive Tensors and Applications

The concept of double nonnegativity of matrices is generalized to doubly nonnegative tensors by means of the nonnegativity of all entries and $H$-eigenvalues. This generalization is defined for tensors of any order (even or odd), while it reduces to the class of nonnegative positive semidefinite tensors in the even order case. We show that many nonnegative structured tensors, which are positive semidefinite in the even order case, are indeed doubly nonnegative as well in the odd order case. As an important subclass of doubly nonnegative tensors, the completely positive tensors are further studied. By using dominance properties for completely positive tensors, we can easily exclude some doubly nonnegative tensors, such as the signless Laplacian tensor of a nonempty $m$-uniform hypergraph with $m\geq 3$, from the class of completely positive tensors. Properties of the doubly nonnegative tensor cone and the completely positive tensor cone are established. Their relation and difference are discussed. These show us a different phenomenon comparing to the matrix case. By employing the proposed properties, more subclasses of these two types of tensors are identified. Particularly, all positive Cauchy tensors with any order are shown to be completely positive. This gives an easily constructible subclass of completely positive tensors, which is significant for the study of completely positive tensor decomposition. A preprocessed Fan-Zhou algorithm is proposed which can efficiently verify the complete positivity of nonnegative symmetric tensors. We also give the solution analysis of tensor complementarity problems with the strongly doubly nonnegative tensor structure.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Error analysis of approximation algorithm for standard bi-quadratic programming

We consider the problem of approximately solving a standard bi-quadratic programming (StBQP), which is NP-hard. After reformulating the original problem as an equivalent copositive tensor programming, we show how to approximate the optimal solution by approximating the cone of copositive tensors via a serial polyhedral cones. The established quality of approximation shows that, a polynomial time approximation scheme (PTAS) for solving StBQP exists and can be extended to solving standard multi-quadratic programming. Some numerical examples are provided to illustrate our approach.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Further Results on Cauchy Tensors and Hankel Tensors

In this article, we present various new results on Cauchy tensors and Hankel tensors. { We first introduce the concept of generalized Cauchy tensors which extends Cauchy tensors in the current literature, and provide several conditions characterizing positive semi-definiteness of generalized Cauchy tensors with nonzero entries.} As a consequence, we show that Cauchy tensors are positive semi-definite if and only if they are SOS (Sum-of-squares) tensors.} Furthermore, we prove that all positive semi-definite Cauchy tensors are completely positive tensors, which means every positive semi-definite Cauchy tensor can be decomposed { as} the sum of nonnegative rank-1 tensors. We also establish that all the H-eigenvalues of nonnegative Cauchy tensors are nonnegative. Secondly, we present new mathematical properties of Hankel tensors. { We prove that an even order Hankel tensor is Vandermonde positive semi-definite if and only if its associated plane tensor is positive semi-definite. We also show that, if the Vandermonde rank of a Hankel tensor $\mathcal{A}$ is less than the dimension of the underlying space, then positive semi-definiteness of $\mathcal{A}$ is equivalent to the fact that $\mathcal{A}$ is a complete Hankel tensor, and so, is further equivalent to the SOS property of $\mathcal{A}$. Lastly, we introduce a new structured tensor called Cauchy-Hankel tensors, which is a special case of Cauchy tensors and Hankel tensors simultaneously.} Sufficient and necessary conditions are established for an even order Cauchy-Hankel tensor to be positive definite. Final remarks are listed at the end of the paper.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Higher-degree eigenvalue complementarity problems for tensors

In this paper, we introduce a unified framework of Tensor Higher-Degree Eigenvalue Complementarity Problem (THDEiCP), which goes beyond the framework of the typical Quadratic Eigenvalue Complementarity Problem (QEiCP) for matrices. First, we study some topological properties of higher-degree cone eigenvalues of tensors. Based upon the symmetry assumptions on the underlying tensors, we then reformulate THDEiCP as a weakly coupled homogeneous polynomial optimization problem, which might be greatly helpful for designing implementable algorithms to solve the problem under consideration numerically. As more general theoretical results, we present the results concerning existence of solutions of THDEiCP without symmetry conditions. Finally, we propose an easily implementable algorithm to solve THDEiCP, and report some computational results.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Inheritance Properties and Sum-of-Squares Decomposition of Hankel Tensors: Theory and Algorithms

In this paper, we show that if a lower-order Hankel tensor is positive semi-definite (or positive definite, or negative semi-definite, or negative definite, or SOS), then its associated higher-order Hankel tensor with the same generating vector, where the higher order is a multiple of the lower order, is also positive semi-definite (or positive definite, or negative semi-definite, or negative definite, or SOS, respectively). Furthermore, in this case, the extremal H-eigenvalues of the higher order tensor are bounded by the extremal H-eigenvalues of the lower order tensor, multiplied with some constants. Based on this inheritance property, we give a concrete sum-of-squares decomposition for each strong Hankel tensor. Then we prove the second inheritance property of Hankel tensors, i.e., a Hankel tensor has no negative (or non-positive, or positive, or nonnegative) H-eigenvalues if the associated Hankel matrix of that Hankel tensor has no negative (or non-positive, or positive, or nonnegative, respectively) eigenvalues. In this case, the extremal H-eigenvalues of the Hankel tensor are also bounded by the extremal eigenvalues of the associated Hankel matrix, multiplied with some constants. The third inheritance property of Hankel tensors is raised as a conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the cone eigenvalue complementarity problem for higher-order tensors

In this paper, we consider the tensor generalized eigenvalue complementarity problem (TGEiCP), which is an interesting generalization of matrix eigenvalue complementarity problem (EiCP). First, we given an affirmative result showing that TGEiCP is solvable and has at least one solution under some reasonable assumptions. Then, we introduce two optimization reformulations of TGEiCP, thereby beneficially establishing an upper bound of cone eigenvalues of tensors. Moreover, some new results concerning the bounds of number of eigenvalues of TGEiCP further enrich the theory of TGEiCP. Last but not least, an implementable projection algorithm for solving TGEiCP is also developed for the problem under consideration. As an illustration of our theoretical results, preliminary computational results are reported.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

P-Tensors, P$_0$-Tensors, and Tensor Complementarity Problem

The concepts of P- and P$_0$-matrices are generalized to P- and P$_0$-tensors of even and odd orders via homogeneous formulae. Analog to the matrix case, our P-tensor definition encompasses many important classes of tensors such as the positive definite tensors, the nonsingular M-tensors, the nonsingular H-tensors with positive diagonal entries, the strictly diagonally dominant tensors with positive diagonal entries, etc. As even-order symmetric PSD tensors are exactly even-order symmetric P$_0$-tensors, our definition of P$_0$-tensors, to some extent, can be regarded as an extension of PSD tensors for the odd-order case. Along with the basic properties of P- and P$_0$-tensors, the relationship among P$_0$-tensors and other extensions of PSD tensors are then discussed for comparison. Many structured tensors are also shown to be P- and P$_0$-tensors. As a theoretical application, the P-tensor complementarity problem is discussed and shown to possess a nonempty and compact solution set.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Positive Definite Tensors to Nonlinear Complementarity Problems

The main purpose of this note is to investigate some kinds of nonlinear complementarity problems (NCP). For the structured tensors, such as, symmetric positive definite tensors and copositive tensors, we derive the existence theorems on a solution of these kinds of nonlinear complementarity problems. We prove that a unique solution of the NCP exists under the condition of diagonalizable tensors.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Positive Semi-Definiteness and Sum-of-Squares Property of Fourth Order Four Dimensional Hankel Tensors

A positive semi-definite (PSD) tensor which is not a sum-of-squares (SOS) tensor is called a PSD non-SOS (PNS) tensor. Is there a fourth order four dimensional PNS Hankel tensor? Until now, this question is still an open problem. Its answer has both theoretical and practical meanings. We assume that the generating vector $v$ of the Hankel tensor $A$ is symmetric. Under this assumption, we may fix the fifth element $v_4$ of $v$ at $1$. We show that there are two surfaces $M_0$ and $N_0$ with the elements $v_2, v_6, v_1, v_3, v_5$ of $v$ as variables, such that $M_0 \ge N_0$, $A$ is SOS if and only if $v_0 \ge M_0$, and $A$ is PSD if and only if $v_0 \ge N_0$, where $v_0$ is the first element of $v$. If $M_0 = N_0$ for a point $P = (v_2, v_6, v_1, v_3, v_5)^\top$, then there are no fourth order four dimensional PNS Hankel tensors with symmetric generating vectors for such $v_2, v_6, v_1, v_3, v_5$. Then, we call such a point $P$ PNS-free. We show that a $45$-degree planar closed convex cone, a segment, a ray and an additional point are PNS-free. Numerical tests check various grid points, and find that they are also PNS-free.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Some Spectral Properties of Odd-Bipartite $Z$-Tensors and Their Absolute Tensors

Stimulated by odd-bipartite and even-bipartite hypergraphs, we define odd-bipartite (weakly odd-bipartie) and even-bipartite (weakly even-bipartite) tensors. It is verified that all even order odd-bipartite tensors are irreducible tensors, while all even-bipartite tensors are reducible no matter the parity of the order. Based on properties of odd-bipartite tensors, we study the relationship between the largest H-eigenvalue of a $Z$-tensor with nonnegative diagonal elements, and the largest H-eigenvalue of absolute tensor of that $Z$-tensor. When the order is even and the $Z$-tensor is weakly irreducible, we prove that the largest H-eigenvalue of the $Z$-tensor and the largest H-eigenvalue of the absolute tensor of that $Z$-tensor are equal, if and only if the $Z$-tensor is weakly odd-bipartite. Examples show the authenticity of the conclusions. Then, we prove that a symmetric $Z$-tensor with nonnegative diagonal entries and the absolute tensor of the $Z$-tensor are diagonal similar, if and only if the $Z$-tensor has even order and it is weakly odd-bipartite. After that, it is proved that, when an even order symmetric $Z$-tensor with nonnegative diagonal entries is weakly irreducible, the equality of the spectrum of the $Z$-tensor and the spectrum of absolute tensor of that $Z$-tensor, can be characterized by the equality of their spectral radii.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

SOS Tensor Decomposition: Theory and Applications

In this paper, we examine structured tensors which have sum-of-squares (SOS) tensor decomposition, and study the SOS-rank of SOS tensor decomposition. We first show that several classes of even order symmetric structured tensors available in the literature have SOS tensor decomposition. These include positive Cauchy tensors, weakly diagonally dominated tensors, $B_0$-tensors, double $B$-tensors, quasi-double $B_0$-tensors, $MB_0$-tensors, $H$-tensors, absolute tensors of positive semi-definite $Z$-tensors and extended $Z$-tensors. We also examine the SOS-rank of SOS tensor decomposition and the SOS-width for SOS tensor cones. The SOS-rank provides the minimal number of squares in the SOS tensor decomposition, and, for a given SOS tensor cone, its SOS-width is the maximum possible SOS-rank for all the tensors in this cone. We first deduce an upper bound for general tensors that have SOS decomposition and the SOS-width for general SOS tensor cone using the known results in the literature of polynomial theory. Then, we provide an explicit sharper estimate for the SOS-rank of SOS tensor decomposition with bounded exponent and identify the SOS-width for the tensor cone consisting of all tensors with bounded exponent that have SOS decompositions. Finally, as applications, we show how the SOS tensor decomposition can be used to compute the minimum $H$-eigenvalue of an even order symmetric extended $Z$-tensor and test the positive definiteness of an associated multivariate form. Numerical experiments are also provided to show the efficiency of the proposed numerical methods ranging from small size to large size numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Tensor Complementarity Problem and Semi-positive Tensors

The tensor complementarity problem $(\q, \mathcal{A})$ is to $$\mbox{ find } \x \in \mathbb{R}^n\mbox{ such that }\x \geq \0, \q + \mathcal{A}\x^{m-1} \geq \0, \mbox{ and }\x^\top (\q + \mathcal{A}\x^{m-1}) = 0.$$ We prove that a real tensor $\mathcal{A}$ is a (strictly) semi-positive tensor if and only if the tensor complementarity problem $(\q, \mathcal{A})$ has a unique solution for $\q>\0$ ($\q\geq\0$), and a symmetric real tensor is a (strictly) semi-positive tensor if and only if it is (strictly) copositive. That is, for a strictly copositive symmetric tensor $\mathcal{A}$, the tensor complementarity problem $(\q, \mathcal{A})$ has a solution for all $\q \in \mathbb{R}^n$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The positive semi-definite cone and sum-of-squares cone of Hankel form

In this paper, the geometry properties of Hankel form are studied, including their positive semi-definite (PSD) cone and sum-of-squares (SOS) cone. We denote them by $HPSD(m,n)$ and $HSOS(m,n)$, respectively. We show that both $HPSD(m,n)$ and $HSOS(m,n)$ are closed convex cones. The dual cone of $HPSD(m,n)$ is the convex hull of all $m$-times convolutions of real vectors. Besides, we derive the dual cone of SOS tensors. By reformulation, it follows that the dual cone of $HSOS(m,n)$ can also be written explicitly. These results may lead further research on the Hilbert-Hankel problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The proof of a conjecture on largest Laplacian and signless Laplacian H-eigenvalues of uniform hypergraphs

Let $\mathcal{A(}G\mathcal{)},\mathcal{L(}G\mathcal{)}$ and $\mathcal{Q(}% G\mathcal{)}$ be the adjacency tensor, Laplacian tensor and signless Laplacian tensor of uniform hypergraph $G$, respectively. Denote by $λ(\mathcal{T})$ the largest H-eigenvalue of tensor $\mathcal{T}$. Let $H$ be a uniform hypergraph, and $H^{\prime}$ be obtained from $H$ by inserting a new vertex with degree one in each edge. We prove that $λ(\mathcal{Q(}% H^{\prime}\mathcal{)})\leqλ(\mathcal{Q(}H\mathcal{)}).$ Denote by $G^{k}$ the $k$th power hypergraph of an ordinary graph $G$ with maximum degree $Δ\geq2$. We will prove that $\{λ(\mathcal{Q(}% G^{k}\mathcal{)})\}$ is a strictly decreasing sequence, which imply Conjectrue 4.1 of Hu, Qi and Shao in \cite{HuQiShao2013}. We also prove that $λ(\mathcal{Q(}G^{k}\mathcal{)})$ converges to $Δ$ when $k$ goes to infinity. The definiton of $k$th power hypergraph $G^{k}$ has been generalized as $G^{k,s}.$ We also prove some eigenvalues properties about $\mathcal{A(}% G^{k,s}\mathcal{)},$ which generalize some known results. Some related results about $\mathcal{L(}G\mathcal{)}$ are also mentioned.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Sparsest Solutions to $Z$-Tensor Complementarity Problems

Finding the sparsest solutions to a tensor complementarity problem is generally NP-hard due to the nonconvexity and noncontinuity of the involved $\ell_0$ norm. In this paper, a special type of tensor complementarity problems with $Z$-tensors has been considered. Under some mild conditions, we show that to pursuit the sparsest solutions is equivalent to solving polynomial programming with a linear objective function. The involved conditions guarantee the desired exact relaxation and also allow to achieve a global optimal solution to the relaxed nonconvex polynomial programming problem. Particularly, in comparison to existing exact relaxation conditions, such as RIP-type ones, our proposed conditions are easy to verify.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Tensor Analogy of Yuan's Theorem of the Alternative and Polynomial Optimization with Sign structure

Yuan's theorem of the alternative is an important theoretical tool in optimization, which provides a checkable certificate for the infeasibility of a strict inequality system involving two homogeneous quadratic functions. In this paper, we provide a tractable extension of Yuan's theorem of the alternative to the symmetric tensor setting. As an application, we establish that the optimal value of a class of nonconvex polynomial optimization problems with suitable sign structure (or more explicitly, with essentially non-positive coefficients) can be computed by a related convex conic programming problem, and the optimal solution of these nonconvex polynomial optimization problems can be recovered from the corresponding solution of the convex conic programming problem. Moreover, we obtain that this class of nonconvex polynomial optimization problems enjoy exact sum-of-squares relaxation, and so, can be solved via a single semidefinite programming problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An Even Order Symmetric B Tensor is Positive Definite

It is easily checkable if a given tensor is a B tensor, or a B$_0$ tensor or not. In this paper, we show that a symmetric B tensor can always be decomposed to the sum of a strictly diagonally dominated symmetric M tensor and several positive multiples of partially all one tensors, and a symmetric B$_0$ tensor can always be decomposed to the sum of a diagonally dominated symmetric M tensor and several positive multiples of partially all one tensors. When the order is even, this implies that the corresponding B tensor is positive definite, and the corresponding B$_0$ tensor is positive semi-definite. This gives a checkable sufficient condition for positive definite and semi-definite tensors. This approach is different from the approach in the literature for proving a symmetric B matrix is positive definite, as that matrix approach cannot be extended to the tensor case.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Centrosymmetric, Skew Centrosymmetric and Centrosymmetric Cauchy Tensors

Recently, Zhao and Yang introduced centrosymmetric tensors. In this paper, we further introduce skew centrosymmetric tensors and centrosymmetric Cauchy tensors, and discuss properties of these three classes of structured tensors. Some sufficient and necessary conditions for a tensor to be centrosymmetric or skew centrosymmetric are given. We show that, a general tensor can always be expressed as the sum of a centrosymmetric tensor and a skew centrosymmetric tensor. Some sufficient and necessary conditions for a Cauchy tensor to be centrosymmetric or skew centrosymmetric are also given. Spectral properties on H-eigenvalues and H-eigenvectors of centrosymmetric, skew centrosymmetric and centrosymmetric Cauchy tensors are discussed. Some further questions on these tensors are raised.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Circulant Tensors with Applications to Spectral Hypergraph Theory and Stochastic Process

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 a circulant tensor to be positive semi-definite.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fast Hankel Tensor-Vector Products and Application to Exponential Data Fitting

This paper is contributed to a fast algorithm for Hankel tensor-vector products. For this purpose, we first discuss a special class of Hankel tensors that can be diagonalized by the Fourier matrix, which is called \emph{anti-circulant} tensors. Then we obtain a fast algorithm for Hankel tensor-vector products by embedding a Hankel tensor into a larger anti-circulant tensor. The computational complexity is about $\mathcal{O}(m^2 n \log mn)$ for a square Hankel tensor of order $m$ and dimension $n$, and the numerical examples also show the efficiency of this scheme. Moreover, the block version for multi-level block Hankel tensors is discussed as well. Finally, we apply the fast algorithm to exponential data fitting and the block version to 2D exponential data fitting for higher performance.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Hankel Tensors: Associated Hankel Matrices and Vandermonde Decomposition

Hankel tensors arise from applications such as signal processing. In this paper, we make an initial study on Hankel tensors. For each Hankel tensor, we associate it with a Hankel matrix and a higher order two-dimensional symmetric tensor, which we call the associated plane tensor. If the associated Hankel matrix is positive semi-definite, we call such a Hankel tensor a strong Hankel tensor. We show that an $m$ order $n$-dimensional tensor is a Hankel tensor if and only if it has a Vandermonde decomposition. We call a Hankel tensor a complete Hankel tensor if it has a Vandermonde decomposition with positive coefficients. We prove that if a Hankel tensor is copositive or an even order Hankel tensor is positive semi-definite, then the associated plane tensor is copositive or positive semi-definite, respectively. We show that even order strong and complete Hankel tensors are positive semi-definite, the Hadamard product of two strong Hankel tensors is a strong Hankel tensor, and the Hadamard product of two complete Hankel tensors is a complete Hankel tensor. We show that all the H-eigenvalue of a complete Hankel tensors (maybe of odd order) are nonnegative. We give some upper bounds and lower bounds for the smallest and the largest Z-eigenvalues of a Hankel tensor, respectively. Further questions on Hankel tensors are raised.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Infinite and finite dimensional Hilbert tensors

For an $m$-order $n-$dimensional Hilbert tensor (hypermatrix) $\mathcal{H}_n=(\mathcal{H}_{i_1i_2\cdots i_m})$, $$\mathcal{H}_{i_1i_2\cdots i_m}=\frac1{i_1+i_2+\cdots+i_m-m+1},\ i_1,\cdots, i_m=1,2,\cdots,n$$ its spectral radius is not larger than $n^{m-1}\sin\fracπ{n}$, and an upper bound of its $E$-spectral radius is $n^{\frac{m}2}\sin\fracπ{n}$. Moreover, its spectral radius is strictly increasing and its $E$-spectral radius is nondecreasing with respect to the dimension $n$. When the order is even, both infinite and finite dimensional Hilbert tensors are positive definite. We also show that the $m$-order infinite dimensional Hilbert tensor (hypermatrix) $\mathcal{H}_\infty=(\mathcal{H}_{i_1i_2\cdots i_m})$ defines a bounded and positively $(m-1)$-homogeneous operator from $l^1$ into $l^p$ ($1<p<\infty$), and the norm of corresponding positively homogeneous operator is smaller than or equal to $\fracπ{\sqrt6}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Positive Definiteness and Semi-Definiteness of Even Order Symmetric Cauchy Tensors

Motivated by symmetric Cauchy matrices, we define symmetric Cauchy tensors and their generating vectors in this paper. Hilbert tensors are symmetric Cauchy tensors. An even order symmetric Cauchy tensor is positive semi-definite if and only if its generating vector is positive. An even order symmetric Cauchy tensor is positive definite if and only if its generating vector has positive and mutually distinct entries. This extends Fiedler's result for symmetric Cauchy matrices to symmetric Cauchy tensors. Then, it is proven that the positive semi-definiteness character of an even order symmetric Cauchy tensor can be equivalently checked by the monotone increasing property of a homogeneous polynomial related to the Cauchy tensor. The homogeneous polynomial is strictly monotone increasing in the nonnegative orthant of the Euclidean space when the even order symmetric Cauchy tensor is positive definite. Furthermore, we prove that the Hadamard product of two positive semi-definite (positive definite respectively) symmetric Cauchy tensors is a positive semi-definite (positive definite respectively) tensor, which can be generalized to the Hadamard product of finitely many positive semi-definite (positive definite respectively) symmetric Cauchy tensors. At last, bounds of the largest H-eigenvalue of a positive semi-definite symmetric Cauchy tensor are given and several spectral properties on Z-eigenvalues of odd order symmetric Cauchy tensors are shown. Further questions on Cauchy tensors are raised.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Positive Semi-Definiteness of Generalized Anti-Circulant Tensors

Anti-circulant tensors have applications in exponential data fitting. They are special Hankel tensors. In this paper, we extend the definition of anti-circulant tensors to generalized anti-circulant tensors by introducing a circulant index $r$ such that the entries of the generating vector of a Hankel tensor are circulant with module $r$. In the special case when $r =n$, where $n$ is the dimension of the Hankel tensor, the generalized anticirculant tensor reduces to the anti-circulant tensor. Hence, generalized anti-circulant tensors are still special Hankel tensors. For the cases that $GCD(m, r) =1$, $GCD(m, r) = 2$ and some other cases, including the matrix case that $m=2$, we give necessary and sufficient conditions for positive semi-definiteness of even order generalized anti-circulant tensors, and show that in these cases, they are SOS tensors. This shows that, in these cases, there are no PNS (positive semidefinite tensors which are not sum of squares) Hankel tensors.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Properties of Some Classes of Structured Tensors

In this paper, we extend some classes of structured matrices to higher order tensors. We discuss their relationships with positive semi-definite tensors and some other structured tensors. We show that every principal sub-tensor of such a structured tensor is still a structured tensor in the same class, with a lower dimension. The potential links of such structured tensors with optimization, nonlinear equations, nonlinear complementarity problems, variational inequalities and the nonnegative tensor theory are also discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

SOS-Hankel Tensors: Theory and Application

Hankel tensors arise from signal processing and some other applications. SOS (sum-of-squares) tensors are positive semi-definite symmetric tensors, but not vice versa. The problem for determining an even order symmetric tensor is an SOS tensor or not is equivalent to solving a semi-infinite linear programming problem, which can be done in polynomial time. On the other hand, the problem for determining an even order symmetric tensor is positive semi-definite or not is NP-hard. In this paper, we study SOS-Hankel tensors. Currently, there are two known positive semi-definite Hankel tensor classes: even order complete Hankel tensors and even order strong Hankel tensors. We show complete Hankel tensors are strong Hankel tensors, and even order strong Hankel tensors are SOS-Hankel tensors. We give several examples of positive semi-definite Hankel tensors, which are not strong Hankel tensors. However, all of them are still SOS-Hankel tensors. Does there exist a positive semi-definite non-SOS-Hankel tensor? The answer to this question remains open. If the answer to this question is no, then the problem for determining an even order Hankel tensor is positive semi-definite or not is solvable in polynomial-time. An application of SOS-Hankel tensors to the positive semi-definite tensor completion problem is discussed. We present an ADMM algorithm for solving this problem. Some preliminary numerical results on this algorithm are reported.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The extremal spectral radii of $k$-uniform supertrees

In this paper, we study some extremal problems of three kinds of spectral radii of $k$-uniform hypergraphs (the adjacency spectral radius, the signless Laplacian spectral radius and the incidence $Q$-spectral radius). We call a connected and acyclic $k$-uniform hypergraph a supertree. We introduce the operation of "moving edges" for hypergraphs, together with the two special cases of this operation: the edge-releasing operation and the total grafting operation. By studying the perturbation of these kinds of spectral radii of hypergraphs under these operations, we prove that for all these three kinds of spectral radii, the hyperstar $\mathcal{S}_{n,k}$ attains uniquely the maximum spectral radius among all $k$-uniform supertrees on $n$ vertices. We also determine the unique $k$-uniform supertree on $n$ vertices with the second largest spectral radius (for these three kinds of spectral radii). We also prove that for all these three kinds of spectral radii, the loose path $\mathcal{P}_{n,k}$ attains uniquely the minimum spectral radius among all $k$-th power hypertrees of $n$ vertices. Some bounds on the incidence $Q$-spectral radius are given. The relation between the incidence $Q$-spectral radius and the spectral radius of the matrix product of the incidence matrix and its transpose is discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Convergence of a Second Order Markov Chain

In this paper, we consider convergence properties of a second order Markov chain. Similar to a column stochastic matrix is associated to a Markov chain, a so called {\em transition probability tensor} $P$ of order 3 and dimension $n$ is associated to a second order Markov chain with $n$ states. For this $P$, define $F_P$ as $F_P(x):=Px^{2}$ on the $n-1$ dimensional standard simplex $Δ_n$. If 1 is not an eigenvalue of $\nabla F_P$ on $Δ_n$ and $P$ is irreducible, then there exists a unique fixed point of $F_P$ on $Δ_n$. In particular, if every entry of $P$ is greater than $\frac{1}{2n}$, then 1 is not an eigenvalue of $\nabla F_P$ on $Δ_n$. Under the latter condition, we further show that the second order power method for finding the unique fixed point of $F_P$ on $Δ_n$ is globally linearly convergent and the corresponding second order Markov process is globally $R$-linearly convergent.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Cored Hypergraphs, Power Hypergraphs and Their Laplacian H-Eigenvalues

In this paper, we introduce the class of cored hypergraphs and power hypergraphs, and investigate the properties of their Laplacian H-eigenvalues. From an ordinary graph, one may generate a $k$-uniform hypergraph, called the $k$th power hypergraph of that graph. Power hypergraphs are cored hypergraphs, but not vice versa. Hyperstars, hypercycles, hyperpaths are special cases of power hypergraphs, while sunflowers are a subclass of cored hypergraphs, but not power graphs in general. We show that the largest Laplacian H-eigenvalue of an even-uniform cored hypergraph is equal to its largest signless Laplacian H-eigenvalue. Especially, we find out these largest H-eigenvalues for even-uniform sunflowers. Moreover, we show that the largest Laplacian H-eigenvalue of an odd-uniform sunflower, hypercycle and hyperpath is equal to the maximum degree, i.e., 2. We also compute out the H-spectra of the class of hyperstars. When $k$ is odd, the H-spectra of the hypercycle of size 3 and the hyperpath of length 3 are characterized as well.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Eigenvalue analysis of constrained minimization problem for homogeneous polynomial

In this paper, the concepts of Pareto $H$-eigenvalue and Pareto $Z$-eigenvalue are introduced for studying constrained minimization problem and the necessary and sufficient conditions of such eigenvalues are given. It is proved that a symmetric tensor has at least one Pareto $H$-eigenvalue (Pareto $Z$-eigenvalue). Furthermore, the minimum Pareto $H$-eigenvalue (or Pareto $Z$-eigenvalue) of a symmetric tensor is exactly equal to the minimum value of constrained minimization problem of homogeneous polynomial deduced by such a tensor, which gives an alternative methods for solving the minimum value of constrained minimization problem. In particular, a symmetric tensor $\mathcal{A}$ is copositive if and only if every Pareto $H$-eigenvalue ($Z-$eigenvalue) of $\mathcal{A}$ is non-negative.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

H$^+$-Eigenvalues of Laplacian and Signless Laplacian Tensors

We propose a simple and natural definition for the Laplacian and the signless Laplacian tensors of a uniform hypergraph. We study their H$^+$-eigenvalues, i.e., H-eigenvalues with nonnegative H-eigenvectors, and H$^{++}$-eigenvalues, i.e., H-eigenvalues with positive H-eigenvectors. We show that each of the Laplacian tensor, the signless Laplacian tensor and the adjacency tensor has at most one H$^{++}$-eigenvalue, but has several other H$^+$-eigenvalues. We identify their largest and smallest H$^+$-eigenvalues, and establish some maximum and minimum properties of these H$^+$-eigenvalues. We then define analytic connectivity of a uniform hypergraph and discuss its application in edge connectivity.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

M-Tensors and Nonsingular M-Tensors

The M-matrix is an important concept in matrix theory, and has many applications. Recently, this concept has been extended to higher order tensors [18]. In this paper, we establish some important properties of M-tensors and nonsingular M-tensors. An M-tensor is a Z-tensor. We show that a Z-tensor is a nonsingular M-tensor if and only if it is semi-positive. Thus, a nonsingular M-tensor has all positive diagonal entries; and an M-tensor, regarding as the limitation of a series of nonsingular M-tensors, has all nonnegative diagonal entries. We introduce even-order monotone tensors and present their spectral properties. In matrix theory, a Z-matrix is a nonsingular M-matrix if and only if it is monotone. This is no longer true in the case of higher order tensors. We show that an even-order monotone Z-tensor is an even-order nonsingular M-tensor but not vice versa. An example of an even-order nontrivial monotone Z-tensor is also given.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Nonnegative Tensor Factorization, Completely Positive Tensors and an Hierarchical Elimination Algorithm

Nonnegative tensor factorization has applications in statistics, computer vision, exploratory multiway data analysis and blind source separation. A symmetric nonnegative tensor, which has a symmetric nonnegative factorization, is called a completely positive (CP) tensor. The H-eigenvalues of a CP tensor are always nonnegative. When the order is even, the Z-eigenvalue of a CP tensor are all nonnegative. When the order is odd, a Z-eigenvector associated with a positive (negative) Z-eigenvalue of a CP tensor is always nonnegative (nonpositive). The entries of a CP tensor obey some dominance properties. The CP tensor cone and the copositive tensor cone of the same order are dual to each other. We introduce strongly symmetric tensors and show that a symmetric tensor has a symmetric binary decomposition if and only if it is strongly symmetric. Then we show that a strongly symmetric, hierarchically dominated nonnegative tensor is a CP tensor, and present a hierarchical elimination algorithm for checking this. Numerical examples are also given.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Regular Uniform Hypergraphs, $s$-Cycles, $s$-Paths and Their largest Laplacian H-Eigenvalues

In this paper, we show that the largest signless Laplacian H-eigenvalue of a connected $k$-uniform hypergraph $G$, where $k \ge 3$, reaches its upper bound $2Δ(G)$, where $Δ(G)$ is the largest degree of $G$, if and only if $G$ is regular. Thus the largest Laplacian H-eigenvalue of $G$, reaches the same upper bound, if and only if $G$ is regular and odd-bipartite. We show that an $s$-cycle $G$, as a $k$-uniform hypergraph, where $1 \le s \le k-1$, is regular if and only if there is a positive integer $q$ such that $k=q(k-s)$. We show that an even-uniform $s$-path and an even-uniform non-regular $s$-cycle are always odd-bipartite. We prove that a regular $s$-cycle $G$ with $k=q(k-s)$ is odd-bipartite if and only if $m$ is a multiple of $2^{t_0}$, where $m$ is the number of edges in $G$, and $q = 2^{t_0}(2l_0+1)$ for some integers $t_0$ and $l_0$. We identify the value of the largest signless Laplacian H-eigenvalue of an $s$-cycle $G$ in all possible cases. When $G$ is odd-bipartite, this is also its largest Laplacian H-eigenvalue. We introduce supervertices for hypergraphs, and show the components of a Laplacian H-eigenvector of an odd-uniform hypergraph are equal if such components corresponds vertices in the same supervertex, and the corresponding Laplacian H-eigenvalue is not equal to the degree of the supervertex. Using this property, we show that the largest Laplacian H-eigenvalue of an odd-uniform generalized loose $s$-cycle $G$ is equal to $Δ(G)=2$. We also show that the largest Laplacian H-eigenvalue of a $k$-uniform tight $s$-cycle $G$ is not less than $Δ(G)+1$, if the number of vertices is even and $k=4l+3$ for some nonnegative integer $l$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Some new trace formulas of tensors with applications in spectral hypergraph theory

We give some graph theoretical formulas for the trace $Tr_k(\mathbb {T})$ of a tensor $\mathbb {T}$ which do not involve the differential operators and auxiliary matrix. As applications of these trace formulas in the study of the spectra of uniform hypergraphs, we give a characterization (in terms of the traces of the adjacency tensors) of the $k$-uniform hypergraphs whose spectra are $k$-symmetric, thus give an answer to a question raised in [3]. We generalize the results in [3, Theorem 4.2] and [5, Proposition 3.1] about the $k$-symmetry of the spectrum of a $k$-uniform hypergraph, and answer a question in [5] about the relation between the Laplacian and signless Laplacian spectra of a $k$-uniform hypergraph when $k$ is odd. We also give a simplified proof of an expression for $Tr_2(\mathbb {T})$ and discuss the expression for $Tr_3(\mathbb {T})$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The E-Eigenvectors of Tensors

We first show that the eigenvector of a tensor is well-defined. The differences between the eigenvectors of a tensor and its E-eigenvectors are the eigenvectors on the nonsingular projective variety $\mathbb S=\{\mathbf x\in\mathbb P^n\;|\;\sum\limits_{i=0}^nx_i^2=0\}$. We show that a generic tensor has no eigenvectors on $\mathbb S$. Actually, we show that a generic tensor has no eigenvectors on a proper nonsingular projective variety in $\mathbb P^n$. By these facts, we show that the coefficients of the E-characteristic polynomial are algebraically dependent. Actually, a certain power of the determinant of the tensor can be expressed through the coefficients besides the constant term. Hence, a nonsingular tensor always has an E-eigenvector. When a tensor $\mathcal T$ is nonsingular and symmetric, its E-eigenvectors are exactly the singular points of a class of hypersurfaces defined by $\mathcal T$ and a parameter. We give explicit factorization of the discriminant of this class of hypersurfaces, which completes Cartwright and Strumfels' formula. We show that the factorization contains the determinant and the E-characteristic polynomial of the tensor $\mathcal T$ as irreducible factors.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Eigenvectors of the Zero Laplacian and Signless Laplacian Eigenvalues of a Uniform Hypergraph

In this paper, we show that the eigenvectors of the zero Laplacian and signless Lapacian eigenvalues of a $k$-uniform hypergraph are closely related to some configured components of that hypergraph. We show that the components of an eigenvector of the zero Laplacian or signless Lapacian eigenvalue have the same modulus. Moreover, under a {\em canonical} regularization, the phases of the components of these eigenvectors only can take some uniformly distributed values in $\{\{exp}(\frac{2jπ}{k})\;|\;j\in [k]\}$. These eigenvectors are divided into H-eigenvectors and N-eigenvectors. Eigenvectors with minimal support is called {\em minimal}. The minimal canonical H-eigenvectors characterize the even (odd)-bipartite connected components of the hypergraph and vice versa, and the minimal canonical N-eigenvectors characterize some multi-partite connected components of the hypergraph and vice versa.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Largest Laplacian and Signless Laplacian H-Eigenvalues of a Uniform Hypergraph

In this paper, we show that the largest Laplacian H-eigenvalue of a $k$-uniform nontrivial hypergraph is strictly larger than the maximum degree when $k$ is even. A tight lower bound for this eigenvalue is given. For a connected even-uniform hypergraph, this lower bound is achieved if and only if it is a hyperstar. However, when $k$ is odd, it happens that the largest Laplacian H-eigenvalue is equal to the maximum degree, which is a tight lower bound. On the other hand, tight upper and lower bounds for the largest signless Laplacian H-eigenvalue of a $k$-uniform connected hypergraph are given. For a connected $k$-uniform hypergraph, the upper (respectively lower) bound of the largest signless Laplacian H-eigenvalue is achieved if and only if it is a complete hypergraph (respectively a hyperstar). The largest Laplacian H-eigenvalue is always less than or equal to the largest signless Laplacian H-eigenvalue. When the hypergraph is connected, the equality holds here if and only if $k$ is even and the hypergraph is odd-bipartite.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The necessary and sufficient conditions of copositive tensors

In this paper, it is proved that (strict) copositivity of a symmetric tensor $\mathcal{A}$ is equivalent to the fact that every principal sub-tensor of $\mathcal{A}$ has no a (non-positive) negative $H^{++}$-eigenvalue. The necessary and sufficient conditions are also given in terms of the $Z^{++}$-eigenvalue of the principal sub-tensor of the given tensor. This presents a method of testing (strict) copositivity of a symmetric tensor by means of the lower dimensional tensors. Also the equivalent definition of strictly copositive tensors is given on entire space $\mathbb{R}^n$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

E-Characteristic Polynomials of Tensors

In this paper, we show that the coefficients of the E-characteristic polynomial of a tensor are orthonormal invariants of that tensor. When the dimension is 2, some simplified formulas of the E-characteristic polynomial are presented. A re- sultant formula for the constant term of the E-characteristic polynomial is given. We then study the set of tensors with infinitely many eigenpairs and the set of irregular tensors, and prove both the sets have codimension 2 as subvarieties in the projective space of tensors. This makes our perturbation method workable. By using the perturbation method and exploring the difference between E-eigenvalues and eigenpair equivalence classes, we present a simple formula for the coefficient of the leading term of the E-characteristic polynomial, when the dimension is 2.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Geometric measure of entanglement of multipartite mixed states

The geometric measure of entanglement of a pure state, defined by its distance to the set of pure separable states, is extended to multipartite mixed states. We characterize the nearest disentangled mixed state to a given mixed state with respect to this measure by a system of equations. The entanglement eigenvalue for a mixed state is introduced. For a given mixed state, we show that its nearest disentangled mixed state is associated with its entanglement eigenvalue.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Symmetric Nonnegative Tensors and Copositive Tensors

We first prove two new spectral properties for symmetric nonnegative tensors. We prove a maximum property for the largest H-eigenvalue of a symmetric nonnegative tensor, and establish some bounds for this eigenvalue via row sums of that tensor. We show that if an eigenvalue of a symmetric nonnegative tensor has a positive H-eigenvector, then this eigenvalue is the largest H-eigenvalue of that tensor. We also give a necessary and sufficient condition for this. We then introduce copositive tensors. This concept extends the concept of copositive matrices. Symmetric nonnegative tensors and positive semi-definite tensors are examples of copositive tensors. The diagonal elements of a copositive tensor must be nonnegative. We show that if each sum of a diagonal element and all the negative off-diagonal elements in the same row of a real symmetric tensor is nonnegative, then that tensor is a copositive tensor. Some further properties of copositive tensors are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The geometric measure of entanglement of pure states with nonnegative amplitudes and the spectral theory of nonnegative tensors

The geometric measure of entanglement for a symmetric pure state with nonnegative amplitudes has attracted much attention. On the other hand, the spectral theory of nonnegative tensors (hypermatrices) has been developed rapidly. In this paper, we show how the spectral theory of nonnegative tensors can be applied to the study of the geometric measure of entanglement for a pure state with nonnegative amplitudes. Especially, an elimination method for computing the geometric measure of entanglement for symmetric pure multipartite qubit or qutrit states with nonnegative amplitudes is given. For symmetric pure multipartite qudit states with nonnegative amplitudes, a numerical algorithm with randomization is presented and proven to be convergent. We show that for the geometric measure of entanglement for pure states with nonnegative amplitudes, the nonsymmetric ones can be converted to the symmetric ones.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Minimum Hartree Value for the Quantum Entanglement Problem

A general $n$-partite state $| Ψ>$ of a composite quantum system can be regarded as an element in a Hilbert tensor product space $\HH = \otimes_{k=1}^n \HH_k$, where the dimension of $\HH_k$ is $d_k$ for $k = 1,..., n$. Without loss of generality we may assume that $d_1 \le...\le d_n$. A separable (Hartree) $n$-partite state $| ϕ>$ can be described by $| ϕ> = \otimes_{k=1}^n | ϕ^{(k)}>$ with $| ϕ^{(k)}> \in \HH_k$. We show that $σ:= \min \{< Ψ| ϕ_Ψ> : | Ψ> \in \HH,.$ $. < Ψ| Ψ> = 1\}$ is a positive number, where $| ϕ_Ψ>$ is the nearest separable state to $| Ψ>$. We call $σ$ the minimum Hartree value of $\HH$. We further show that $σ\ge 1/{\sqrt{d_1... d_{n-1}}}$. Thus, the geometric measure of the entanglement content of $Ψ$, $\| | Ψ> - | ϕ_Ψ> \| \le \sqrt{2-2σ} \le \sqrt{2-2(1/{\sqrt{d_1...d_{n-1}}})}$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Quantum Eigenvalue Problem and Z-Eigenvalues of Tensors

The quantum eigenvalue problem arises in the study of the geometric measure of the quantum entanglement. In this paper, we convert the quantum eigenvalue problem to the Z-eigenvalue problem of a real symmetric tensor. In this way, the theory and algorithms for Z-eigenvalues can be applied to the quantum eigenvalue problem. In particular, this gives an upper bound for the number of quantum eigenvalues. We show that the quantum eigenvalues appear in pairs, i.e., if a real number $λ$ is a quantum eigenvalue of a square symmetric tensor $Ψ$, then $-λ$ is also a quantum eigenvalue of $Ψ$. When $Ψ$ is real, we show that the entanglement eigenvalue of $Ψ$ is always greater than or equal to the Z-spectral radius of $Ψ$, and that in several cases the equality holds. We also show that the ratio between the entanglement eigenvalue and the Z-spectral radius of a real symmetric tensor is bounded above in a real symmetric tensor space of fixed order and dimension.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

E-Determinants of Tensors

We generalize the concept of the symmetric hyperdeterminants for symmetric tensors to the E-determinants for general tensors. We show that the E-determinant inherits many properties of the determinant of a matrix. These properties include: solvability of polynomial systems, the E-determinat of the composition of tensors, product formula for the E-determinant of a block tensor, Hadamard's inequality, Gersgrin's inequality and Minikowski's inequality. As a simple application, we show that if the leading coefficient tensor of a polynomial system is a triangular tensor with nonzero diagonal elements, then the system definitely has a solution. We investigate the characteristic polynomial of a tensor through the E-determinant. Explicit formulae for the coefficients of the characteristic polynomial are given when the dimension is two.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Finding the Spectral Radius of a Nonnegative Tensor

In this paper, we introduce a new class of nonnegative tensors --- strictly nonnegative tensors. A weakly irreducible nonnegative tensor is a strictly nonnegative tensor but not vice versa. We show that the spectral radius of a strictly nonnegative tensor is always positive. We give some sufficient and necessary conditions for the six well-conditional classes of nonnegative tensors, introduced in the literature, and a full relationship picture about strictly nonnegative tensors with these six classes of nonnegative tensors. We then establish global R-linear convergence of a power method for finding the spectral radius of a nonnegative tensor under the condition of weak irreducibility. We show that for a nonnegative tensor T, there always exists a partition of the index set such that every tensor induced by the partition is weakly irreducible; and the spectral radius of T can be obtained from those spectral radii of the induced tensors. In this way, we develop a convergent algorithm for finding the spectral radius of a general nonnegative tensor without any additional assumption. The preliminary numerical results demonstrate the feasibility and effectiveness of the proposed algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Dominant Eigenvalue of an Essentially Nonnegative Tensor

It is well known that the dominant eigenvalue of a real essentially nonnegative matrix is a convex function of its diagonal entries. This convexity is of practical importance in population biology, graph theory, demography, analytic hierarchy process and so on. In this paper, the concept of essentially nonnegativity is extended from matrices to higher order tensors, and the convexity and log convexity of dominant eigenvalues for such a class of tensors are established. Particularly, for any nonnegative tensor, the spectral radius turns out to be the dominant eigenvalue and hence possesses these convexities. Finally, an algorithm is given to calculate the dominant eigenvalue, and numerical results are reported to show the effectiveness of the proposed algorithm.

0 citations0 reviewsNo code linkedOpen access