# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 5 Experimentation
### The Nonnegative Factorization of a 3 rd-Order Tensor  
Let \(T\) be a 3 rd-order tensor, i.e., a three-dimensional array whose elements are \(t_{i,j,k}\), with \(i=1,\ldots,m,j=1,\ldots,n\) and \(k=1,\ldots,\ell\). A common way to represent graphically \(T\) is through its (frontal) slices \(T_{k}\), \(k=1,\ldots,\ell\), where \(T_{k}\) is the matrix obtained by fixing to \(k\) the third index. If \(T\) can be expressed as the outer product of three vectors \(\mathbf{u}\), \(\mathbf{v}\) and \(\mathbf{z}\), i.e., \(T=\mathbf{u}\circ\mathbf{v}\circ\mathbf{z}\), where \(\circ\) denotes the vector outer product, \(T\) is called _rank-one_ tensor or _triad_. Among the many factorizations of a tensor defined in the literature, we consider here the CANDECOMP/PARAFAC (in the following CP) decomposition (see [14]) into the sum of triads, which extends in a natural way the decomposition of matrices in sum of dyads. Given an integer \(\rho\), three matrices \(U\in\mathbb{R}^{m\times\rho}\), \(V\in\mathbb{R}^{n\times\rho}\) and \(Z\in\mathbb{R}^{\ell\times\rho}\) are computed such that  
\[T\approx\sum_{s=1}^{\rho}\mathbf{u}_{s}\circ\mathbf{v}_{s}\circ\mathbf{z}_{s}, \tag{8}\]  
where \(\mathbf{u}_{s}\), \(\mathbf{v}_{s}\) and \(\mathbf{z}_{s}\) are the \(s\)th columns of \(U\), \(V\) and \(Z\) (see [14; 15]). Elementwise, (8) is written as  
\[t_{i,j,k}\approx\sum_{s=1}^{\rho}u_{i,s}\,v_{j,s}\,z_{k,s},\quad\text{for}\quad i =1,\ldots,m,\ j=1,\ldots,n,\ k=1,\ldots,\ell.\] \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline _cluster_ & \(\mathbf{N}\) & **Indices** & NM & DE & SA & MS1 & MS2 & AD1 & AD2 \\ \hline \multirow{2}{*}{\(C_{1}\), \(n=10\)} & \multirow{2}{*}{100} & _time_ & 5 & 18 & 11 & 10 & 10 & 6 & 6 \\  & & _lerr_ & + & + & + & + & + & + & + \\ \hline \multirow{2}{*}{\(C_{1}\), \(n=50\)} & \multirow{2}{*}{500} & _time_ & 1232 & 1092 & 1363 & 15 & 14 & 12 & 13 \\  & & _err_ & 8.6 & 8.6 & 8.6 & + & + & + & + \\ \hline \multirow{2}{*}{\(C_{2}\), \(n=50\)} & \multirow{2}{*}{500} & _time_ & 991 & 1138 & 1085 & 12 & 12 & 11 & 11 \\  & & _lerr_ & 8.5 & 8.5 & 8.5 & + & + & + & + \\ \hline \multirow{2}{*}{\(C_{1}\), \(n=100\)} & \multirow{2}{*}{1000} & _time_ & 7541 & 8275 & 7749 & 108 & 107 & 83 & 87 \\  & & _lerr_ & 8.2 & 8.3 & 8.2 & + & + & + & + \\ \hline \multirow{2}{*}{\(C_{2}\), \(n=100\)} & \multirow{2}{*}{1000} & _time_ & 5577 & 5645 & 6184 & 84 & 94 & 81 & 82 \\  & & _lerr_ & 8.6 & 8.6 & 8.6 & 14.8 & 14.8 & 14.8 & 14.8 \\ \hline \multirow{2}{*}{\(C_{2}\), \(n=200\)} & \multirow{2}{*}{2000} & _time_ & 28,003 & 36,256 & 37,424 & 356 & 421 & 137 & 164 \\  & & _lerr_ & 9.2 & 9.8 & 9.8 & 9.0 & + & 9.0 & + \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Execution times and accuracies for symmetric Nonnegative Matrix Factorization (NMF) problems. Figure 2: (a) Set \(C_{1}\) and (b) Set \(C_{2}\) with \(n=50\) points. The objective function of the CP decomposition of \(T\) is  
\[f(U,V,Z)=\|T-\sum_{s=1}^{\rho}\mathbf{u}_{s}\circ\mathbf{v}_{s}\circ z_{s}\|_{F}^{2}=\sum _{i=1}^{m}\sum_{j=1}^{n}\sum_{k=1}^{\ell}\Big{(}t_{i,j,k}-\sum_{s=1}^{\rho}u_{i,s}\,v_{j,s}\,z_{k,s}\Big{)}^{2}. \tag{9}\]  
The smallest integer \(\rho\) for which (8) holds with equality, i.e., \(\min f(U,V,Z)=0\), is the _tensor rank_ of \(T\). By flattening its slices, the elements of \(T\) can be arranged into a matrix. For example, one can leave the \(i\)th index and linearize the two other indices, obtaining a matrix which is denoted by \(T^{(i)}\). Thus, \(T^{(1)}\in\mathbb{R}^{m\times n\ell}\), \(T^{(2)}\in\mathbb{R}^{n\times m\ell}\) and \(T^{(3)}\in\mathbb{R}^{\ell\times m\,n}\) are the matrices whose elements are  
\[t^{(1)}_{i,n(k-1)+j}=t^{(2)}_{j,m(k-1)+i}=t^{(3)}_{k,m(j-1)+i}=t_{i,j,k}.\]  
These matrices are written in a compact way by using the notation of the Khatri-Rao product, defined as follows.