\section{Introduction}

Tensors can be regarded as a high-order generalization of matrices. For $m,n \in \mathbb{N}$, an $m$-order $n$-dimensional real tensor is a multidimensional array with the form
\[
\mathcal{A} = (a_{i_1 i_2 \dots i_m}), \quad a_{i_1i_2 \dots i_m} \in \mathbb{R}, \quad 1 \leq i_1 ,i_2,\dots, i_m \leq n.
\]
Matrices are tensors with order $m=2$. Denote $ \mathbb{T}_{m,n}$ as the space of all real tensors with order$~m$ and dimension $n$. Then 
\begin{equation*}
\mathbb{T}_{m,n} = \underbrace { \mathbb{R}^{n} \otimes \mathbb{R}^{n}  \otimes \cdots \otimes \mathbb{R}^{n} }_{m},
\end{equation*}
where $\otimes $ is the outer product. Denote $[n] = \{1,2,\dots, n\}$. The tensor $\mathcal{A} = (a_{i_1  \dots i_m}) \in  \mathbb{T}_{m,n}$ is called {\em symmetric} if its entries~$a_{i_1  \dots i_m} $ are invariant under any permutation of $(i_1, \dots, i_m)$ for~$i_j \in [n], j \in [m]$. Denote $\mathbb{S}_{m,n}$ as the set of symmetric tensors in $ \mathbb{T}_{m,n}$. The entries~$a_{ii\dots i}$ for any $i \in [n]$ are called {\em diagonal elements (or entries)} of $\mathcal{A}$. 

Following~\cite{cartwright2013number,lim2005singular,qi2005eigenvalues}, for $\mathcal{A} \in \mathbb{T}_{m,n}$, $\lambda \in \mathbb{C}$ is called an {\em eigenvalue} of $\mathcal{A}$, if there exists an {\em eigenvector} $x \in \mathbb{C}^n\backslash \{0 \}$ such that $\mathcal{A}x^{m-1}= \lambda x^{[m-1]}$, where $\mathcal{A}x^{m-1} \in \mathbb{C}^n$ is defined by
\begin{flalign*}
(\mathcal{A}x^{m-1} )_i =  \sum_{i_2,\dots, i_m = 1}^n a_{ii_2 \dots i_m } x_{i_2}\cdots x_{i_m},
\end{flalign*}
and $x^{[m-1]}\in\mathbb{C}^n \backslash \{0 \}$ is defined by $(x^{[m-1]})_i = x_i^{m-1}$ for all $i \in [n] $. In particular, if $x$ is real, then~$\lambda$ is also real. In this case, we say that $\lambda$ is an {\em H-eigenvalue} of~$\mathcal{A}$.

The {\em comparison tensor} of $\mathcal{A} \in \mathbb{T}_{m,n}$, denoted as $M(\mathcal{A})$, is defined in~\cite{ding2013m,kannan2015some} as follows:
\begin{equation}
\label{eq:comptensor}
M(\mathcal{A})_{i_1  \dots i_m} = \begin{cases}
|a_{i_1  \dots i_m}| & \text{if } i_1 = \cdots = i_m, \\
- |a_{i_1 \dots i_m}| & \text{otherwise}.
\end{cases}
\end{equation}
Following~\cite{ding2013m,kannan2015some}, we introduce the following classes of tensors. 
A tensor is called a {\em nonnegative tensor} if all its entries are nonnegative and a tensor is called a {\em diagonal tensor} if all its off-diagonal elements are zero. A tensor~$\mathcal{A}  \in \mathbb{T}_{m,n}$ is said to be a {\em $Z$-tensor} if there exists a nonnegative tensor~$\mathcal{D}  \in \mathbb{T}_{m,n}$ and a nonnegative scalar~$s$ such that $\mathcal{A} = s\mathcal{I} - \mathcal{D}$, where $\mathcal{I}  \in \mathbb{T}_{m,n}$ is a diagonal tensor with all diagonal elements equal to one. For tensor $\mathcal{A}$, denote~$\rho(\mathcal{A})$ as the largest modulus of its eigenvalues. A~$Z$-tensor~$\mathcal{A} = s\mathcal{I} - \mathcal{D}$ is said to be an {\em $M$-tensor} if $s \geq \rho(\mathcal{D})$. If $s > \rho(\mathcal{D})$, then $\mathcal{A}$ is called a {\em strong $M$-tensor}. A tensor is called an {\em $H$-tensor} if its comparison tensor is an $M$-tensor. A tensor is called a {\em strong $H$-tensor} if its comparison tensor is a strong $M$-tensor. An~$H$-tensor with nonnegative diagonal elements is called an {\em $H^+$-tensor}.



The authors in~\cite[Theorem 4.9]{kannan2015some} show that a symmetric tensor is an $H$-tensor if and only if it is a {\em generalized diagonally dominant tensor} (see Definition \ref{def:dd_sdd}). The matrix version (i.e., when $m$ = 2) of this result is given in~\cite[Theorem 8]{boman2005factor} and~\cite{varga1963matrix}. Furthermore, the authors in \cite{boman2005factor} prove that a symmetric matrix is an $H^+$-matrix if and only if it can be written as the sum of a number of positive semidefinite matrices which have a special sparse structure. Based on this result, the authors in \cite{ahmadi2019dsos} show that membership to the set of symmetric $H^+$-matrices can be decided in polynomial time by solving a {\em second-order cone optimization} problem~\cite[see, e.g.,][]{lobo1998applications}. 

In this work we generalize these results to symmetric $H^+$-tensors. Namely, we prove that a symmetric tensor is an $H^+$-tensor if and only if it can be written as the sum of a number of tensors which have a special sparse structure (see Theorem~\ref{theo:gdd_decomp}). Based on this result, we obtain (see Theorem~\ref{theo:gdd_characterization}) a novel characterization of  $H^+$-tensors that is amenable to the use of {\em conic optimization techniques}~\citep[see, e.g.,][]{wright1997primal}. In particular, we show (see Corollary~\ref{cor:F(A)} and~\eqref{eq:F_A_long}) that membership to the set of symmetric $H^+$-tensors can be decided in polynomial time by solving a {\em power cone optimization} problem~\cite[see, e.g.,][]{chares2009cones,hien2015differential}

A lot of effort has been made to characterize $H^+$-tensors~\cite[see, e.g.,][]{huang2019iterative,li2014criterions,li2017programmable,liu2017iterative,wang2017new, zhang2016h,zhao2016criterions}. However, these articles typically focus on studying sufficient conditions for a tensor to be an $H$-tensor. A notable exception is recent work based on the use of spectral theory of nonnegative tensors. Namely, the authors in \cite{luan2019new} present a necessary and sufficient condition for strong $H$-tensors and propose an iterative algorithm for identifying strong H-tensors. In contrast from their methodology, here we study sufficient and necessary condition for a symmetric tensor to be an $H^+$-tensor by exploring the diagonal dominance property. 
This type of characterization allows, unlike the recent results in~\cite{luan2019new}, to directly optimize over the set of $H^+$-tensors. 
In Section~\ref{sec:Meigenvalue} and Section~\ref{part:application}.

In particular, in Section~\ref{sec:Meigenvalue}, we consider the problem of computing the minimum $H$-eigenvalue of $M$-tensors (which generalize $M$-matrices), which play an important role in a wide range of interesting applications~\citep[see,][and the references therein]{huang2018some}. In contrast with the problem of obtaining bounds on the minimum $H$-eigenvalue of $M$-tensors that has received significant attention in the literature~\citep{he2014inequalities,huang2018some,li2013new,tian2010inequalities}; here, we use our characterization of $H^+$-tensors to compute $H$-eigenvalues of $M$-tensors by solving a power cone optimization problem (see Corollary~\ref{cor:Meigen}). A comparison of the $H$-eigenvalues obtained in this way with bounds proposed in the literature is provided in Table~\ref{tab:bounds}.


Further, in Section~\ref{part:application}, we show that our characterization can be applied to address the solution of {\em polynomial optimization} problems~\citep[see, e.g.,][]{lasserre2001global}; that is, an optimization problem in which both the objective and the constraints are defined by polynomials. The connection between tensors and polynomials stems from the fact that the coefficients of a polynomial can be described using tensors.
Of particular importance, is the problem of finding if a given polynomial is nonnegative.

For example, this problem appears in the field of shape-constrained function estimation \cite{papp2011optimization}, the stability study of nonlinear autonomous systems  in automatic control \cite{anderson1975output}, and spectral hypergraph theory \cite{li2013z}. However, checking if an $m$ order and $n$ variate polynomial is nonnegative is an NP-hard problem when $n\geq 3$ and $m \geq 4$~\cite{lasserre2007sum}. Thus, to make use of nonnegative polynomials and maintain the computational efficiency, researchers have focused on using {\em tractable} subclasses of nonnegative polynomials~\cite[see, e.g.,][]{ahmadi2019dsos,chandrasekaran2016relative,iliman2016amoebas,saunderson2019certifying}. One classical choice is to use {\em sum of squares} (SOS) to certify the nonnegativity of a polynomial~\citep[see, e.g.,][]{lasserre2001global}. 
To further improve tractability, for example, authors in~\cite{ahmadi2019dsos} propose more tractable alternatives to SOS to certify the nonnegativity of a polynomial. Their approach is based on properties of symmetric $H^+$-matrices and the fact that polynomials that correspond to symmetric $H^+$-matrices are nonnegative polynomials. 
Note that $H^+$-tensors corresponds to a high-order generalization of $H^+$-matrices. Thus, it is relevant to consider whether $H^+$-tensors can be used to certify the nonnegativity of a polynomial. In Section~\ref{part:application} we introduce results that allow to use polynomials whose coefficients are given by $H^+$-tensors 
(see Proposition~\ref{th:ddtpsd}
and 
Proposition~\ref{th:sddtpsd})
to obtain  alternative approaches for the approximation of polynomial optimization problems. We illustrate our results by presenting and analyzing the numerical results obtained in Table~\ref{tab:comparsion_2} and Table~\ref{tab:comparsion_3}. In particular, we show the use of {$H^+$-tensors induced} polynomials can provide a good trade-off between the tightness and the effort required to obtain approximations for polynomial optimization problems.


For ease of exposition, in what follows, we use small letters $a,b,\dots$ for scalars and vectors; capital letters $A,B, \dots$ for matrices; calligraphic letters~$\mathcal{A}, \mathcal{B}, \dots$ for tensors and~$\mathscr{A}, \mathscr{B},\dots $ for index sets; and blackboard bold letters $\mathbb{T}, \mathbb{D}, \dots$ for other kinds of sets or spaces in this work.

The remaining of the article is structured as follows: Section \ref{part:pre} introduces additional notation, definitions and some basic results. In Section \ref{part:dd_sdd}, the characterizations of symmetric~$H^+$-tensors are presented. With these characterizations, we provide a way to check if a tensor is a symmetric $H^+$-tensor in polynomial time. The applications of these results in polynomial optimization are illustrated in Section \ref{part:application}. Section \ref{part:conclusion} concludes this work. In Appendix, we derive additional results regarding the relationship between $H^+$-tensor induced polynomials and other classes of polynomials. This results are used in Section~\ref{sec:Meigenvalue}, but are also interesting on their own.


\section{Preliminaries}
\label{part:pre}

First we introduce additional notation and fundamental properties of tensors. Let $\mathbb{R}[x]: = \mathbb{R} [ x_1,\dots, x_n ] $ be the set of polynomials in $n$ variables with real coefficients. A polynomial $p\in \mathbb{R}[x]$ is called a sum of squares (SOS) if it can be written as $p = \sum_{i} q_i^2$ for a finite number of polynomials $q_i \in \mathbb{R}[x]$. Tensor $\mathcal{A} \in \mathbb{S}_{m,n}$ is said to have an SOS decomposition if its corresponding polynomial {${\mathcal{A}}x^m$ is an SOS~\citep[see, e.g.,][]{luo2015linear}}. The authors in~\cite{chen2015sos} show that every symmetric $H^+$-tensor has an SOS decomposition. 

\begin{theorem}[\cite{chen2015sos}, Theorem 3.7]
	\label{theo:H_plus_SOS}
	Let $m, n \in \mathbb{N}$ and $\mathcal{A} \in \mathbb{S}_{m,n}$ be an $H^+$-tensor. If $m$ is even, then $\mathcal{A}$ has an SOS tensor decomposition.
\end{theorem}

From Theorem \ref{theo:H_plus_SOS}, it follows that a symmetric $H^+$-tensor is also a PSD tensor. On the other hand, symmetric $H^+$-tensors can be characterized using the notion of diagonally dominant tensors (see Definition \ref{def:dd_sdd}). Most of the work related to $H^+$-tensors makes use of the diagonal dominance property~\cite[see, e.g.,][]{huang2019iterative,li2014criterions,li2017programmable,wang2017new, zhao2016criterions}. We will also make use of this property in this work. The definitions of diagonally dominant tensors and generalized diagonally dominant tensors are given below.

\begin{definition}[\cite{luo2016completely}, Definition 6.5]
	\label{def:dd_sdd}
	Let $m, n \in \mathbb{N}$ and $ \mathcal{A}= (a_{i_{1} \dots i_m}) \in \mathbb{T}_{m,n}$.
	\begin{enumerate}[label=(\roman*)]
		\item $\mathcal{A}$ is called a diagonally dominant (DD) tensor if 
		\begin{equation}
		\label{inner1:diag}
		|a_{ii\dots i}| \geq \sum_{(i_2,\dots,i_m) \neq (i,\dots,i)} |a_{i i_2 \dots i_m}|, \forall \  i \in [n].
		\end{equation}
		
		\item $\mathcal{A}$ is called a generalized diagonally dominant (GDD) tensor if there exists a positive diagonal matrix $D$ such that the tensor $\mathcal{A} D^{1-m}D\cdots D$ defined as 
		\begin{equation}
		\label{eq:gdd_def1}
		(\mathcal{A}D^{1-m}D\cdots D)_{i_1\dots i_m} = a_{i_1 \dots i_m} d_{i_1}^{1-m} d_{i_2}\cdots d_{i_m}, \ \ \forall  i_1, \dots, i_m \in [n],
		\end{equation}
		is diagonally dominant, where $d_{i} = D_{ii}$ is the $i$th diagonal element of $D$.
		\label{defitemii}
	\end{enumerate}
\end{definition}

From the definition of DD tensors and GDD tensors, one can derive an equivalent definition of GDD tensors that will be useful throughout the article.

\begin{proposition}
	\label{prop: alter_gdd_def}
	Let $m, n \in \mathbb{N}$, then $\mathcal{A} \in \mathbb{T}_{m,n}$ is a GDD tensor if and only if there exists a positive diagonal matrix $D$ such that the tensor $\mathcal{A} DD\dots D$ defined as 
	\begin{equation}
	\label{eq:gdd_def2}
	(\mathcal{A}DD\cdots D)_{i_1\dots i_m} = a_{i_1 \dots i_m} d_{i_1}d_{i_2}\cdots d_{i_m}, \ \ \forall  i_1,  \dots, i_m \in [n],
	\end{equation}
	is diagonally dominant, where $d_{i} = D_{ii}$ is the $i$th diagonal element of $D$. If~$\mathcal{A} \in \mathbb{S}_{m,n}$, then $\mathcal{A} DD\cdots D \in \mathbb{S}_{m,n}$.
\end{proposition}
\begin{proof}
	From Definition~\ref{def:dd_sdd}\ref{defitemii}, if $\mathcal{A} = (a_{i_{1} \dots i_m}) \in \mathbb{T}_{m,n}$ is a GDD tensor, then there exists a positive diagonal matrix $D $ such that $\mathcal{A}D^{1-m}D\cdots D$ is a DD tensor. That is for all~$i \in [n]$,
	\begin{equation}
	\label{eq:prop1_prof1}
	|(\mathcal{A}D^{1-m}D\cdots D)_{i\dots i}| \geq \sum_{(i_2,\dots,i_m) \neq (i,\dots,i)}  |(\mathcal{A}D^{1-m}D\cdots D)_{i i_2\dots i_m}| .
	\end{equation}
	 Note that \eqref{eq:prop1_prof1} is equivalent to 
	\begin{equation}
	\label{eq:prop1_prof2}
	|a_{i\dots i}| \geq \sum_{(i_2,\dots,i_m) \neq (i,\dots,i)}  |a_{i \dots i_m} d_{i}^{1-m} d_{i_2}\cdots d_{i_m}|.
	\end{equation}
	Considering that $d_{i} >0 $ for all $i \in [n]$, and multiplying by $d_i^m$ on both sides of~\eqref{eq:prop1_prof2}, we have that
	\begin{equation}
	\label{eq:prop1_prof3}
	|a_{i\dots i} | d_i^m \geq \sum_{(i_2,\dots,i_m) \neq (i,\dots,i)}  |a_{i \dots i_m} | d_{i} d_{i_2}\cdots d_{i_m}
	\end{equation}
	for all $ i \in [n]$. Thus, the tensor $\mathcal{A} DD\dots D$ defined by \eqref{eq:gdd_def2} is a DD tensor.
	
	For the another direction, if the tensor $\mathcal{A} DD\cdots D$ defined by \eqref{eq:gdd_def2} is a DD tensor for a positive diagonal matrix $D $, then inequality \eqref{eq:prop1_prof3} holds for all $i \in [n]$. Dividing both sides of \eqref{eq:prop1_prof3} by $d_i^m > 0$,  we have inequality \eqref{eq:prop1_prof2} which is equivalent to \eqref{eq:prop1_prof1} 	for all $ i \in [n]$ and indicates that $\mathcal{A}$ is a GDD tensor.
\end{proof}

For the remainder of this work, we assume that every tensor is a symmetric tensor unless it is explicitly stated otherwise. Denote by ${DD}_{m,n}$ and ${GDD}_{m,n}$ the set of DD tensors and the set of GDD  tensors in $\mathbb{S}_{m,n}$, respectively. DD and GDD tensors with nonnegative diagonal elements will be referred as DD$^+$ and GDD$^+$ tensors, respectively. Also, denote by $DD^+_{m,n}$ and $GDD^+_{m,n}$ the set of DD$^+$ tensors and the set of GDD$^+$ tensors in $\mathbb{S}_{m,n}$, respectively.

For $n \in \mathbb{N}$, a set $\mathbb{W} \subset \mathbb{R}^n$ is called a cone if $0 \in \mathbb{W}$ and~$x \in \mathbb{W}$ implies~$\lambda x \in \mathbb{W}$ for any $\lambda \geq 0 $. A set $\mathbb{W}$ is called a convex cone if it contains~$\lambda x + \mu y$ for any $x,y \in \mathbb{W}$ and any $\lambda, \mu \geq 0$. Given a set $\mathbb{W}$, let $cone(\mathbb{W}) = \{ \lambda x \ | \ x \in \mathbb{W}, \lambda \geq 0 \}$ be the {\em conic hull} of $\mathbb{W}$; and $convex(\mathbb{W}) = \{ \lambda x + \mu y \ | \ x, y \in \mathbb{W}, \lambda ,\mu \geq  0, \lambda + \mu = 1 \}$ be the {\em convex hull} of $\mathbb{W}$.



Clearly, for $m,n \in \mathbb{N}$, $DD_{m,n}$ is a cone and $DD^+_{m,n}$ is a convex cone. We will show that~$GDD^+_{m,n}$ is also a convex cone later (see Proposition \ref{prop:convex_cone_GDD}). Next we present a characterization of symmetric $H$-tensors using symmetric GDD tensors.

\begin{theorem}[\cite{kannan2015some} Theorem 4.9]
	\label{them:gdd_h}
	Let $m, n \in \mathbb{N}$ and $\mathcal{A} \in \mathbb{S}_{m,n}$. Then $\mathcal{A}$ is an~$H$-tensor if and only if $\mathcal{A} \in GDD_{m,n}$.
\end{theorem}

\begin{corollary}
	\label{coro:gdd_h}
	Let $m, n \in \mathbb{N}$ and $\mathcal{A} \in \mathbb{S}_{m,n}$. Then $\mathcal{A}$ is an $H^+$-tensor if and only if $\mathcal{A} \in GDD^+_{m,n}$.
\end{corollary}

From Theorem \ref{theo:H_plus_SOS} and Corollary \ref{coro:gdd_h}, if $m$ is even, we have the following inclusion relationships:
\begin{equation*}
DD^+_{m,n} \subseteq GDD^+_{m,n} \subseteq PSD_{m,n}.
\end{equation*}
In light of Corollary \ref{coro:gdd_h}, in what follows we will take the liberty to use both $H^+$ and GDD$^+$ interchangeably to refer to $H^+$-tensors. 

Denote $\operatorname{card}(A)$ as the cardinality of the set $A$. For $m, n \in \mathbb{N}$, define the index sets
\[
\mathscr{D}_{n}^m = \{(i_1, \dots, i_m) \ | \ 1 \leq i_1 \leq \cdots \leq i_m \leq n  \} \cap  \{(i_1, \dots , i_m): \operatorname{card}(\{i_1, \dots, i_m\}) > 1\} ,
\]
and
\[
\mathscr{F}_{n}^m = \{ (\underbrace{i,i,\dots, i}_{m}) \ | \ i \in [n] \}.
\]

For any index $(i_1,\dots, i_m) \in \mathscr{D}_{n}^m \cup \mathscr{F}_{n}^m$,  denote $\mathscr{P}_{i_1  \dots i_m} $ as the set of all permutations of~$i_1, \dots, i_m$ and denote 
\[
\mathscr{Q}_{i_1  \dots i_m} = \{(\underbrace{p,p, \dots, p}_{m}) \ | \ p \in \{ i_1, \dots i_m  \}\}.\]
 Also, for $(i_1,\dots,i_m) \in \mathscr{D}_{n}^m \cup \mathscr{F}_{n}^m$, let $\mathbb{D}_{m,n}^{i_1  \dots i_m} \in  \mathbb{S}_{m,n}$ be the set of sparse tensors defined as follows:
\begin{equation}
\label{eq:def_D_mn_i}
	\mathbb{D}_{m,n}^{i_1  \dots i_m} = \{  (a_{j_1  \dots j_m}) \in\mathbb{S}_{m,n} \ |\  a_{j_1 \dots j_m} = 0 \text{ \ if \ } (j_1, \dots ,j_m) \notin \mathscr{P}_{i_1\dots i_m}  \cup\mathscr{Q}_{i_1  \dots i_m}  \}.
\end{equation}
Further, let
\[
\mathbb{D}_{m,n} =\bigcup_{(i_1,\dots, i_m) \in \mathscr{D}_n^m} \mathbb{D}_{m,n}^{i_1  \dots i_m}.
\]	

To assist the proofs in this work, we introduce the following class of tensors. 
\begin{definition}
	\label{def:two_subclass}
	For $m, n \in \mathbb{N}$ and any $(i_1, \dots, i_m) \in \mathscr{D}_{n}^m $, $c \in \{0 ,1\}$, denote $\mathcal{V}^{c, i_1 \dots i_m} = (v^{c, i_1  \dots i_m}_{j_1  \dots j_m}) \in \mathbb{D}_{m,n}^{i_1  \dots i_m}$,  as the tensor defined by:
	\begin{enumerate}[label=(\roman*)]
		\item $v^{c, i_1   \dots i_m  }_{j_1\dots j_m} = (-1)^c$ if $(j_1,\dots ,j_m) \in \mathscr{P}_{i_1 \dots i_m}$.
		\item  The value of $j$-th diagonal element is equal to the sum of the absolute values of the off-diagonal entries on the $j$-th slice (the diagonal elements are excluded in the sum); that is \\
		\[v_{j j  \dots j  }^{c,i_1 \dots i_m} = \sum_{ (j_2, \dots, j_m ) \neq (j, \dots, j ) } |v_{j j_2  \dots j_m  }^{c,i_1  \dots i_m}|, \forall  \ j\in [n].\]
	\end{enumerate}
Further, for all $i \in [n]$, denote $\mathcal{V}^{0,i i \dots i}$ as the tensor where the only nonzero entry is $v^{0,ii\dots i}_{ii\dots i} = 1$; and $\mathcal{V}^{1,i i \dots i}$ as the tensor with all entries set to 0. Also, denote $\mathbb{E}_{m,n} = \{  \mathcal{V}^{c, i_1 \dots i_m}   \ | \ c \in \{0, 1\},  (i_1, \dots, i_m) \in \mathscr{D}_{n}^m \cup \mathscr{F}_{n}^m   \}  $.
\end{definition}

Clearly, from Definition \ref{def:two_subclass}, it follows that for all $(i_1, \dots, i_m) \in \mathscr{D}_{n}^m \cup \mathscr{F}_{n}^m$ and~$c \in \{0,1\}$, $\mathcal{V}^{c,i_1 \dots i_m} \in DD_{m,n}^+$. For example, when $m = 2$ and $n = 4$, we have
\begin{equation*}
\mathcal{V}^{0,12} = \begin{bmatrix}
1    & 1 & 0 & 0 \\
1       & 1 & 0 &0 \\
0  &  0& 0 & 0\\
0  &  0& 0 &0
\end{bmatrix}, \quad \quad 
\mathcal{V}^{1,13} = \begin{bmatrix}
1    & 0 & -1 & 0 \\
0       & 0 & 0 &0 \\
-1  &  0& 1 & 0\\
0  &  0& 0 &0
\end{bmatrix}.
\quad \quad 
\end{equation*}

For ease of exposition, we also introduce an auxiliary notation for indices. For $m, n \in \mathbb{N}$, index $ {\vec{i}}  :=(i_1, i_2,\dots, i_m) \in  \mathscr{D}_n^m $ and some $l^{{\vec{i}}} \in[m]$, we call 
\[
(( { j_1^{\ii}, j_2^{\ii}, \dots, j^{\ii}_{l^{\ii}} }) , ( {\alpha_1^{\ii}, \alpha_2^{\ii}, \dots, \alpha^{\ii}_{l^{\ii}} }) ) \in { [n]^{l^{{\vec{i}}}} \times [m]^{l^{{\vec{i}}}}}
\]
as the tight pair of ${\vec{i}}$ if $( { j_1^{\ii}, j_2^{\ii}, \dots, j^{\ii}_{l^{\ii}} }) $ and $( {\alpha_1^{\ii}, \alpha_2^{\ii}, \dots, \alpha^{\ii}_{l^{\ii}} }) $ satisfy 
\begin{equation}
\label{eq:tightpair}
x_{i_1} x_{i_2} \dots x_{i_m} = x_{j_1^{{\vec{i}}}}^{\alpha_1^{{\vec{i}}}} x_{j_2^{{\vec{i}}}}^{\alpha_2^{{\vec{i}}}} \dots x_{j_{l^{{\vec{i}}}}^{{\vec{i}}}}^{\alpha_{l^{{\vec{i}}}}^{{\vec{i}}}},
\end{equation}
where $ 1 \leq j_1^{{\vec{i}}} < j_2^{{\vec{i}}} < \dots < j_{l^{{\vec{i}}}}^{{\vec{i}}} \leq n$. We will refer to~$( { j_1^{\ii}, j_2^{\ii}, \dots, j^{\ii}_{l^{\ii}} }) $ as the tight index and to $( {\alpha_1^{\ii}, \alpha_2^{\ii}, \dots, \alpha^{\ii}_{l^{\ii}} }) $ as the tight power. However, we will routinely drop the upper $\vec{i}$ in the notation when the $\vec{i}$ we are referring to is clear from (or fixed in) the context. Also, denote $e_j $ as the unitary vector in the $j$th direction of appropriate dimensions.



\section{New characterization of symmetric $H^+$-tensors}
\label{part:dd_sdd}



Next, we present a new characterization of symmetric $H^+$-tensors (or equivalently GDD$^+$ tensors (cf., Corollary \ref{coro:gdd_h})) based on the {\em power cone}~\cite{chares2009cones,hien2015differential}. First, we characterize DD$^+$ tensors with the following result.

\begin{proposition}
	\label{prop:DDT_cone}
	For $m, n \in \mathbb{N}$, $DD^+_{m,n} = convex(cone(\mathbb{E}_{m,n}))$ and each tensor in $\mathbb{E}_{m,n}$ generates an extreme ray of $ DD^+_{m,n} $.
\end{proposition}

\begin{proof}
	First, from Definition \ref{def:two_subclass}, it follows that $\mathbb{E}_{m,n} \subseteq DD^+_{m,n}$. This, together with the fact that $DD_{m,n}^+$ is a convex cone, implies that $convex(cone(\mathbb{E}_{m,n})) \subseteq DD^+_{m,n} $.
	
	Second, for  $\mathcal{A} = (a_{i_1\dots i_m}) \in DD^+_{m,n}$, denote $  \mathscr{P}_+ =  \{(i_1, \dots, i_m) \in \mathscr{D}_n^m \ | \   a_{i_1i_2\dots i_m} \geq 0  \}$ and $ \mathscr{P}_- =  \{(i_1,\dots, i_m)\in \mathscr{D}_n^m \ | \  a_{i_1i_2\dots i_m} < 0  \}$. Then 
	\begin{flalign}
	\label{eq:DD_cone}
	\mathcal{A} = &\sum_{i = 1}^n \left(a_{i i \dots i} - \sum_{(i_2,\dots,i_m) \neq (i,\dots,i)} |a_{i i_2 \dots i_m}|\right) \mathcal{V}^{0, i i \dots i} \\
	+ &\sum_{ (i_1,i_2,\dots, i_m) \in \mathscr{P}_+ } a_{i_1 i_2 \dots  i_m} \mathcal{V}^{0, i_1i_2 \dots i_m}  +  \sum_{ (i_1,i_2,\dots, i_m) \in \mathscr{P}_- }( - a_{i_1 i_2 \dots  i_m}) \mathcal{V}^{1, i_1i_2 \dots i_m} \nonumber.
	\end{flalign}
	
	Since $\mathcal{A} \in DD_{m,n}^+$, $a_{i i \dots i} \geq  \sum_{(i_2,\dots,i_m) \neq (i,\dots,i)} |a_{i i_2 \dots i_m}|$ for all $i \in [n]$. Thus, $\mathcal{A} $ is in the convex hull of the conic hull of $\mathbb{E}_{m,n}$, after noticing that all the coefficients in the right hand side of \eqref{eq:DD_cone} are nonnegative. That is $DD^+_{m,n} \subseteq convex(cone(\mathbb{E}_{m,n}))$.
\end{proof}




To give a similar characterization for GDD$^+$ tensors, we need Theorem \ref{lemma:nonnegative_tensor_pho} and \ref{lemma:nonnegative_tensor_max} and Propositions \ref{prop:nonnegative_tensor_sum} and \ref{prop:z_tensor_m_tensor}.

\begin{theorem}[\cite{qi2013symmetric}, Theorem 1 (a)]
	\label{lemma:nonnegative_tensor_pho}
	For $m, n \in \mathbb{N}$, if $\mathcal{D} \in \mathbb{S}_{m,n}$ is a nonnegative tensor, then $\rho(\mathcal{D})$ is an $H$-eigenvalue of $\mathcal{D}$. 
\end{theorem}


Denote the largest $H$-eigenvalue of tensor $\mathcal{A} \in \mathbb{S}_{m,n}$ as $\lambda_{\text max}(\mathcal{A})$. 
\begin{theorem}[\cite{qi2013symmetric}, Theorem 2]
	\label{lemma:nonnegative_tensor_max}
	For $m, n \in \mathbb{N}$, if $\mathcal{A} \in \mathbb{S}_{m,n}$ is a nonnegative tensor, then
	\[
	\lambda_{\text max}(\mathcal{A}) = {\max} \left\{  \mathcal{A} x^m: x\in \mathbb{R}^n_+, \sum_{i=1}^n x_i^m = 1 \right\}.
	\]
\end{theorem}

\begin{proposition}
	\label{prop:nonnegative_tensor_sum}
	For $m, n \in \mathbb{N}$, if both $\mathcal{A} \in \mathbb{S}_{m,n}$ and $\mathcal{B} \in \mathbb{S}_{m,n}$ are nonnegative tensors, then $\rho(\mathcal{A} + \mathcal{B}) \leq \rho(\mathcal{A}) + \rho(\mathcal{B})$.
\end{proposition}
\begin{proof} 
	Let $\mathcal{D} \in \mathbb{T}_{m,n}$. From the definition of $\rho(\mathcal{D})$ and $\lambda_{\text max}(\mathcal{D})$, it clearly follows that $\rho(\mathcal{D}) \geq \lambda_{\text max}(\mathcal{D})$. If $\mathcal{D}$ is a symmetric nonnegative tensor, it then follows from Theorem \ref{lemma:nonnegative_tensor_pho} that 
	\begin{equation}
	\label{eq:rho_inequality_pf}
	\rho(\mathcal{D}) = \lambda_{\text max}(\mathcal{D}).
	\end{equation}
	Let $\mathcal{A} \in \mathbb{S}_{m,n}$, and $\mathcal{B} \in \mathbb{S}_{m,n}$ be nonnegative tensors. Then we have from equation \eqref{eq:rho_inequality_pf} that $\rho(\mathcal{A}) = \lambda_{\text max}(\mathcal{A})$ and $\rho(\mathcal{B}) = \lambda_{\text max}(\mathcal{B})$. Furthermore, from Theorem \ref{lemma:nonnegative_tensor_max}, we have 
	\begin{flalign*}
	\lambda_{\text max}(\mathcal{A} + \mathcal{B}) &= {\max} \left\{  (\mathcal{A} + \mathcal{B}) x^m: x\in \mathbb{R}^n_+, \sum_{i=1}^n x_i^m = 1 \right\} \\ 
	& = {\max} \left\{  \mathcal{A} x^m + \mathcal{B} y^m : x,y\in \mathbb{R}^n_+, \sum_{i=1}^n x_i^m = 1, \sum_{i=1}^n y_i^m = 1, x = y\right\} \\ 
	& \leq {\max} \left\{  \mathcal{A} x^m: x\in \mathbb{R}^n_+, \sum_{i=1}^n x_i^m = 1\right\} + {\max} \left\{  \mathcal{B} y^m: y\in \mathbb{R}^n_+, \sum_{i=1}^n y_i^m = 1\right\} \\
	&	= \lambda_{\text max}(\mathcal{A} ) + \lambda_{\text max}(\mathcal{B}).
	\end{flalign*}
	
	To finish, notice that $\mathcal{A} + \mathcal{B}$ is a symmetric nonnegative tensor. Thus after using equation \eqref{eq:rho_inequality_pf} for the tensor $\mathcal{A} + \mathcal{B}$, we conclude that $\rho(\mathcal{A} + \mathcal{B}) = \lambda_{\text max}(\mathcal{A} + \mathcal{B}) \leq  \lambda_{\text max}(\mathcal{A}) +  \lambda_{\text max}(\mathcal{B}) = \rho(\mathcal{A}) + \rho(\mathcal{B}) $.
\end{proof}

\begin{proposition}[\cite{kannan2015some}, Proposition 2.7]
	\label{prop:z_tensor_m_tensor}
	For $m, n \in \mathbb{N}$, let $\mathcal{B} \in \mathbb{S}_{m,n}$ be a $Z$-tensor such that $\mathcal{A} \leq \mathcal{B}$ where $\mathcal{A}$ is an $M$-tensor. Then $\mathcal{B}$ is also an $M$-tensor.
\end{proposition}

\begin{proposition}
	\label{prop:convex_cone_GDD}
	For $m, n \in \mathbb{N}$, $GDD_{m,n}^+$ is a convex cone.
\end{proposition}
\begin{proof}
	Let $\mathcal{A} = (a_{i_1\dots i_m})\in GDD_{m,n}^+  $ and $\mathcal{B}  = (b_{i_1\dots i_m})\in  GDD_{m,n}^+  $. From Corollary~\ref{coro:gdd_h}, both $\mathcal{A}$ and $\mathcal{B}$ are symmetric $H^+$-tensors. Thus $M(\mathcal{A})$ and $M(\mathcal{B})$ are symmetric $M$-tensors. That is, there exist nonnegative scalars $s_1, s_2$ and nonnegative tensors $\mathcal{D}_1$ and~$\mathcal{D}_2$ such that $M(\mathcal{A}) = s_1 I - \mathcal{D}_1$, $M(\mathcal{B}) = s_2 I - \mathcal{D}_2$ and $s_1 \geq \rho(\mathcal{D}_1)$, $s_2 \geq \rho(\mathcal{D}_2)$. Then~$M(\mathcal{A}) + M(\mathcal{B}) = (s_1 + s_2)I - (\mathcal{D}_1 + \mathcal{D}_2)$. Since $s_1 + s_2 \geq 0$ and $D_1 + D_2$ is a nonnegative tensor, $M(\mathcal{A}) + M(\mathcal{B})$ is a symmetric $Z$-tensor. Also, from Proposition~\ref{prop:nonnegative_tensor_sum}, if follows that~$\rho(\mathcal{D}_1 + \mathcal{D}_2) \leq \rho(\mathcal{D}_1 ) + \rho(\mathcal{D}_2) \leq s_1 + s_2$. Thus, $M(\mathcal{A}) + M(\mathcal{B})$ is also a symmetric $M$-tensor.
	
	
	Next, we prove that $M(\mathcal{A}+\mathcal{B})$ is a $Z$-tensor. Recall that $M(\mathcal{A}+\mathcal{B})$ is the comparison matrix of $\mathcal{A}+\mathcal{B}$. Thus, all its diagonal elements are nonnegative and all off-diagonal elements are nonpositive. Denote $s = { \max}\{ |a_{ii\dots i}| + |b_{ii\dots i}| ,  i\in[n]  \}$. Then $M(\mathcal{A}+\mathcal{B}) = s I - (sI -M(\mathcal{A}+\mathcal{B}) )$ where $sI -M(\mathcal{A}+\mathcal{B})$ is a nonnegative tensor. Thus, $M(\mathcal{A}+\mathcal{B}) $ is a $Z$-tensor.
	
	
	From the definition of comparison tensors and the fact that $\mathcal{A}, \mathcal{B}$ have nonnegative diagonal elements, $M(\mathcal{A}+\mathcal{B}) \geq M(\mathcal{A}) + M(\mathcal{B})$ componentwise. From the fact that $M(\mathcal{A}) + M(\mathcal{B})$ is an $M $-tensor and $M(\mathcal{A}+\mathcal{B})$ is a $Z$-tensor, it follows from Proposition~\ref{prop:z_tensor_m_tensor} that $M(\mathcal{A}+\mathcal{B})$ is also an $M$-tensor. Thus $\mathcal{A}+\mathcal{B}$ is a symmetric $H^+ $-tensor, and from Corollary \ref{coro:gdd_h}, $\mathcal{A}+\mathcal{B}$ is a GDD$^+$ tensor. Thus, $\mathcal{A} + \mathcal{B} \in GDD_{m,n}^+$. This, together with the fact that $\mathcal{A} \in GDD_{m,n}^+$ implies~$\lambda \mathcal{A} \in GDD_{m,n}^+$ for any nonnegative scalar $\lambda$, implies that $GDD_{m,n}^+$ is a convex cone.
	
\end{proof}



\begin{theorem}
	\label{theo:gdd_decomp}
	For $m, n \in \mathbb{N}$, $\mathcal{A} \in  GDD_{m,n}^+$ if and only if $\mathcal{A} = \sum_{i =1}^{r} B_i$ where $r \in \mathbb{N}$ and $B_i \in \mathbb{D}_{m,n}  \cap GDD_{m,n}^+$.
\end{theorem}
\begin{proof}
	For $m, n \in \mathbb{N}$, let $\mathcal{A} \in GDD^+_{m,n}$. Then, from Proposition \ref{prop: alter_gdd_def}, there exists a positive diagonal matrix $D$ such that $\mathcal{B}: = \mathcal{A} DD \cdots D \in DD^+_{m,n}$. From Proposition~\ref{prop:DDT_cone}, it follows that there exist $r \in \mathbb{N}$, $\lambda_i \geq 0$, $\mathcal{C}_i \in \mathbb{E}_{m,n} \subset \mathbb{D}_{m,n} \cap DD_{m,n}^+$ for~$ i \in [r]$ such that $\mathcal{B} = \sum_{i=1}^{r} \mathcal{C}_i$. Then $\mathcal{A} = \sum_{i=1}^{r} \mathcal{C}_i D^{-1} \cdots D^{-1} D^{-1}$. Let $\mathcal{B}_i = \mathcal{C}_i D^{-1} \cdots D^{-1} D^{-1}$ for all $ i \in [r]$. Then the {only if} statement follows after noticing that for all $ i \in [r]$, $\mathcal{B}_i \in GDD_{m,n}^+$ and $\mathcal{B}_i \in \mathbb{D}_{m,n}$ (as multiplying with positive numbers will not affect the sparse structure of tensors $\mathcal{C}_i \in \mathbb{D}_{m,n}$, $i \in [r]$). For the if statement, note that if $\mathcal{A} = \sum_{i=1}^r \mathcal{B}_i$ with $\mathcal{B}_i \in \mathbb{D}_{m,n}^+ \cap GDD_{m,n}^+$ for all $i \in [r]$, then, from Proposition \ref{prop:convex_cone_GDD}, we have $\mathcal{A} \in GDD_{m,n}^+$.
\end{proof}

The matrix version of Theorem \ref{theo:gdd_decomp} has been presented in \cite{ahmadi2019dsos,boman2005factor}.

\begin{lemma}[\cite{ahmadi2019dsos}, Lemma 3.8]
	\label{lemma:gdd_matrix_decomp}
	For $n \in \mathbb{N}$, if matrix $A \in \mathbb{S}_{2,n} $, then $A $ is a GDD$^+$ matrix if and only if $A = \sum_{i<j}  M^{ij}$ where each $M^{ij} \in \mathbb{S}_{2,n}$ with zeros everywhere except for four entries $(M^{ij})_{ii}$, $(M^{ij})_{ij}$, $(M^{ij})_{ji}$, $(M^{ij})_{jj}$ which make $M^{ij}$ symmetric and positive semidefinite. 
\end{lemma}


It is easy to see that $M^{ij}$ in Lemma \ref{lemma:gdd_matrix_decomp} is positive semidefinite if and only if $M^{ij}$ is a GDD$^+$ matrix. Thus, Lemma \ref{lemma:gdd_matrix_decomp} can be regarded as a special case of Theorem \ref{theo:gdd_decomp}. In Theorem \ref{theo:gdd_characterization}, we provide sufficient and necessary conditions for a tensor to be in $\mathbb{D}_{m,n} \cap  GDD_{m,n}^+ $ (i.e., a sparse GDD$^+$ tensor). 



\begin{theorem} 
	\label{theo:gdd_characterization}
	Let $m, n \in \mathbb{N}$, $(i_1, \dots, i_m) \in \mathscr{D}_{n}^m \cup  \mathscr{F}_{n}^m$, and a tensor $\mathcal{B} = (b_{p_1  \dots p_m}) \in \mathbb{D}^{i_1   \dots i_m}_{m,n}  $ be given. Then,
	\begin{enumerate}[label=(\roman*)]
		 \item if $(i_1, \dots, i_m) \in \mathscr{D}_{n}^m $, $\mathcal{B} \in GDD^+_{m,n}$ if and only if its entries satisfy 
		 \begin{equation}
		 \label{eq:geo_mean_cone_}
		 \prod_{k=1}^l b_{j_k j_k\dots j_k}^{\alpha_k}   \geq c| b_{i_1 \dots i_m} |^m,
		 \end{equation}
		 where $c = \prod_{k=1}^l {\binom{m-1}{\alpha - e_k} }^{\alpha_k}$, and $((j_1, \dots, j_l), \alpha = (\alpha_1,   \dots. \alpha_l))$ is the tight pair associated with $(i_1,\dots, i_m)$, and 
		 \begin{equation}
		 \label{eq:th_pf_nonnegative_diagonal}
		 b_{pp\dots p} \geq 0,  \forall (pp\dots p) \in \mathscr{Q}_{i_1  \dots i_m}  .
		 \end{equation}  \label{thmgdd_characterization_item1}
		 \item If $(i_1, \dots, i_m) \in \mathscr{F}_n^m$, $\mathcal{B} \in GDD^+_{m,n}$ if and only if $\mathcal{B}$ is a diagonal tensor satisfying $b_{i_1\dots i_m} \geq 0$.
		 \label{thmgdd_characterization_item2}
	\end{enumerate}
\end{theorem}
\begin{proof} Let $(i_1,  \dots, i_m) \in \mathscr{D}_{n}^m $ be given. Denote $((j_1, \dots, j_l), \alpha = (\alpha_1,  \dots. \alpha_l))$ as the tight pair associated with $(i_1, \dots, i_m)$. Let $\mathcal{B} \in \mathbb{D}^{i_1 \dots i_m}_{m,n} $. Then, all the off-diagonal elements of $\mathcal{B}$ are zero except for the elements $b_{p_1 \dots p_m}$, where $ (p_1, \dots ,p_m) \in \mathscr{P}_{i_1\dots i_m} $. Then, using Proposition \ref{prop: alter_gdd_def}, it follows that $\mathcal{B} \in GDD_{m,n}^+$  if and only if its entries satisfy~\eqref{eq:th_pf_nonnegative_diagonal} and 
	\begin{equation}
	\label{eq:geo_mean_cone}
	b_{j_k j_k \dots j_k} d_{j_k}^m \geq \binom{m-1}{\alpha - e_k} | b_{i_1 \dots i_m} | d_{i_1} d_{i_2} \dots d_{i_m},
	\end{equation}
	for $k \in [l]$ and some $d_{j_k}>0$, for all $ k \in [l]$, after using in \eqref{eq:prop1_prof3} the sparsity pattern and symmetry of $\mathcal{B}$, and the fact that the number of equal summands in the right-hand side of \eqref{eq:prop1_prof3} in this case is $ \binom{m-1}{\alpha - e_k}$.
	
	Now note that if \eqref{eq:th_pf_nonnegative_diagonal} and \eqref{eq:geo_mean_cone} hold then \eqref{eq:th_pf_nonnegative_diagonal} and
	\begin{equation}
	\label{eq:geo_mean_cone1}
	b_{j_k j_k \dots j_k} ^{\alpha_k} d_{j_k}^{m \alpha_k } \geq \binom{m-1}{\alpha - e_k}^{\alpha_k}  |b_{i_1 \dots i_m}|^{\alpha_k} d_{i_1}^{\alpha_k} d_{i_2}^{\alpha_k} \dots d_{i_m}^{\alpha_k},
	\end{equation}
	hold for all $k \in [l]$, and some $d_{j_k} > 0$, for all $k \in [l]$; since~\eqref{eq:geo_mean_cone1} is obtained by taking the $\alpha_k$th power on both sides of \eqref{eq:geo_mean_cone}, whose (multiplicative) terms are all nonnegative. Given that both the left-hand side and the right-hand side of~\eqref{eq:geo_mean_cone1} are nonnegative, it follows, after multiplying the left-hand sides and the right-hand sides of~\eqref{eq:geo_mean_cone1} for all $k \in [l]$, and using the fact that $\|\alpha\|_1 = m$,  that \eqref{eq:th_pf_nonnegative_diagonal} and~\eqref{eq:geo_mean_cone1} imply \eqref{eq:th_pf_nonnegative_diagonal} and
	\begin{equation} 
	\label{eq:sdd_characterization_pf_1}
	\prod_{k=1}^l (	b_{j_k j_k \dots j_k} ^{\alpha_k} d_{j_k}^{m \alpha_k }) \geq  \left (\prod_{k=1}^l \binom{m-1}{\alpha - e_k}^{\alpha_k} \right ) |b_{i_1  \dots i_m}|^m  (d_{i_1} d_{i_2} \dots d_{i_m})^m,
	\end{equation}
	for some $d_{j_k}>0$, for all $k \in [l]$. In turn, \eqref{eq:sdd_characterization_pf_1} is equivalent to~\eqref{eq:geo_mean_cone_}, with $c :=  \prod_{k=1}^l \binom{m-1}{\alpha - e_k}^{\alpha_k}$, after noticing that from the definition of tight pair~\eqref{eq:tightpair}, it follows that 
	\begin{equation}
	\label{eq:tightpair2}
	\prod_{k=1}^l d_{j_k}^{\alpha_k } = d_{i_1} d_{i_2} \dots d_{i_m}.
	\end{equation}
	Now, to complete the proof, we show that \eqref{eq:th_pf_nonnegative_diagonal} and~\eqref{eq:geo_mean_cone_} imply \eqref{eq:th_pf_nonnegative_diagonal} and~\eqref{eq:geo_mean_cone} (i.e., that $\mathcal{B}$ is a $GDD^+_{m,n}$ tensor). First note that if for any $k \in [l]$, $b_{j_k j_k \dots j_k} = 0$, then~\eqref{eq:geo_mean_cone_} implies that $b_{i_1  \dots i_m}=0$. Thus, in this case, given \eqref{eq:th_pf_nonnegative_diagonal} and the fact that $d_{j_k} > 0$ for all $k \in [l]$, it follows that~\eqref{eq:geo_mean_cone} is satisfied for all $k \in [l]$. Moreover, in the case where $b_{i_1 \dots i_m}=0$, condition~\eqref{eq:geo_mean_cone} follows from~\eqref{eq:th_pf_nonnegative_diagonal}, given the fact that $d_{j_k} > 0$ for all $k \in [l]$. Thus, it is enough to consider the case in which $b_{j_k j_k \dots j_k} > 0$ for all $k \in [l]$, and $b_{i_1  \dots i_m} \not = 0$. In this case, using the fact that $d_{j_k} > 0$, we can write that 
	\begin{equation} 
	\label{eq:ddef}
	d_{j_k}= z_k \sqrt[m]{\frac{\binom{m-1}{\alpha - e_k}}{b_{j_k j_k \dots j_k} }},
	\end{equation}
	for some $z_k>0$, for all $k \in [l]$. Thus, for any $k \in [l]$, it follows that 
	\begin{equation} 
	\label{eq:sparse_tensor_pf}
	|b_{i_1 \dots i_m} | d_{i_1}   \dots d_{i_m} = z_k^m|b_{i_1  \dots i_m}|  \sqrt[m]{ \frac{c}{  \Pi_{k=1}^l b_{j_k j_k\dots j_k}^{\alpha_k} }} \leq z_k^m = \frac{b_{j_k j_k \dots j_k} d_{j_k}^{m }  }{  \binom{m-1}{\alpha - e_k}},
	\end{equation}
	where the first equality follows by using~\eqref{eq:tightpair2},~\eqref{eq:ddef}, and the definition of $c$; the inequality follows from~\eqref{eq:geo_mean_cone_}, and the last equality follows by using~\eqref{eq:ddef} again. After noticing that~\eqref{eq:sparse_tensor_pf} is equivalent to~\eqref{eq:geo_mean_cone}, it then follows that \eqref{eq:th_pf_nonnegative_diagonal} and~\eqref{eq:geo_mean_cone_} imply \eqref{eq:th_pf_nonnegative_diagonal} and~\eqref{eq:geo_mean_cone}; that is, that $\mathcal{B} \in GDD^+_{n,m}$.
	
	If $(i_1, \dots, i_m) \in \mathscr{F}_n^m$ and tensor $\mathcal{B} = (b_{p_1  \dots p_m}) \in \mathbb{D}^{i_1   \dots i_m}_{m,n}  $, it follows from the definition of $\mathbb{D}^{i_1   \dots i_m}_{m,n}  $ (i.e. \eqref{eq:def_D_mn_i}) that $\mathcal{B}$ is a diagonal tensor in which the only nonzero entry is  $b_{i_1\dots i_m}$. Thus, $\mathcal{B} \in GDD^+_{m,n}$ tensor if and only if $\mathcal{B}$ is a diagonal tensor satisfying $b_{i_1\dots i_m} \geq 0$. 
\end{proof}

Next, we apply Theorem~\ref{theo:gdd_decomp} and Theorem~\ref{theo:gdd_characterization} to obtain sufficient and necessary conditions for a tensor $\mathcal{A} \in \mathbb{S}_{m,n}$ to be an $H^+$-tensor (or equivalently GDD$^+$ tensor).

\begin{corollary}
	\label{col:fullGDDplus}
	Let $m, n \in \mathbb{N}$. Then $\mathcal{A} = (a_{p_1 p_2 \dots p_m}) \in \mathbb{S}_{m,n}$ is a GDD$^+$ tensor if and only if there exist $b^{\vec{i}}_{j} \ge 0$ for all $\vec{i} = (i_1,\dots,i_m) \in \mathscr{D}_n^m$,
	$j \in {\vec{i}}$ satisfying
	\begin{enumerate}[label = (\roman*)]
			\item For $\vec{i} \in \mathscr{D}_n^m$, 
		\begin{equation}
		\label{eq:gdd_corollary2}
		\prod_{k=1}^{l^{{\vec{i}}}} 
		(b^{{\vec{i}}}_{j_k})^{\alpha_k^{{\vec{i}}}}  \geq c({\vec{i}}) | a_{\vec{i}} |^m 
		\end{equation}
		where  $c({\vec{i}}) = \prod_{k=1}^{l^{\vec{i}}} {\binom{m-1}{\alpha^{\vec{i}} - e_k} }^{\alpha^{\vec{i}}_k}$, and $((j^{\vec{i}}_1,j^{\vec{i}}_2, \dots, j^{\vec{i}}_{l^{\vec{i}}}),\alpha^{\vec{i}} =  (\alpha^{\vec{i}}_1, \alpha^{\vec{i}}_2, \dots. \alpha^{\vec{i}}_{l^{\vec{i}}}))$ is the tight pair associated with $\vec{i} $.
		\label{col:fullGDDplusitem1}
				\item For $j \in [n]$, 
		\begin{equation}
			\label{eq:gdd_corollary1}
			a_{jj\dots j} \geq  \sum_{\vec{i} \in  \mathcal{D}_{n}^m: j \in \vec{i}} b^{\vec{i}}_{j}.
		\end{equation}
	\end{enumerate}
\end{corollary}
\begin{proof}
	Let $m, n \in \mathbb{N}$. From Theorem~\ref{theo:gdd_decomp}, $\mathcal{A} = (a_{p_1 p_2 \dots p_m}) \in \mathbb{S}_{m,n}$ is a GDD$^+$ tensor if and only if 
	\begin{equation}
		\label{eq:geo_mean_cone_corollary_sum}
		\mathcal{A} = \sum_{\vec{i} \in \mathscr{D}_{n}^m\cup \mathscr{F}_{n}^m}\mathcal{B}^{{\vec{i}}}
	\end{equation} and for $\vec{i} \in \mathscr{D}_{n}^m\cup \mathscr{F}_{n}^m$, $\mathcal{B}^{{\vec{i}}} \in \mathbb{D}_{m,n}  \cap GDD_{m,n}^+$ satisfies conditions~\ref{thmgdd_characterization_item1} and~\ref{thmgdd_characterization_item2} in Theorem~\ref{theo:gdd_characterization}. Note that from the sparse structure of the tensors $\mathcal{B}^{\vec{i}}$ used in~\eqref{eq:geo_mean_cone_corollary_sum}, it follows that 
for any $j \in [n]$,	
	\begin{equation}
	\label{eq:diagelements}
	a_{jj\dots j} = \sum_{\vec{i} \in \mathscr{D}_{n}^m: (jj\dots j) \in \mathscr{Q}_{\vec{i}}} b^{\vec{i}}_{jj\dots j} + 
	                  
	                      b^{jj\dots j}_{jj\dots j},
\end{equation}
and 
for any $\vec{i} \in \mathscr{D}_{n}^m$,
\begin{equation}
\label{eq:offdiagelements}
a_{\vec{i}} = b^{\vec{i}}_{\vec{i}}.
\end{equation}
From Theorem~\ref{theo:gdd_characterization}\ref{thmgdd_characterization_item1} and~\eqref{eq:offdiagelements}, it follows that $c({\vec{i}})|a_{\vec{i}}|^m =$ $c({\vec{i}})|b^{\vec{i}}_{\vec{i}}|^m$ $\leq \prod_{k=1}^{l^{{\vec{i}}}} 
		(b^{{\vec{i}}}_{j_kj_k\dots j_k})^{\alpha_k^{{\vec{i}}}}$
		where  $c({\vec{i}}) = \prod_{k=1}^{l^{\vec{i}}} {\binom{m-1}{\alpha^{\vec{i}} - e_k} }^{\alpha^{\vec{i}}_k}$,  $((j^{\vec{i}}_1,j^{\vec{i}}_2, \dots, j^{\vec{i}}_{l^{\vec{i}}}),\alpha^{\vec{i}} =  (\alpha^{\vec{i}}_1, \alpha^{\vec{i}}_2, \dots. \alpha^{\vec{i}}_{l^{\vec{i}}}))$ is the tight pair associated with $\vec{i}$, and $b^{{\vec{i}}}_{pp\dots p} \geq 0$, for all $p \in \mathscr{Q}_{{\vec{i}}}$. The statement then follows from this and~\eqref{eq:diagelements}, after noticing that from 
Theorem~\ref{theo:gdd_characterization}\ref{thmgdd_characterization_item2}, $b^{jj\dots j}_{jj\dots j} \ge 0$ for all $j \in [n]$, and after simplifying notation to let $b^{\vec{i}}_{jj\dots j} := b^{\vec{i}}_j$ for any $\vec{i} \in  \mathscr{D}_{n}^m: (jj\dots j) \in \mathscr{Q}_{\vec{i}}$; that is, for any $\vec{i} \in  \mathscr{D}_{n}^m: j \in \vec{i}$.
\end{proof}



Now we provide an example to illustrate the results in Theorem~\ref{theo:gdd_decomp} and 
 Corollary~\ref{col:fullGDDplus}.
\begin{example}
	Consider the following symmetric tensor
	\[
	\mathcal{A} = [ A(1,1,:,:), A(1,2,:,:); A(2,1,:,:), A(2,2,:,:) ] \in \mathbb{S}_{4,2},
	\]
	where 
	\begin{equation*}
		A(1,1,:,:) = \begin{pmatrix}
		4& -2 \\
		-2 & -1
		\end{pmatrix}, 
		A(1,2,:,:) =\begin{pmatrix}
		-2 & - 1\\
		-1 & 64/3
		\end{pmatrix},
		\end{equation*}
			\begin{equation*}
		A(2,1,:,:) = \begin{pmatrix}
		-2 & -1 \\
		-1 & 64/3
		\end{pmatrix},
		A(2,2,:,:) = \begin{pmatrix}
		-1 & 64/3 \\
		64/3 &1000
		\end{pmatrix}.
	\end{equation*}
	
	Denote $D_1 = \begin{pmatrix}
	1 & 0 \\
	0 & 2
	\end{pmatrix} $, $D_2 = \begin{pmatrix}
	1/2 & 0 \\
	0 & 2
	\end{pmatrix} $, $D_3 = \begin{pmatrix}
	1/3 & 0 \\
	0 & 4
	\end{pmatrix} $. Then, we have \[
	\mathcal{A} = \frac{1037}{1296}\mathcal{V}^{0,1111} + 168\mathcal{V}^{0,2222} +  \mathcal{B}^{(1112)} +  \mathcal{B}^{(1122)}+  \mathcal{B}^{(1222)},
	\]
	where
	$\mathcal{B}^{(1112)} = \mathcal{V}^{1,1112}D_1 D_1 D_1 D_1 ,  \mathcal{B}^{(1122)}= \mathcal{V}^{1,1122}D_2 D_2 D_2 D_2$ and $   \mathcal{B}^{(1222)}= \mathcal{V}^{0,1222}D_3D_3 D_3 D_3$. Besides, $b^{\vec{i}}_{j}$ = $\mathcal{B}^{\vec{i}}_{jjjj}  \geq 0, j \in  {\vec{i}}$ for $\vec{i} \in \mathscr{D}_2^4$ satisfy~\eqref{eq:gdd_corollary1} and~\eqref{eq:gdd_corollary2}. As a result, $\mathcal{A}$ is a symmetric $H^+$-tensor (GDD$^+$ tensor).
	

	

	
	On the other hand, denote $D = \begin{pmatrix}
	3  & 0 \\
	0 & 1/2
	\end{pmatrix} $. Then \[
	\bar{\mathcal{A}} = \mathcal{A}DDDD =  [ \bar{A}(1,1,:,:), \bar{A}(1,2,:,:); \bar{A}(2,1,:,:), \bar{A}(2,2,:,:) ] ,
	\]
	where \begin{equation*}
	\bar{A}(1,1,:,:) = \begin{pmatrix}
	324 & -27 \\
	-27 & -9/4
	\end{pmatrix}, 
	\bar{A}(1,2,:,:) = \begin{pmatrix}
	-27 & -9/4 \\
	-9/4 & 8
	\end{pmatrix},
		\end{equation*}
	\begin{equation*}
	\bar{A}(2,1,:,:) = \begin{pmatrix}
		-27 & -9/4 \\
		-9/4 & 8
	\end{pmatrix},
	\bar{A}(2,2,:,:) = \begin{pmatrix}
	-9/4 & 8 \\
	8 &125/2
	\end{pmatrix},
	\end{equation*}
	is a DD$^+$ tensor.
\end{example}

\subsection{Checking membership with power cone optimization}

Corollary~\ref{col:fullGDDplus} readily implies that membership in the set of 
$H^+$-tensors can be tested using tractable conic optimization techniques, and more precisely, the {\em power cone}~\citep[see, e.g.,][]{chares2009cones,hien2015differential}. To illustrate this, let us first introduce the {\em high-dimensional power cone}.

\begin{definition}[{High-dimensional power cone~\citep[][Sec. 4.1.2]{chares2009cones}}]
\label{def:highpowercone}
For any $\alpha \in \mathbb{R}^m_+$ such that $e^\intercal \alpha = 1$, the {\em  high-dimensional power cone} is defined by
\begin{equation}
\label{eq:highpowercone}
\mathbb{K}^{(m)}_{\alpha} = \{(x, z) \in \mathbb{R}^m_+ \times \mathbb{R}: x_1^{\alpha_1} \cdots x_m^{\alpha_m} \ge |z| \}
\end{equation}
\end{definition}

Now, for any tensor $\mathcal{A} \in \mathbb{S}_{m,n}$, let
\begin{multline}
\label{eq:F_A}
\mathbb{F}(\mathcal{A}) = \left \{ d^{\vec{i}}_{j} \in \mathbb{R}, \vec{i} \in \mathscr{D}_n^m, j \in {\vec{i}}
\right . : \\  \left . 
\begin{array}{ll}
a_{jj\dots j} \geq  \displaystyle \sum_{\vec{i} \in  \mathcal{D}_{n}^m: j \in {\vec{i}}} d^{\vec{i}}_{j}, &\forall j \in [n]\\
( d^{\vec{i}}_{{i}_1}, \dots,  d^{\vec{i}}_{{i}_m}, c({\vec{i}})^{\frac{1}{m}}a_{{\vec{i}}}) \in \mathbb{K}^{(m)}_{\frac{1}{m}e}, & \forall  \vec{i} \in \mathscr{D}_n^m \\
\end{array}  \right \}
\end{multline}

The next Corollary then follows from Definition~\ref{def:highpowercone} and Corollary~\ref{col:fullGDDplus}.

\begin{corollary}
	\label{cor:F(A)}
	Let $m, n \in \mathbb{N}$. Then $\mathcal{A} = (a_{p_1 p_2 \dots p_m}) \in \mathbb{S}_{m,n}$ is a GDD$^+$ tensor if and only if $\mathbb{F}(\mathcal{A}) \neq \emptyset$.
\end{corollary}

Furthermore, the condition $\mathbb{F}(\mathcal{A}) \neq \emptyset$ in Corollary~\ref{cor:F(A)} can be checked in polynomial time using appropriate {\em interior point methods}~\cite[see, e.g.,][]{renegar2001mathematical}. To show this, we make use of the {\em power cone}, which is a lower-dimensional version of the high-dimensional power cone introduced in Definition~\ref{def:highpowercone}. Namely, 
for any $\alpha \in [0,1]$, the power cone $\mathbb{K}_{\alpha} := \mathbb{K}^2_{\alpha, 1-\alpha} = \{ (x,z) \in \mathbb{R}^2_+ \times \mathbb{R} : x_1^{\alpha} x_2^{1-\alpha} \ge |z| \}$~\citep[see, e.g.][]{koecher1957positivitatsbereiche, nesterov2012towards,roy2018self}. 
As shown in~\cite[][eq. (4.3), Sec. 4.1.2]{chares2009cones}, the higher-dimensional power cone $\mathbb{K}^{(m)}_{\alpha}$ can be decomposed into $m-1$ (low-dimensional) power cones. 
Using this fact, we can rewrite~\eqref{eq:F_A} as follows:
\begin{multline}
\label{eq:F_A_long}
\mathbb{F}(\mathcal{A}) = \left \{ 
\begin{array}{l}
d^{\vec{i}}_{j} \in \mathbb{R}, \vec{i} \in \mathscr{D}_n^m, j \in {\vec{i}}\\
v^{\vec{i}}_l \in \mathbb{R}_+, \vec{i} \in \mathscr{D}_n^m, l \in [m-2]\\
\end{array}
\right . : \\ \left . 
\begin{array}{ll}
a_{jj\dots j} \geq  \displaystyle \sum_{\vec{i} \in  \mathcal{D}_{n}^m: j \in {\vec{i}}} d^{\vec{i}}_{j}, &\forall j \in [n],\\
( d^{\vec{i}}_{{i}_1}, v^{{\vec{i}}}_1, c({\vec{i}})^{\frac{1}{m}}a_{{\vec{i}}}) \in \mathbb{K}_{\frac{1}{m}}, & \forall  \vec{i} \in \mathscr{D}_n^m \\
( d^{\vec{i}}_{{i}_l}, v^{{\vec{i}}}_l, v^{{\vec{i}}}_{l-1}) \in \mathbb{K}_{\frac{1}{m-l+1}}, & \forall  \vec{i} \in \mathscr{D}_n^m, l=2, \dots, m-2 \\
( d^{\vec{i}}_{{i}_{m-1}},  d^{\vec{i}}_{{i}_m}, v^{{\vec{i}}}_{m-2}) \in {\mathbb{K}_{\frac{1}{2}}}, & \forall  \vec{i} \in \mathscr{D}_n^m \\
\end{array}  \right \}
\end{multline}
The relevance of introducing the power cone in~\eqref{eq:F_A_long} is that~\cite{chares2009cones,nesterov2012towards,roy2018self} provide different {\em self-concordant barriers} for the power cone. In short, this means that for any $\mathcal{A} \in \mathbb{S}_{m,n}$, the nonsymmetric conic feasibility system defined by~\eqref{eq:F_A_long}  can be solved in polynomial time using a {\em primal-dual predictor-corrector method}~\citep{wright1997primal}. The reference to nonsymmetric, stems from the fact that the power cone is not symmetric if $\alpha \neq \frac{1}{2}$~\cite{hien2015differential,tunccel2010self}. 
\begin{theorem}
	\label{th:check_gdd}
	For $m, n \in \mathbb{N}$, to check if a tensor in $\mathbb{S}_{m,n}$ is an $H^+$-tensor (GDD$^+$ tensor) is equivalent to solve a power cone optimization problem of size polynomial in $n$ for a fixed $m$.
\end{theorem}
\begin{proof}
The result follows from Corollary~\ref{cor:F(A)}, equation~\eqref{eq:F_A_long}, and the fact that $|\mathscr{D}_{n}^m | = \binom{n+m-1}{m} - n$.
\end{proof}

For a detailed discussion of the properties of, and optimization over the power cone, we direct the reader to~\cite{mosek,chares2009cones}.


\section{Computing the minimum $H$-eigenvalue of $M$-tensors}
\label{sec:Meigenvalue}

The problem of obtaining bounds on the minimum $H$-eigenvalue of $M$-tensors has received significant attention in the literature~\citep{he2014inequalities,huang2018some,li2013new, tian2010inequalities}. This is due to the important role the $M$-tensors play in a wide range of interesting applications~\citep[see,][and the references therein]{huang2018some}. However, these bounds are loose~\citep[see, e.g.,][Table~1]{huang2018some}, and 
even expensive to compute~\citep[see, e.g.,][Table~2]{huang2018some}. Next, we show that  the characterization in Corollary~\ref{cor:F(A)} can be applied to obtain the minimum $H$-eigenvalue of $M$-tensors in polynomial time. For that purpose, we first introduce the following results.

\begin{lemma}[\cite{zhang2014m}, Lemma 2.2] 
	\label{lemma:linear_eigenvalue_tensor}
	For $m,n \in \mathbb{N}$, let $\mathcal{A} \in \mathbb{T}_{m,n}$. Suppose that $\mathcal{B} = a(\mathcal{A} + b \mathcal{I})$, where $a$ and $b$ are two real numbers. Then $\mu$ is an eigenvalue ($H$-eigenvalue) of $\mathcal{B}$ if and only if $\mu = a (\lambda +b)$ and $\lambda$ is an eigenvalue ($H$-eigenvalue) of $\mathcal{A}$.
\end{lemma}
\begin{lemma}
	\label{lemma:H-eigenvalue_Z-tensor}
	For $m,n \in \mathbb{N}$, if $\mathcal{A} = s\mathcal{I} - \mathcal{D}\in \mathbb{S}_{m,n}$ where $\mathcal{D}$ is a nonnegative tensor and $s$ is a scalar, then $s - \rho(\mathcal{D})$ is the minimum $H$-eigenvalue of $\mathcal{A}$.
\end{lemma}
\begin{proof}
	First, from Theorem \ref{lemma:nonnegative_tensor_pho} it follows that $\rho(\mathcal{D})$ is an $H$-eigenvalue of $\mathcal{D}$. Then, from Lemma \ref{lemma:linear_eigenvalue_tensor}, $s - \rho(\mathcal{D})$ is an $H$-eigenvalue of $\mathcal{A}$. Now, assume that $\lambda$ is an $H$-eigenvalue of $\mathcal{A}$. Then, $s - \lambda$ is an $H$-eigenvalue of $\mathcal{D}$. Thus, $\rho(\mathcal{D}) \geq |s - \lambda| \geq s - \lambda $. That is, $\lambda \geq s - \rho(\mathcal{D})$. Thus, $s - \rho(\mathcal{D})$ is the minimum $H$-eigenvalue of $\mathcal{A}$.
\end{proof}

In what follows, for any $\mathcal{A}  \in \mathbb{S}_{m,n}$, let $\lambda_{\min}(\mathcal{A})$ denote the smallest $H$-eigenvalue of $\mathcal{A}$.

\begin{proposition}
	\label{prop:M-tensor_eigenvalue}
	For $m,n \in \mathbb{N}$, if $\mathcal{A} \in \mathbb{S}_{m,n}$ is an $M$-tensor, then for any $\lambda \leq \lambda_{\min}(\mathcal{A})$, $\mathcal{A} - \lambda I$ is also an $M$-tensor. Besides, for any $\lambda > \lambda_{\min}(\mathcal{A})$, $\mathcal{A} - \lambda I$ is not an $M$-tensor.
\end{proposition}
\begin{proof}
	Since $\mathcal{A} \in \mathbb{S}_{m,n}$ is an $M$-tensor, then there exist a nonnegative tensor $\mathcal{D}$ and nonnegative scalar $s \geq  \rho(\mathcal{D})$ such that $\mathcal{A} = sI - \mathcal{D}$. Then, for any $\lambda \leq   \lambda_{\min}(\mathcal{A})$,
	\[
	\mathcal{A} - \lambda I = (s - \lambda)I - \mathcal{D}.
	\]
	From Lemma \ref{lemma:H-eigenvalue_Z-tensor}, $\lambda_{\min}(\mathcal{A}) = s - \rho(\mathcal{D})$. Thus $s - \lambda -  \rho(\mathcal{D}) \geq s - \lambda_{\min}(\mathcal{A}) -  \rho(\mathcal{D}) =  0$. Furthermore, $s - \lambda \geq \rho(\mathcal{D})  \geq 0$. As a result, $\mathcal{A} - \lambda I$ is an $M$-tensor. Now, for some $\lambda > \lambda_{\min}(\mathcal{A})  $, assume $\mathcal{A} - \lambda I$ is an $M$-tensor. Then there exist a nonnegative tensor $\tilde{\mathcal{D}}$ and nonnegative scalar $\tilde{s} \geq \rho(\tilde{\mathcal{D}})$ such that $\mathcal{A} - \lambda I = \tilde{s} I -\tilde{\mathcal{D}}$. Thus $\mathcal{A} = (\lambda + \tilde{s}) I  - \tilde{\mathcal{D}}$. From Lemma \ref{lemma:H-eigenvalue_Z-tensor}, $\lambda_{\min}(\mathcal{A}) = (\lambda + \tilde{s}) - \rho(\tilde{\mathcal{D}})  \geq \lambda$ which contradicts the condition $\lambda > \lambda_{\min}(\mathcal{A})$. Thus, $\mathcal{A} - \lambda I$ is not an $M$-tensor.
\end{proof}

Note that from Corollary~\ref{cor:F(A)}  and the definition of $H^+$-tensors in terms of the comparison tensor (cf., \eqref{eq:comptensor}), one obtains the following characterization for $M$-tensors.

\begin{corollary}
	\label{cor:F_M(A)}
	Let $m, n \in \mathbb{N}$. Then $\mathcal{A} = (a_{i_1 i_2 \dots i_m}) \in \mathbb{S}_{m,n}$ is an $M$-tensor if and only if 
	$a_{i_1 i_2 \dots i_m}\le 0$ for all $(i_1,i_2, \dots, i_m) \in  \mathscr{D}_n^m$, and $\mathbb{F}(\mathcal{A}) \neq \emptyset$.
\end{corollary}

Proposition~\ref{prop:M-tensor_eigenvalue} and the characterization of $M$-tensors in Corollary~\ref{cor:F_M(A)} and~\eqref{eq:F_A_long}, readily provide a way to compute the $H$-eigenvalue of $M$-tensors in polynomial time.

\begin{corollary}
\label{cor:Meigen}
 For $m,n \in \mathbb{N}$, if $\mathcal{A} \in \mathbb{S}_{m,n}$ is an $M$-tensor, then 
 \begin{equation}
 \label{eq:M-tensor_eigenvalue_compute}
 \lambda_{\min}(\mathcal{A}) =  {\max} \left\{  \lambda:  \mathbb{F}(\mathcal{A} - \lambda \mathcal{I}), a_{i_1 i_2 \dots i_m} \le 0, \forall ({i_1,i_2, \dots, i_m}) \in  \mathscr{D}_n^m \right\}.
 \end{equation}
\end{corollary}
\begin{proof}
 From Proposition~\ref{prop:M-tensor_eigenvalue}, it follows that
\[
 \lambda_{\min}(\mathcal{A}) =  {\max} \left\{  \lambda:  \mathcal{A} - \lambda \mathcal{I} \text{ is an $M$-tensor} \right\}.
 \]
The result then follows by using Corollary~\ref{cor:F_M(A)} to characterize the membership in the set of $M$-tensors.
\end{proof}

Equation~\eqref{eq:F_A_long}, and the discussion that follows it means that one can compute the $H$-eigenvalue of an $M$-tensor by solving the power cone optimization problem~\eqref{eq:M-tensor_eigenvalue_compute}. To show the performance of the proposed method to compute the minimum $H$-eigenvalue, we apply it to 
obtain the $H$-eigenvalue of the $M$-tensors considered in 
Example~3.1 and Example~3.2 in~\cite{huang2018some}. Specifically, in Table~\ref{tab:bounds}, we compare the best upper and lower bounds for the $H$-eigenvalue of these $M$-tensors obtained in~\cite{huang2018some}, versus the value of the $H$-eigenvalue of these $M$-tensors obtained using~\eqref{eq:M-tensor_eigenvalue_compute}.

\begin{table}[!htb]
\begin{center}
\begin{tabular}{lrrrrr}
\toprule
& & & \multicolumn{3}{c}{minimum $H$-eigenvalue}\\
\cmidrule{4-6}
                 &   &  & \multicolumn{1}{c}{best lower} & &\multicolumn{1}{c}{best upper} \\
\multicolumn{1}{c}{$M$-tensor} &  \multicolumn{1}{c}{$m$}  &\multicolumn{1}{c}{$n$}  & \multicolumn{1}{c}{bound~\cite{huang2018some}}&  \multicolumn{1}{c}{value~\eqref{eq:M-tensor_eigenvalue_compute}}  &  \multicolumn{1}{c}{bound~\cite{huang2018some}} \\
\midrule
Example~3.1~\cite{huang2018some} &3 & 3& 3.0738 & 5.8046 & 6.8390  \\
Example~3.2~\cite{huang2018some}  & 3& 3& 4.0768 & 7.7442 & 9.0313 \\
\bottomrule
\end{tabular}
\end{center}
\caption{$H$-eigenvalues of $M$-tensors. \label{tab:bounds}}
\end{table}

The results in Table~\ref{tab:bounds} show that  neither the lower or upper bounds for the $H$-eigenvalues are particularly tight in comparison with the actual $H$-eigenvalues. 

All the tests in Table~\ref{tab:bounds} were implemented in \texttt{MATLAB} using the Systems Polynomial Optimization Toolbox (SPOT)~\cite{SPOT}, and the solver \texttt{MOSEK}~\cite{mosek}, using an Intel computer Core i7-4770HQ with 2.20 GHz frequency and 16 GB RAM memory. 


\section{Application on polynomial optimization}
\label{part:application}

Let us begin by introducing some additional notation. Let $\mathbb{R}_{m}[x]: = \mathbb{R}_{m} [ x_1, \dots, x_n ] $ be the set of polynomials in $n$ variables with real coefficients of degree at most~$m$.  Denote $\Sigma_{2m}[x]: = \Sigma_{2m}[ x_1, \dots, x_n ] $ as the cone of SOS in $n$ variables with real coefficients of degree at most $2m$. Let $\mathbb{P}_{m} [x]: = \mathbb{P}_{m}  [ x_1, \dots, x_n ] $ be the cone of nonnegative polynomials in $n$ variables with real coefficients of degree at most~$m$. For ease of exposition, in what follows, we work mainly with homogeneous polynomials. The results presented for homogeneous polynomials can be extended to polynomials by setting one of the homogeneous polynomial variables to 1. For that purpose, let $\mathbb{H}_{m}: = \mathbb{H}_{m}  [ x_1,\dots, x_n ]$ be the set of homogeneous polynomials in $n$ variables with real coefficients of degree $m$.


If $\mathcal{A} $ is a symmetric $H^+$-tensor, then ${\mathcal{A}}x^m$ is an SOS from Theorem \ref{theo:H_plus_SOS}. This fact can be used to have a {\em restricted} (i.e., with a potentially smaller feasible set) optimization problem to approximately solve global optimization problems in polynomial time. To illustrate this, let us first state the well-known characterization of SOS using a {\em Gram matrix}~\cite{choi1995sums}.

\begin{theorem}[{\citep[see, e.g.,][Thm. 2.1]{ahmadi2019dsos}}]
	\label{th:sos_gram}
	For $m \in \mathbb{N}$ and $f(x) \in \mathbb{R}_{2m}[x]$, denote $z(x)$ as the vector with all monomials of degree less than or equal to $m$. Then $f(x)$ is an SOS if and only if $f = z(x)^T Q z(x)$, where $Q \succeq 0$.
\end{theorem}

In Theorem \ref{th:sos_gram}, the matrix $Q$ satisfying $f = z(x)^T Qz(x)$ is called the Gram matrix of $f$~\citep[see, e.g.,][]{choi1995sums}. From Theorem~\ref{th:sos_gram}, optimization over SOS is equivalent to a {\em semidefinite optimization} (SDO) problem
which is solvable in polynomial time~\citep[see, e.g.,]{wright1997primal}. However, in practice it is 
prohibitively time consuming to solve SDOs when the involved polynomial(s) is of high degree and/or with a large number of variables. Given that optimization over SOS can be used to solve polynomial optimization problems~\cite[see, e.g.,][]{anjos2011handbook,blekherman2012semidefinite}, different methods have been proposed to obtain a good feasible solution of SOS optimization problems efficiently~\cite[see, e.g.,][]{ahmadi2019dsos,gatermann2004symmetry,pataki1998rank,weisser2018sparse,zheng2019block}. The authors in~\cite{ahmadi2019dsos} proposed two subclasses of SOS: DSOS and SDSOS which are constructed via DD$^+$ matrices GDD$^+$ matrices (in their work,  they use another name of GDD$^+$ matrices: scaled diagonally dominant (SDD) matrices).

\begin{definition}[\cite{ahmadi2019dsos}, Definition 3.1]
	\label{def:dsos}
	A polynomial $p(x)$ is a diagonally dominant sum of squares (DSOS) if it can be written as 
	\begin{equation}
	\label{eq:def_dsos}
	p(x) = \sum_{i} \gamma_i m_i^2(x) + \sum_{i,j} \beta_{ij}^+ (m_i(x) + m_j(x))^2 +  \sum_{i,j} \beta_{ij}^- (m_i(x) - m_j(x))^2,
	\end{equation}
	for some monomials $m_i(x), m_j(x)$ and some nonnegative scalars $\gamma_i, \beta_{ij}^+,  \beta_{ij}^-$. For $m,n \in \mathbb{N}$, the set of polynomials in $n$ variables and degree $2m$ that are DSOS is denoted by $DSOS_{2m,n}$.
\end{definition}

\begin{definition}[\cite{ahmadi2019dsos}, Definition 3.2]
	\label{def:sdsos}
	A polynomial $p(x)$ is a scaled diagonally dominant sum of squares (SDSOS) if it can be written as 
	\begin{equation}
	\label{eq:def_sdsos}
	p(x) = \sum_{i} \gamma_i m_i^2(x) + \sum_{i \neq j} (\hat{\beta}_{ij}^+ m_i(x) + \tilde{\beta}_{ij}^+ m_j(x))^2 +  \sum_{i\neq j}  (  \hat{\beta}_{ij}^- m_i(x) - \tilde{\beta}_{ij}^+ m_j(x))^2,
	\end{equation}
	for some monomials $m_i(x), m_j(x)$ and some nonnegative scalars $\gamma_i, \hat{\beta}_{ij}^+, \tilde{\beta}_{ij}^+, \hat{\beta}_{ij}^-, \tilde{\beta}_{ij}^-$. For $m,n \in \mathbb{N}$, the set of polynomials in $n$ variables and degree $2m$ that are SDSOS is denoted by $SDSOS_{2m,n}$.
\end{definition}

In \cite[Theorem 3.4]{ahmadi2019dsos} (resp., \cite[Theorem 3.6]{ahmadi2019dsos}), the authors prove that $f \in DSOS_{2m,n} $ (resp., $SDSOS_{2m,n}$) if and only if there is a DD$^+$ (resp., GDD$^+$) matrix $Q$ such that $f= z(x)^T Q z(x)$, where $z(x)$ is the vector with all monomials of degree less than or equal to $m$.




Similar to their results, we also present the polynomials that are induced by DD$^+$ and GDD$^+$ tensors. Let $m,n \in \mathbb{N}$, $(i_1,\dots,i_m) \in {\mathscr{D}}_n^m$ and $((j_1, \dots, j_l), \alpha:= (\alpha_1, \dots, \alpha_l))$ be the tight pair associated with $(i_1, \dots, i_m)$. Define the polynomials
\begin{equation}
\label{eq:f+}
f_{i_1 \dots i_m}^+(x) = \sum_{k=1}^l  \binom{m-1}{\alpha - e_k}  x_{j_k}^m + \binom{m}{\alpha} x_{i_1} \dots x_{i_m},
\end{equation}
\begin{equation}
\label{eq:f-}
f_{i_1 \dots i_m}^-(x)  = \sum_{k=1}^l  \binom{m-1}{\alpha - e_k} x_{j_k}^m - \binom{m}{\alpha} x_{i_1} \dots x_{i_m},
\end{equation}
\begin{equation}
\label{eq:g+}
g_{i_1 \dots i_m}^+(x) = \sum_{k=1}^l \beta_{i_1 \dots i_m}^{(+k)} x_{j_k}^m + \binom{m}{\alpha}   m(i_1,\dots, i_m)^+ x_{i_1} \dots x_{i_m},
\end{equation}
where $\beta_{i_1 \dots i_m}^{(+k)}, k \in [l]$ are nonnegative scalars and 
\begin{equation*}
m(i_1,\dots, i_m)^+ = \sqrt[m]{ \frac{ \prod_{k=1}^l \left(\beta_{i_1 \dots i_m}^{(+k)}\right)^{\alpha_k}}{\prod_{k=1}^l  \binom{m-1}{\alpha - e_k}^{\alpha_k}  }},
\end{equation*}
\begin{equation}
\label{eq:g-}
g_{i_1 \dots i_m}^-(x) = \sum_{k=1}^l \beta_{i_1 \dots i_m}^{(-k)} x_{j_k}^m - \binom{m}{\alpha}   m(i_1,\dots, i_m)^- x_{i_1} \dots x_{i_m},
\end{equation}
where $\beta_{i_1 \dots i_m}^{(-k)}, k \in [l]$ are nonnegative scalars and 
\begin{equation*}
m(i_1,\dots, i_m)^- = \sqrt[m]{ \frac{ \prod_{k=1}^l \left(\beta_{i_1 \dots i_m}^{(-k)}\right)^{\alpha_k}}{\prod_{k=1}^l  \binom{m-1}{\alpha - e_k}^{\alpha_k}  }}.
\end{equation*}


\begin{definition}
	\label{def:ddtpsd}
	For $m,n \in \mathbb{N}$, a polynomial $p(x)$ is a diagonally dominant tensor {homogeneous (DDTH) polynomial} in $n$ variables and degree $m$ if it can be written as 
	\begin{flalign}
	\label{eq:def_ddtpsd}
	p(x) = \sum_{i \in [n]} \gamma_i x_{i}^m +  &\sum_{(i_1,\dots, i_m) \in { \mathscr{D}}_n^m} \beta_{i_1 \dots i_m}^+ 	f_{i_1 \dots i_m}^+(x) +   \sum_{(i_1,\dots, i_m) \in  { \mathscr{D}}_n^m } \beta_{i_1 \dots i_m}^- f_{i_1  \dots i_m}^-(x),
	\end{flalign}
	for some nonnegative scalars $\gamma_i, \beta_{i_1\dots i_m}^+, \beta_{i_1\dots i_m}^-$. The set of DDTH polynomials in $n$ variables and degree $m$ is denoted as $DDTH_{m,n}$.
\end{definition}

The polynomials defined in Definition \ref{def:ddtpsd} and Definition \ref{def:dsos} are closely related.

\begin{proposition}
	$DDTH_{2,n} = DSOS_{2,n} \cap \mathbb{H}_{2}$ for $n \in \mathbb{N}$.
\end{proposition}

\begin{proof}
	Let $n \in \mathbb{N}$ and $p \in DDTH_{2,n}$. Then it follows from \eqref{eq:def_ddtpsd}, \eqref{eq:f+}, \eqref{eq:f-} that 
	\begin{equation}
	\label{eq:dsos_dtsos_2}
	p(x) = \sum_{i \in [n]} \gamma_i x_i^2 + \sum_{i,j \in [n], i\neq j} \beta_{ij}^+ (x_i + x_j)^2 + \sum_{i,j \in [n], i\neq j} \beta_{ij}^-  (x_i - x_j)^2 
	\end{equation}
	for some nonnegative $\gamma_i, i \in [n]$ and $\beta_{ij}^+,\beta_{ij}^- $, $i,j \in [n]$ and $i \neq j$. Comparing \eqref{eq:dsos_dtsos_2} with \eqref{eq:def_dsos}, it is clear that $p \in DSOS_{2,n}\cap \mathbb{H}_{2}$. Next, notice that for $p \in DSOS_{2,n} \cap \mathbb{H}_{2}$ to hold, the monomials in \eqref{eq:def_dsos} must be given by $m_i(x) = x_i,i\in [n]$. Thus, $p \in DSOS_{2,n} \cap \mathbb{H}_{2}$ implies \eqref{eq:dsos_dtsos_2}, which completes the proof.
\end{proof}


\begin{definition}
	\label{def:sddtpsd}
	For $m,n \in \mathbb{N}$, a polynomial $p(x)$ is a generalized diagonally dominant tensor homogeneous (GDDTH) polynomial in $n$ variables and degree~$m$ if it can be written as 
	\begin{flalign}
	\label{eq:def_sddtpsd}
	p(x) = \sum_{i \in [n]} \gamma_i x_{i}^m + & \sum_{(i_1,\dots, i_m) \in {  \mathscr{D}}_n^m } g_{i_1  \dots i_m}^+(x)    +  \sum_{(i_1,\dots, i_m) \in {  \mathscr{D}}_n^m} g_{i_1 \dots i_m}^-(x),
	\end{flalign}
	for some nonnegative scalars $\gamma_i, i \in [n]$. The set of GDDTH in $n$ variables and degree $m$ is denoted as $GDDTH_{m,n}$.
\end{definition}

Similarly, the polynomials in Definition \ref{def:sddtpsd} and Definition~\ref{def:sdsos} are closely related.

\begin{proposition}
	$GDDTH_{2,n} = SDSOS_{2,n} \cap \mathbb{H}_{2}$ for $n \in \mathbb{N}$.
\end{proposition}
\begin{proof}
	Let $n \in \mathbb{N}$ and $p \in GDDTH_{2,n}$. Then, it follows from \eqref{eq:def_sddtpsd}, \eqref{eq:g+}, \eqref{eq:g-} that 
	\begin{equation}
	\label{eq:sdsos_gdtsos_2}
	\begin{aligned}
	p(x) = \sum_{i \in [n]} \gamma_i x_i^2 &+ \sum_{i,j \in [n], i\neq j} \left(\sqrt{\beta_{i j}^{(+1)} }x_{i} +  \sqrt{\beta_{ij}^{(+2)}}x_{j} \right)^2  \\
	&+ \sum_{i,j \in [n], i\neq j} \left(\sqrt{\beta_{i j}^{(-1)} }x_{i} -\sqrt{\beta_{ij}^{(-2)}}x_{j} \right)^2 
	\end{aligned}
	\end{equation} 
	for some nonnegative $\gamma_i, i \in [n]$ and $\beta_{ij}^+,\beta_{ij}^- $, $i,j \in [n]$ and $i \neq j, k\in \{1,2\}$. Comparing with \eqref{eq:def_sdsos}, it is clear that $p \in SDSOS_{2,n} \cap \mathbb{H}_{2}$. Next, notice that for $p \in  SDSOS_{2,n} \cap \mathbb{H}_{2}$ to hold, the monomial in \eqref{eq:def_sdsos} must be given by $m_i(x)= x_i,i \in [n]$. Thus, $p \in  SDSOS_{2,n} \cap \mathbb{H}_{2}$ implies \eqref{eq:sdsos_gdtsos_2}, which completes the proof.
\end{proof}

As mentioned earlier, DDTH and GDDTH polynomials are induced by DD$^+$ tensors and GDD$^+$ tensors, respectively. To formally see this, first denote $\langle \cdot , \cdot \rangle_{m,n}$ as the inner product in $\mathbb{T}_{m,n}$ defined by 
\[
\langle \mathcal{A},\mathcal{B} \rangle_{m,n} = \sum_{i_1,\dots, i_m = 1}^{n} a_{i_1\dots i_m} b_{i_1\dots i_m},
\]
where $\mathcal{A},\mathcal{B}  \in \mathbb{T}_{m,n}$. Notice that when $m = 2$, the inner product $\langle \cdot , \cdot \rangle_{2,n}$ is the Frobenius inner product for matrices. For any tensor $\mathcal{A} \in \mathbb{T}_{m,n}$, define its corresponding polynomial as:
\[
{\mathcal{A}}x^m =  \langle \mathcal{A}, \underbrace {x\otimes \cdots \otimes x}_{m} \rangle_{m,n} = \sum_{i_1,\dots i_m = 1}^n a_{i_1 \dots i_m } x_{i_1}\cdots x_{i_m},
\]

\begin{proposition}
	\label{th:ddtpsd}
	For $m,n \in \mathbb{N}$, a polynomial $p \in DDTH_{m,n}$ if and only if  there is a tensor $\mathcal{A} \in DD^+_{m,n}$ such that 
	$p(x) = \langle \mathcal{A}, x\otimes \cdots \otimes x \rangle$.
\end{proposition}

\begin{proof}
	Assume $p(x) = \langle \mathcal{A}, x\otimes \cdots \otimes x \rangle$ where $\mathcal{A} \in DD^+_{m,n}$. From \eqref{eq:DD_cone},
	\begin{equation}
	\label{eq:pf_dtsos_ddt_1}
	\begin{aligned}
	p(x) = &\sum_{i \in [n]}\gamma_i \langle \mathcal{V}^{0,i i \dots i}, x \otimes \cdots \otimes x \rangle  +  \sum_{(i_1,\dots, i_m) \in {\mathscr{D}}_n^m}  \beta_{i_1 \dots i_m}^+  \langle \mathcal{V}^{0,i_1\dots i_m} , x \otimes \dots \otimes x \rangle\\ &+ \sum_{(i_1,\dots, i_m) \in {\mathscr{D}}_n^m}  \beta_{i_1 \dots i_m}^-  \langle \mathcal{V}^{1,i_1 \dots i_m} , x \otimes \dots \otimes x \rangle,
	\end{aligned}
	\end{equation}
	for some nonnegative $\gamma_i, \beta_{i_1 \dots i_m}^+,  \beta_{i_1 \dots i_m}^- $, $ i \in [n], (i_1,\dots, i_m) \in {\mathscr{D}}_n^m $. For $i \in [n]$, 
	\begin{equation}
	\label{eq:pf_dtsos_ddt_2}
	\langle\mathcal{V}^{0,i i \dots i}, x \otimes \cdots \otimes x \rangle  = x_i^m .
	\end{equation}
	Furthermore, for $(i_1, \dots,i_m) \in {\mathscr{D}}_n^m$,  it follows 
	from Definition \ref{def:two_subclass} that
	\begin{equation}
	\label{eq:pf_dtsos_ddt_3}
	\langle \mathcal{V}^{0,i_1 \dots i_m} , x \otimes \cdots \otimes x \rangle  = f_{i_1  \dots i_m}^+(x),
	\end{equation}
	and
	\begin{equation}
	\label{eq:pf_dtsos_ddt_4}
	\langle \mathcal{V}^{1,i_1 \dots i_m} , x \otimes \cdots \otimes x \rangle  = f_{i_1  \dots i_m}^-(x).
	\end{equation}
	After replacing \eqref{eq:pf_dtsos_ddt_2}, \eqref{eq:pf_dtsos_ddt_3}, \eqref{eq:pf_dtsos_ddt_4} in \eqref{eq:pf_dtsos_ddt_1} and comparing with \eqref{eq:def_ddtpsd}, it follows that $p \in  DDTH_{m,n}$.
	
	Similarly, if $p \in  DDTH_{m,n}$, one obtains \eqref{eq:pf_dtsos_ddt_1}  after replacing \eqref{eq:pf_dtsos_ddt_2}, \eqref{eq:pf_dtsos_ddt_3}, \eqref{eq:pf_dtsos_ddt_4} into \eqref{eq:def_ddtpsd}; which implies that $p(x) = \langle \mathcal{A}, x\otimes \cdots \otimes x \rangle$ for some $\mathcal{A} \in DD^+_{m,n}$.
	
\end{proof}

An analogous result holds for $GDDTH_{m,n}$ .

\begin{proposition}
	\label{th:sddtpsd}
For $m,n \in \mathbb{N}$, a polynomial $p \in GDDTH_{m,n}$ if and only if  there is a tensor $\mathcal{A} \in GDD^+_{m,n}$ such that 
	$p(x) = \langle \mathcal{A}, x\otimes \dots \otimes x \rangle$.
\end{proposition}
\begin{proof}
	Assume $p(x) = \langle \mathcal{A}, x\otimes \cdots \otimes x \rangle $ where $\mathcal{A} \in GDD^+_{m,n}$. Then there exists a diagonal matrix $D$ with positive diagonal entries $d_i, i\in [n]$, such that $\mathcal{B} = \mathcal{A}DD\cdots D$ is a DD$^+$ tensor. Thus
	\begin{align*}
	p(x) = & \langle \mathcal{A} ,x\otimes \cdots \otimes x \rangle \\
	= & \langle  \mathcal{B}D^{-1}D^{-1}\dots D^{-1} ,x\otimes \cdots \otimes x \rangle \\
	= & \langle  \mathcal{B} ,\bar{x}\otimes \cdots \otimes \bar{x} \rangle ,
	\end{align*}
	where $\bar{x} = (x_1 d_1^{-1}, x_2 d_2^{-1}, \dots , x_n d_n^{-1})$. From the proof of Proposition \ref{th:ddtpsd},
	\begin{equation}
	\label{eq:pf_gdsos_gdd_1}
	p(x) = \sum_{i \in [n]} \hat{\gamma}_i \bar{x}_{i}^m +  \sum_{(i_1,\dots, i_m) \in {\mathscr{D}}_n^m } \beta_{i_1 \dots i_m}^+  {f}_{i_1\dots i_m}^+(\bar{x}_{i}) +   \sum_{(i_1,\dots, i_m) \in{\mathscr{D}}_n^m} \beta_{i_1 \dots i_m}^- {f}_{i_1 \dots i_m}^-(\bar{x}_{i}),
	\end{equation}
	where $\hat{\gamma}_i, i \in [n], \beta_{i_1 \dots i_m}^+, \beta_{i_1 \dots i_m}^-, (i_1,\dots, i_m) \in {\mathscr{D}}_n^m$ are nonnegative. Assume $((j_1, \dots, j_l), \alpha:= (\alpha_1,\dots, \alpha_l))$ is the tight pair of $(i_1, \dots ,i_m) $, then
	\begin{equation}
	\label{eq:pf_gdsos_gdd_2}
	\begin{aligned}
	{f}_{i_1 \dots i_m}^+(\bar{x}) &= \sum_{k=1}^l \binom{m-1}{\alpha - e_k}\bar{x}_{j_k}^m + \binom{m}{\alpha} \bar{x}_{i_1} \dots \bar{x}_{i_m} \\
	& =  \sum_{k=1}^l  \binom{m-1}{\alpha - e_k} d_{j_k}^{-m}x_{j_k}^m + \binom{m}{\alpha} d_{i_1}^{-1} \dots d_{i_m}^{-1} x_{i_1} \dots x_{i_m},
	\end{aligned}
	\end{equation}
	\begin{equation}
	\label{eq:pf_gdsos_gdd_3}
	\begin{aligned}
	{f}_{i_1  \dots i_m}^- (\bar{x}) &= \sum_{k=1}^l \binom{m-1}{\alpha - e_k} \bar{x}_{j_k}^m - \binom{m}{\alpha} \bar{x}_{i_1} \dots \bar{x}_{i_m} \\
	& =  \sum_{k=1}^l  \binom{m-1}{\alpha - e_k} d_{j_k}^{-m}x_{j_k}^m - \binom{m}{\alpha} d_{i_1}^{-1} \dots d_{i_m}^{-1} x_{i_1} \dots x_{i_m}.
	\end{aligned}
	\end{equation}
	Now, let $\gamma_i := \hat{\gamma}_i d_{i}^{-m}$ for $i \in [n]$, $\beta_{i_1 \dots i_m}^{(+k)} = \beta_{i_1 \dots i_m}^+\binom{m-1}{\alpha - e_k} d_{j_k}^{-m} \geq 0$ and $\beta_{i_1 \dots i_m}^{(-k)} = \beta_{i_1 \dots i_m}^- \binom{m-1}{\alpha - e_k} d_{j_k}^{-m} \geq 0$ for $(i_1,\dots, i_m) \in \mathscr{D}_n^m$ and $k \in [l] $. Notice that 
	\[
	\beta_{i_1 \dots i_m}^+ d_{i_1}^{-1} \cdots d_{i_m}^{-1}   = \sqrt[m]{ \frac{ \Pi_{k=1}^l (\beta_{i_1 \dots i_m}^{(+k)})^{\alpha_k}}{\Pi_{k=1}^l (\binom{m-1}{\alpha - e_k})^{\alpha_k}  }} = m(i_1, \dots, i_m)^+,
	\]
	and similarly, $\beta_{i_1 \dots i_m}^- d_{i_1}^{-1} \cdots d_{i_m}^{-1}   =m(i_1,\dots, i_m)^- $ for $(i_1,\dots, i_m) \in {\mathscr{D}}_n^m$. Thus, after replacing \eqref{eq:pf_gdsos_gdd_2}, \eqref{eq:pf_gdsos_gdd_3} in \eqref{eq:pf_gdsos_gdd_1}, and using the definitions of ${\gamma}_i, i \in [n]$, $\beta_{i_1 \dots i_m}^{(+k)}$, $\beta_{i_1 \dots i_m}^{(-k)}, (i_1,\dots, i_m) \in {\mathscr{D}}_n^m$ and $k \in [l] $, as well as \eqref{eq:g+} and \eqref{eq:g-}, it follows that $p$ satisfies \eqref{def:sddtpsd}. That is $p \in  GDDTH_{m,n}$.
	
	For the other direction, let $p \in GDDTH_{m,n}$. Then, there exists nonnegative scalars $\gamma_i, \beta_{i_1 \dots i_m}^{(+k)}$, $\beta_{i_1 \dots i_m}^{(-k)}, i \in [n], (i_1,\dots, i_m) \in {\mathscr{D}}_n^m$ such that
	\[
	p(x) = \sum_{i \in [n]} \gamma_i x_{i}^m + \sum_{(i_1,\dots, i_m) \in {\mathscr{D}}_n^m } g_{i_1\dots i_m}^+(x)    +  \sum_{(i_1,\dots, i_m) \in {\mathscr{D}}_n^m } g_{i_1 \dots i_m}^-(x),
	\]
	where $g_{i_1 \dots i_m}^+(x), g_{i_1 \dots i_m}^-(x)$ are defined in equation \eqref{eq:g+} and \eqref{eq:g-} for $(i_1,\dots, i_m) \in {\mathscr{D}}_n^m$. First note that
	\[
	\sum_{i = 1}^n \gamma_i x_{i}^m  =\sum_{i = 1}^n  {\gamma_i}  \langle\mathcal{V}^{0,i i \dots i} ,x\otimes \cdots \otimes x \rangle.
	\]
	Also, for a given $(i_1, \dots, i_m) \in {\mathscr{D}}_n^m$, let $((j_1, \dots, j_l), \alpha = (\alpha_1,  \dots, \alpha_l))$ be its tight pair and denote $d_{j_k}^{-1} := \sqrt[m]{\frac{\beta_{i_1 \dots i_m}^{(+k)}}{ \binom{m-1}{\alpha - e_k} }}, k\in [l]$. Then 
	\begin{flalign*}
	g_{i_1  \dots i_m}^+ (x) =&  \sum_{k=1}^l \beta_{i_1 \dots i_m}^{(+k)} x_{j_k}^m + \binom{m}{\alpha}   m(i_1, \dots, i_m)^+ x_{i_1} \dots x_{i_m} \\
	=& \sum_{k=1}^l \binom{m-1}{\alpha - e_k}     d_{j_k}^{-m}x_{j_k}^m + \binom{m}{\alpha}   d_{i_1}^{-1}\dots d_{i_m}^{-1} x_{i_1} \dots x_{i_m} \\
	=&  \langle \mathcal{V}^{0,i_1\dots i_m} D^{-1} \cdots D^{-1} , x \otimes \cdots \otimes x \rangle \\
	=&  \langle \bar{\mathcal{V}}^{0,i_1\dots i_m}  , x \otimes \cdots \otimes x \rangle,
	\end{flalign*}
	where $D= (d_{ij})$ is an $m$ by $m$ diagonal matrix with diagonal elements 
	\begin{equation*}
	d_{ii} =\begin{cases} 
		 d_{j_k}	&  \text{if $i = j_k$ for some $k \in [l]$}, \\
		 1 & \text{otherwise},
		\end{cases}
	\end{equation*}
	for $i \in [m]$	and 
	\[\bar{\mathcal{V}}^{0,i_1 \dots i_m}  := \mathcal{V}^{0,i_1 \dots i_m} D^{-1} \cdots D^{-1} \in GDD_{m,n}^+.\] 
	Similarly, 
	\begin{flalign*}
	g_{i_1\dots i_m}^-(x) =\langle \bar{\mathcal{V}}^{1,i_1 \dots i_m}  , x \otimes \cdots \otimes x \rangle,
	\end{flalign*}
	where $\bar{\mathcal{V}}^{1,i_1 \dots i_m}  := \mathcal{V}^{1,i_1\dots i_m} \hat{D}^{-1} \cdots\hat{D}^{-1} \in GDD_{m,n}^+$ and $\hat{D} = (\hat{d}_{ij})$ is an $m$ by $m$ diagonal matrix with diagonal elements 
	\begin{equation*}
	d_{ii} =\begin{cases} 
	\sqrt[m]{\frac{\beta_{i_1 \dots i_m}^{(-k)}}{ \binom{m-1}{\alpha - e_1} }}&  \text{if $i = j_k$ for some $k \in [l]$}, \\
	1 & \text{otherwise},
	\end{cases}
	\end{equation*}
	for $i \in [m]$. Thus, from Proposition \eqref{prop:convex_cone_GDD}, it follows that
	\begin{flalign*}
	\mathcal{M}: = \sum_{i \in [n]} {\alpha_i} \mathcal{V}^{0,i i \dots i}  + \sum_{(i_1,\dots, i_m) \in {\mathscr{D} }_n^m  }   \bar{\mathcal{V}}^{0,i_1\dots i_m} + \sum_{(i_1,\dots, i_m) \in  {\mathscr{D} }_n^m  } \bar{\mathcal{V}}^{1,i_1\dots i_m}  \in GDD_{m,n}^+
	\end{flalign*}
	and the result follows the fact that  $p(x) = \langle \mathcal{M}  , x \otimes \dots \otimes x \rangle$.
\end{proof}



From Proposition \ref{th:ddtpsd} and \ref{th:sddtpsd}, $p(x) \in DDTH_{m,n} $ (resp. $GDDTH_{m,n}$) if and only if $p(x) = \langle \mathcal{A} ,x\otimes \dots \otimes x \rangle$ for an $\mathcal{A} \in DD_{m,n}^+$ (resp. $GDD_{m,n}^+$). This polynomial equality can be imposed with a finite set of linear equations in the coefficients of $p(x)$ and the elements of $\mathcal{A}$. Then the diagonally dominant constraints on $\mathcal{A} = (a_{i_1 \dots i_m})$ can be formulated using the linear inequalities: 
\begin{align*}
&a_{ii\dots i} \geq \sum_{(i_2,\dots,i_m) \neq (i,\dots,i)}  z_{i i_2 \dots i_m},  i \in [n], \\
& - z_{i_1 \dots i_m } \leq a_{i_1  \dots i_m} \leq z_{i_1 \dots i_m },  (i_1,\dots, i_m) \in  {\mathscr{D} }_n^m  .
\end{align*}
The number of linear constraints is at most $ n  + 2\binom{n+m-1}{m}$.

The constraints on GDD$^+$ tensors can be formulated using power cone optimization problem of size polynomial in $n$ for fixed $m$ (Theorem~\ref{th:check_gdd}). Thus in both cases, the resulting linear and power cone optimization problems are of polynomial size in $n$ for fixed $m$. Next, we illustrate how the polynomial classes $DDTH_{m,n} $ and $GDDTH_{m,n}$ can be used to address the solution of polynomial optimization problems.



\subsection{Comparison between optimization with $DSOS_{2m,n}$ ($SDSOS_{2m,n}$) and $DDTH_{2m,n}$ ($GDDTH_{2m,n}$)}
\label{subsection:comparsion}

 From Theorem \ref{theo:H_plus_SOS} and Proposition \ref{th:ddtpsd} and \ref{th:sddtpsd}, polynomials in $DDTH_{2m,n}$ and $GDDTH_{2m,n}$ are all nonnegative and from Theorem \ref{th:check_gdd}, membership in these polynomial classes can be checked in polynomial time. As a result, we can make use of them to approximately solve polynomial optimization problems. To illustrate this, we consider the particular problem of finding the smallest $H$-eigenvalue of an even order symmetric tensor and compare the performance of the approximations obtained using the polynomial classes $DSOS_{m,n}$ ($SDSOS_{m,n}$) and optimization on $DDTH_{m,n}$ ($GDDTH_{m,n}$). 
 
 For $m,n \in \mathbb{N}$, denote the smallest $H$-eigenvalue of $\mathcal{A} \in \mathbb{S}_{2m,n}$ as $\lambda_{\text{min}}(\mathcal{A})$. Then, from~\cite{qi2005eigenvalues,qi2013symmetric}, 
\begin{equation}
\label{prob:min_H_eigenvalue}
\lambda_{\text min}(\mathcal{A}) = {\min} \left\{  \mathcal{A} x^{2m}: x\in \mathbb{R}^n, \sum_{i=1}^n x_i^{2m} = 1  \right\}.
\end{equation}

It is well-known that the problem of computing eigenvalues of higher order tensors (i.e., $m \geq 3$) is NP-hard \cite{hillar2013most}. Thus, it is not easy to obtain the optimal value of problem \eqref{prob:min_H_eigenvalue}. On the other hand, its optimal value is easily seen to be equivalent to the optimal value of the following problem:
\begin{flalign}
\label{pro:numerical_test}
\max \left \{ \  \lambda:   \mathcal{A} x^{2m}- \lambda \sum_i^n x_i^{2m} \geq 0,   \forall x \in  \mathbb{R}^n \right \}.
\end{flalign}

For any $\mathbb{K} \subseteq \mathbb{R}_{2m}[x] \cap \mathbb{H}_{2m}[x]$, define the following problem $P^{\mathbb{K}}$:
\begin{flalign}
\label{pro:min_H_eigenvalue_K}
\max \left \{ \lambda  :   \mathcal{A} x^{2m} - \lambda \sum_i^n x_i^{2m}  \in \mathbb{K}, \forall x \in  \mathbb{R}^n \right \}.
\end{flalign}
and denote its optimal value as $\lambda(\mathcal{A})^{\mathbb{K}}$. With this notation, $\lambda_{\text min}(\mathcal{A}) = \lambda(\mathcal{A})^{\mathbb{P}_{2m}[x]}$. From \eqref{pro:min_H_eigenvalue_K}, it follows that $\lambda(\mathcal{A})^{\mathbb{K}} \leq \lambda_{\text min}(\mathcal{A})$ if $\mathbb{K} \subseteq \mathbb{P}_{2m}[x]$. One classical choice of $\mathbb{K}$ is $\Sigma_{2m}[x]\cap \mathbb{H}_{2m}[x]$ and the resulting SDO problem is solvable in polynomial time. However, it is still computationally expensive to solve the resulting SDO problem if either the degree $m$ or the number of variables $n$ is large. Given this, the authors in \cite{ahmadi2019dsos} propose two scalable methods by setting $\mathbb{K} = DSOS_{2m,n}$ and $\mathbb{K} = SDSOS_{2m,n}$. Considering the close relationship with $DSOS_{2m,n}$ and $SDSOS_{2m,n}$, it is natural to consider the choice $\mathbb{K} = DDTH_{2m,n}$ and $\mathbb{K} = GDDTH_{2m,n}$. In what follows, we compare the approximations obtained from these four polynomials classes when \eqref{pro:min_H_eigenvalue_K} is used to approximate the value of problem \eqref{prob:min_H_eigenvalue} from below.

In this numerical test, $ \mathcal{A} x^{2m}$ is set as a homogeneous polynomial with order $4$ and $n$ variables. Its coefficients are sampled from the standard normal distribution. The test is implemented in \texttt{MATLAB} using the Systems Polynomial Optimization Toolbox (SPOT) \cite{SPOT}, and the solver \texttt{MOSEK} \cite{mosek}, using an Intel computer Core i7-4770HQ with 2.20 GHz frequency and 16 GB RAM memory. 

The lower bounds and computational time for solving problem \eqref{pro:min_H_eigenvalue_K} with each method and different number of variables are listed in Table~\ref{tab:comparsion_2} and Table~\ref{tab:comparsion_3}. 

\begin{table}[h!]
	\centering
	\begin{tabular}{l  r r r r} 
		\toprule
		\multicolumn{1}{c}{$\mathbb{K}$} & \multicolumn{1}{c}{$n=5$} & \multicolumn{1}{c}{$n=10$} &\multicolumn{1}{c}{$n=15$}&\multicolumn{1}{c}{$n=20$} \\
		\midrule
		$DSOS_{4,n}$ & -11.7592  & -61.9733 &-170.8438 &-364.0555\\ 
		$SDSOS_{4,n}$ & -9.4565 & -57.4002 & -162.8298 &-352.0931\\
		$DDTH_{4,n}$ & -14.1803 &  -65.4432& -177.6707  & -370.2231\\
		$GDDTH_{4,n}$  &   -11.5839&-61.9366    & -168.7655   &-360.0859 \\
		\bottomrule
	\end{tabular}
	\caption{Comparison of lower bounds on problem \eqref{prob:min_H_eigenvalue} using the restriction \eqref{pro:min_H_eigenvalue_K} for different choices of $\mathbb{K}$.}
	\label{tab:comparsion_2}
\end{table}
\begin{table}[h!]
	\centering
	\begin{tabular}{l r r r r } 
		\toprule
		\multicolumn{1}{c}{$\mathbb{K}$} & \multicolumn{1}{c}{$n=5$} & \multicolumn{1}{c}{$n=10$} &\multicolumn{1}{c}{$n=15$}&\multicolumn{1}{c}{$n=20$} \\ 
		\midrule
		$DSOS_{4,n}$ &  0.0213  & 0.0842  & 0.3833 & 1.1367\\ 
		$SDSOS_{4,n}$ & 0.0227  &  0.0949 & 0.4697 &1.4319 \\
		$DDTH_{4,n}$ & 0.0135 & 0.0307 &   0.1590 & 0.2960 \\
		$GDDTH_{4,n}$ &  0.0412  & 0.3476   &1.8041     &5.7232  \\
		\bottomrule
	\end{tabular}
	\caption{Comparison of solution time (in seconds) required to obtain the bounds on problem \eqref{prob:min_H_eigenvalue} using the restriction \eqref{pro:min_H_eigenvalue_K} for different choices of $\mathbb{K}$.}
	\label{tab:comparsion_3}
\end{table}




In this numerical test, we observe the following facts: The ranking in terms of strength of the bounds for these four methods is not altered by the size of the problems. In particular, $\lambda(\mathcal{A})^{SDSOS_{4,n}}$ gives the best bound while $\lambda(\mathcal{A})^{DDTH_{4,n}}$ gives the worst bound. 
Compared to $\lambda(\mathcal{A})^{GDDTH_{m,n}}$ (resp., $\lambda(\mathcal{A})^{DDTH_{m,n}}$), $\lambda(\mathcal{A})^{SDSOS_{4,n}}$ (resp., $\lambda(\mathcal{A})^{DSOS_{4,n}}$) provides a stronger bound. This concurs with the fact that the set of $DDTH_{m,n}$ (resp., $GDDTH_{m,n}$)  is contained in the set of $DSOS_{m,n}$ (resp., $SDSOS_{m,n}$). We will prove this result {for fourth order polynomials} in Proposition~\ref{theo:ddt_dsos_gddt_sdsos_4} in the Appendix.

From Table~\ref{tab:comparsion_3}, optimization over $DDTH_{4,n}$ is faster than optimization over $DSOS_{4,n}$.  Thus, there is a trade off between quality of the bounds and solution time when choosing between optimization over $DDTH_{4,n}$ and optimization over $DSOS_{4,n}$ to approximately solve polynomial optimization problems. One might expect that optimization over $GDDTH_{4,n}$ would be faster than optimization over $SDSOS_{4,n}$ so that there is a similar trade between strength of the bound and solution time as 
the one between optimization over $DDTH_{4,n}$ and optimization over $DSOS_{4,n}$. However, Table \ref{tab:comparsion_3} shows opposite result. The main reason for this is that efficient power cone optimization solvers are still underdeveloped in comparison with the highly developed second-order cone optimization solvers used to optimize over $SDSOS_{4,n}$.





\section{Conclusions}
\label{part:conclusion}


In this work, a new characterization of symmetric $H^+$-tensors is presented (see Corollary \eqref{col:fullGDDplus}). As a result of this characterization, it follows that one can decide whether a tensor is a symmetric $H^+$-tensor in polynomial time (see Theorem~\ref{th:check_gdd}). Comparing to other characterizations which typically focus on sufficient conditions for a tensor to be an $H^+$-tensor, our characterization provides sufficient and necessary conditions. Besides, the set of symmetric $H^+$-tensors is described using tractable convex cones; in particular, the power cone.

We apply the new characterization of symmetric $H^+$-tensors in computing the minimum $H$-eigenvalue of $M$-tensors. In particular, we show how these $H$-eigenvalues; which can be computed in polynomial time, compare with the best bounds for the minimum $H$-eigenvalues of $M$-tensors proposed in the related literature.
Furthermore, we illustrate how this new characterization of symmetric $H^+$-tensors can be used to obtain alternative solution approaches to approximately solve polynomial optimization problems (see Section \ref{part:application}). In particular, we compare and discuss the trade-offs between the use of $H^+$-tensor induced polynomials versus the use of $DSOS$ and $SDSOS$ polynomials to approximately solve the polynomial optimization problem associated with finding the minimum $H$-eigenvalue of an even order symmetric tensor.






\bibliographystyle{apalike}

