# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 5 Experimentation
### The Nonnegative Matrix Factorization  
The first test problem is the NMF problem (3) already outlined in Section 2, i.e., given \(M\in\mathbb{R}_{+}^{m\times n}\) and \(k<n\), we look for the _basis_ matrix \(W\in\mathbb{R}_{+}^{m\times k}\) and the _coefficient_ matrix \(H\in\mathbb{R}_{+}^{n\times k}\) which minimize \(f(W,H)=\left\|M-W\,H^{T}\right\|_{F}^{2}\) under the constrains \(W\), \(H\geq O\). ANLS is applied to \(f(W,H)\) with \(\mu=2\). An initial \(W_{0}\in\mathbb{R}_{+}^{m\times k}\) is chosen and the sequences  
\[\left\{ \begin{array}{l}H_{\
u}=\underset{H\geq 0}{\text{argmin}}\,\left\|M-W_{ -1}\,H^{T}\right\|_{F}^{2},\\ W_{\
u}=\underset{W\geq 0}{\text{argmin}}\,\left\|M^{T}-H_{\
u}\,W^{T} \right\|_{F}^{2},\end{array} \right. \tag{6}\]  
for \(\
u=1,2,\ldots\), are computed. Although the original problem (3) is nonconvex, subproblems (6) are convex and can be easily dealt with. In the experimentation we use for (6) the Greedy Coordinate Descent method (called GCD in [11]), which is specifically designed for solving nonnegative constrained least squares problems. The attribute \"Greedy\" refers to the selection policy of the elements updated during the iteration, based on the largest decrease of the objective function. In our tests this method has shown to be fast and reliable. The corresponding code can be found as Algorithm 1 in [11]. For the experimentation, given the integers \(m\), \(n\) and \(h\leq\min\{m,n\}\), two matrices \(A\in\mathbb{R}_{+}^{m\times h}\) and \(B\in\mathbb{R}^{n\times h}\) are generated with random elements uniformly distributed over \([0,1]\) and the matrix \(M=A\,B^{T}\) is constructed. The test problem (3) requires computing the NMF of \(M\), i.e., given an integer \(k\leq h\), two matrices \(W\in\mathbb{R}_{+}^{m\times k}\) and \(H\in\mathbb{R}_{+}^{n\times k}\) such that \(M\approx WH^{T}\) are to be found. The following cases are considered  
\[ \begin{array}{l}m=20,\ n=10,\ h=5,\text{with }k=3\text{ and }k=5,\\ m=40,\ n=30,\ h=10,\text{with }k=5\text{ and }k=10.\end{array} \]  
The dimension of the solution space is \(N=(m+n)\,k\). In the cases \(k=h\) we expect \(f^{*}=0\). The results are shown in Table 1.  
In the table we note that Class 1 methods, which use general purpose local optimizers, are more time consuming than Class 2 methods, as expected. Moreover, this gap increases with the dimension \(N\) \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \(m\times n\) (\(h\), \(k\)) & \(N\) & **Indices** & NM & DE & SA & MS1 & MS2 & AD1 & AD2 \\ \hline \multirow{3}{*}{\(20\times 10\) (5, 3)} & \multirow{3}{*}{90} & \(time\) & \(18\) & \(42\) & \(38\) & \(19\) & \(27\) & \(16\) & \(18\) \\  & & \(lerr\) & \(14.1\) & \(13.7\) & \(13.4\) & \(12.9\) & \(13.\) & \(12.9\) & \(13.0\) \\ \hline \multirow{3}{*}{\(20\times 10\) (5, 5)} & \multirow{3}{*}{150} & \(time\) & \(336\) & \(168\) & \(536\) & \(37\) & \(55\) & \(7\) & \(8\) \\  & & \(lerr\) & \(13.9\) & \(13.2\) & \(13.6\) & \(8.9\) & \(+\) & \(8.2\) & \(+\) \\ \hline \multirow{3}{*}{\(40\times 30\) (10, 5)} & \multirow{3}{*}{350} & \(time\) & \(617\) & \(696\) & \(783\) & \(200\) & \(323\) & \(135\) & \(148\) \\  & & \(lerr\) & \(12.1\) & \(12.4\) & \(12.5\) & \(6.6\) & \(10.8\) & \(6.6\) & \(10.8\) \\ \hline \multirow{3}{*}{\(40\times 30\) (10, 10)} & \multirow{3}{*}{700} & \(time\) & \(3158\) & \(5011\) & \(3929\) & \(606\) & \(917\) & \(183\) & \(255\) \\  & & \(lerr\) & \(13.2\) & \(11.5\) & \(12.2\) & \(8.6\) & \(12.4\) & \(8.6\) & \(12.0\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Execution times and accuracies for nonsymmetric Nonnegative Matrix Factorization (NMF) problems. Averagely, Class 1 methods are more accurate than Class 2 methods. Within the Class 2, each adaptive method is faster than the corresponding non adaptive one, as can be seen by comparing the times in column AD1 with those in column MS1 and the times in column AD2 with those in column MS2.