# Adaptive Clustering via Symmetric Nonnegative Matrix Factorization of the Similarity Matrix
## 1 Introduction  
Clustering can be applied to a variety of different kinds of documents as long as a distance measure can be assigned among the data objects. Generally, a similarity function assigns to pairs of closely related objects with a higher similarity than to objects which are only weakly related. A clustering technique classifies the data into groups, called clusters, in such a way that objects belonging to a same cluster are more similar to each other than to objects belonging to different clusters. In this paper we assume that the data objects are \(n\) distinct points \(\mathbf{p}_{1},\ldots,\mathbf{p}_{n}\) in \(\mathbb{R}^{d}\) and denote by \(k\), with \(1<k\ll n\), the number of clusters. As usual in this context, we consider the similarity expressed through the Gaussian kernel [1]  
\[e_{i,r}=\exp\big{(}-\frac{\|\mathbf{p}_{i}-\mathbf{p}_{r}\|_{2}^{2}}{\sigma\mu}\big{)},\quad\text{where}\quad\mu=\max_{j,s}\ \|\mathbf{p}_{j}-\mathbf{p}_{s}\|_{2}^{2}, \tag{1}\]  
and \(\sigma>0\) is a parameter based on the scale of the points. The nonnegative symmetric matrix \(A\in\mathbb{R}_{+}^{n\times n}\), whose elements are  
\[a_{i,r}=d_{i}^{-1/2}e_{i,r}d_{r}^{-1/2},\quad\text{where }d_{i}=\sum_{s=1}^{n}e_{i,s}, \quad\text{for}\quad i,r=1,\ldots,n, \tag{2}\]  
is called the _similarity matrix_. Among the many different techniques devised to solve the clustering problem, we chose a method which performs a dimensionality reduction through the _Nonnegative Matrix Factorization_ (NMF) of matrix \(A\). NMF finds an approximate factorization of \(A\) by means of two low-rank, nonnegative matrices. In its basic form, the problem is set as follows: given a matrixand an integer \(k\ll n\), we look for two low-rank matrices \(W\in\mathbb{R}_{+}^{m\times k}\) (the _basis_ matrix) and \(H\in\mathbb{R}_{+}^{n\times k}\) (the _coefficient_ matrix), such that the product \(WH^{T}\) approximates \(A\) according to  
\[\min_{W,\,H\geq O}\,f(W,H),\,\,\text{with}\,f(W,H)=\tfrac{1}{2}\,\left\|A-W\,H^ {T}\right\|_{F}^{2}, \tag{3}\]  
where the subscript F denotes the Frobenius norm. Actually, if the nonnegativity condition was not imposed, the minimum of \(f(W,H)\) could be obtained by truncating the Singular Value Decomposition \(A=U\Sigma V^{T}\). Unfortunately, some entries of \(U\) and \(V\) would be negative, and this would prevent interpretation of the factorization in terms of clustering [1]. In fact, since each column of \(A\) can be approximately represented by a linear combination with coefficients in \(H\) of columns of \(W\), thanks to the nonnegativity feature, the elements of \(H\), properly normalized, could be seen as the probabilities of assignment of the points to the different clusters. The clustering can be obtained by assigning the \(i\)th point \(\mathbf{p}_{i}\) to the \(j\)th cluster corresponding to the largest coefficient \(h_{i,j}\) in the \(i\)th row of \(H\). The problem of computing NMF was first proposed in [2] for data analysis and, from then on, it has received much attention. The first algorithm to compute NMF was proposed under the name of multiplicative updating rule in [3], but its slow convergence suggested looking for more efficient algorithms. Many of them belong to the class of Block Coordinate Descent (BCD) methods [4; 5; 6; 7; 8], but other iterative methods for nonlinear optimization have also been suggested, based on some gradient descent procedure. To improve the convergence rate, a quasi-Newton strategy has also been considered, coupled with nonnegativity (see, for example, the Newton-like algorithm of [9]). Open source libraries for computing NMF are available--see, for example, [10], where several methods proposed in related works are implemented. Over the years, many variants of the basic problem (3) have been considered. The case of a symmetric matrix \(A\) has been deeply investigated, but other features have also been taken into consideration.