# Adaptive Clustering via Symmetric Nonnegative Matrix Factorization of the Similarity Matrix
## 2 The Alternating Nonnegative Least Squares for NMF
#### The Symmetric Case  
In our case, the similarity matrix \(A\in\mathbb{R}_{+}^{n\times n}\) is symmetric; hence, the general NMF problem (3) is replaced by the symmetric NMF (SymNMF) problem  
\[\min_{W\geq O}\,f(W),\text{ with }f(W)=\tfrac{1}{2}\,\|A-W\,W^{T}\|_{F}^{2}, \quad\text{with}\quad W\in\mathbb{R}_{+}^{n\times k}. \tag{6}\]  
Since \(A\) may generally be indefinite, while \(WW^{T}\) is positive semidefinite, \(WW^{T}\) represents a good factorization of \(A\) if \(A\) has enough nonnegative eigenvalues. When this happens, we are led to believe that \(W\) naturally captures the cluster structure hidden in \(A\)[1; 9]. Thanks to the nonnegativity, the largest entry in the \(i\)th row of \(W\) is assumed as the clustering assignment of the \(i\)th point--that is, \(\mathbf{p}_{i}\) belongs to the \(j\)th cluster if \(w_{ij}=\max_{r=1,\ldots,k}w_{ir}\). This interpretation furnishes a clustering \(\Pi\) induced by the matrix \(W\). In [9], this approach, which efficiently solves the clustering problem, is shown to be competitive with the widely used spectral clustering techniques, which perform a dimensionality reduction by means of the eigenvectors corresponding to the leading eigenvalues of \(A\). Problem (6) has a fourth-order nonconvex objective function. Following [1], we suggest solving it through a nonsymmetric penalty problem of the form  
\[\min_{W,H\geq O}\,f_{a}(W,H),\text{ with }f_{a}(W,H)=\tfrac{1}{2}\,\left(\|A- WH^{T}\|_{F}^{2}+\alpha\|W-H\|_{F}^{2}\right), \tag{7}\]  
\(\alpha\) being a positive parameter which acts on the violation of the symmetry. Problem (7) can be tackled by using any of the techniques proposed in the literature for solving the general NMF problem (3). For example, algorithm ANLS can be applied by alternating the solution of the two subproblems  
\[\left\{\begin{array}{l}H_{\
u}=\underset{H\geq 0}{\text{argmin}}\,\,\tfrac{1}{2} \,\left\|\,\left[ \begin{array}{c}A\\ \sqrt{\alpha_{\
u}}\end{array} \right]\,W_{\
u-1}^{T}\,\right]-\left[ \begin{array} []{c}W_{\
u-1}\\ \sqrt{\alpha_{\
u}}\end{array} \right]\,H^{T}\right\|_{F}^{2},\\ W_{\
u}=\underset{W\geq 0}{\text{argmin}}\,\,\tfrac{1}{2}\,\left\|\,\left[ \begin{array} []{c}A\\ \sqrt{\alpha_{\
u}}\end{array} \right]\,H_{\
u}^{T}\right]-\left[ \begin{array} []{c}H_{\
u}\\ \sqrt{\alpha_{\
u}}\end{array} \right]\,W^{T}\right\|_{F}^{2}. \tag{8}\]In [1], the sequence of penalizing parameters is constructed by setting  
\[\alpha_{v}=\beta_{v}\,\max A,\quad\text{with}\quad\beta_{0}=1,\]  
and \(\beta_{v}\) modified according to the geometric progression \(\beta_{v}=\zeta^{v}\) with the fixed ratio \(\zeta=1.01\). We suggest, instead, to let \(\beta_{v}\) be modified adaptively, as shown in [14]. Both problems (8) have a form similar to (5), with \(k\) rows involving the \(\sqrt{\alpha_{v}}\), appended at the bottom. Hence, each problem is solved by applying GGD with gradient  
\[G(X)=XY^{T}Y-B^{T}Y+\alpha(X-Y)=XQ-(B+\alpha I_{n})^{T}Y,\text{ where }Q=\alpha I_{k}+Y^{T}Y.\]  
The function which computes a single iteration of ANLS by applying GGD and modifying \(\alpha_{v}\) as described in [14], is thus called  
\[\big{(}W_{v},H_{v},\alpha_{v}\big{)}=\texttt{Sym\_ANLS}\big{(}A,W_{v-1},H_{v- 1},\alpha_{v-1}\big{)}.\]  
The whole iterative procedure is organized in the following function, Sym_IMF. The stopping condition tests the stabilization of the residuals \(\epsilon_{v}=\|A-W_{v}W_{v}^{T}\|_{F}^{2}\) by using two parameters: a tolerance \(\eta_{2}\) and a maximum number \(\
u_{\max}\) of allowed iterations (Section 6).