Data representation using robust nonnegative matrix factorization for edge computing

1.   Introduction

With the development of automatic driving technology, edge computing (EC) has attracted more and more attention. Compared with cloud computing that exploits distributed computing to decomposing many data processing tasks through the network, EC is initiated at the edge of the data source, and thus reduces the process of data transfer on the network. To recognize a face image, for example, cloud computing will upload this image to the server first, and then the cloud server will complete such a task. EC directly calculates the recognition result after obtaining the image. Obviously, it requires a variety of techniques to complete different tasks. Generally, the data EC processes usually has high-dimensional and complex structure ^[1]. Furthermore, in multimedia mining, pattern recognition and bio-informatics ^[2,3,4], one is often faced with high-dimensional data. Directly dealing with such high-dimensional data requires massive time and memory cost for learning tasks. In fact, the features of data are not all discriminative and important, since many of them are redundant or noisy ^[4,5,6]. Important and meaningful features always lie on (or near) a low-dimensional space ^[7,8]. This leads one to investigate a new technique to process these data. Dimensionality reduction (DR) is to find a low-dimensional representation of high-dimensional data by preserving the inherent desired structure contained in the original data ^[9,10,11]. It has been proved to be an effective method to decrease the dimensionality of data ^{[12,13,14,15,16,17,18]}. Existing popular representative methods for DR are Linear Discriminant Analysis (LDA) ^[19,20], Principal Component Analysis (PCA) ^[10], Locality Preserving Projections (LPP) ^[21], LLE ^[12], ISOMAP ^[13] and Laplacian Eigenmap ^[22], and so on. The basis vectors and coefficients obtained by these approaches above are not constrained the non-negativity and thus usually contain negative values. Data in real applications like texts, images, audios and videos, are naturally nonnegative. Basis vectors and coefficients with negative values lack of clear physical meaning and interpretability for nonnegative data ^[23].

As a new DR algorithm, Nonnegative Matrix Factorization (NMF) has recently been presented to solve the nonnegative data. NMF is to decompose a given nonnegative matrix into two nonnegative factor matrices, so that the product of the two factor matrices can well approximate the given one ^[24]. It constrains the two factors to be nonnegative. That is, all elements of two factor matrices must be greater than or equal to zero. NMF is a parts-based DR method since it only allows the addition combination of the original data space, not the subtraction combination ^[25]. It has successfully been used in many fields, such as face recognition ^[24,26], document clustering ^[27,28], image processing ^[29,30,31], and molecular pattern discovery ^[32,33]. Therefore, many improved NMF-based algorithms have been put forward. Ding et al. ^[34] presented Convex-NMF and Semi-NMF to increase its applicable range by relaxing the data matrix to hold positive and negative numbers, respectively. A graph regularized NMF (GNMF) ^[35] is put forward to promote discriminating ability of the ordinary NMF by defining an affinity graph to encode the geometrical data structure. Li et al. ^[36] incorporated distant repulsion and basis redundancy elimination into the cost function of GNMF and thus developed a structure preserving NMF approach. Zhang et al. ^[37] proposed manifold regularized low-rank matrix decomposition by extending GNMF to the nonlinear space. A structure constraint NMF ^[38] is developed to apply the intra-sample structures to promote the matrix decomposition process. Cichocki et al. ^[39] proposed a general framework for NMF based on Csizar's divergences, which improved the efficiency and robustness of NMF. Cichocki et al. ^[40] exploited orthogonality and sparsity constraints to extend NMF. Fevotte et al. ^[41] proposed a novel NMF based on the β-divergence cost function (β-NMF). Devarajan et al. ^[42] presented a unified method for NMF based on the generalized linear model theory. Devarajan et al. ^[43] used generalized dual Kullback-Leibler divergence to improve NMF and thus proposed a statistical NMF framework.

Above approaches are unsupervised and ignore supervised information, including class label and pairwise constraint. Actually, supervised information is used to promote the performance of learning methods ^[8,15,16,18]. Usually, class labels for all data are fairly expensive to obtain but limited supervised information is readily available, therefore semi-supervised NMF with a small amount of supervised information has attracted considerable attention ^[44,45,46]. Constrained NMF method (CNMF) ^[31] is a representative work of semi-supervised ones. It combined class labels of data as additional constraints to improves the discriminating power. Robust structured NMF algorithm (RSNMF) ^[8] applied class label to encode the block-diagonal structure, which embeds instances from the same class to the same space. constraint propagation-based semi-supervised NMF algorithm (CPSNMF) ^[23] propagates pairwise constraints on the entire data set in the form of cannot-link and must-link, which constructs a weight graph as the regularization to constrain the factorial matrix of NMF. Zhang et al. ^[47] used pairwise constraints to guide NMF clustering and thus proposed an NMF-based constrained clustering method. Yang et al. ^[48] developed an adaptive non-smooth NMF approach which applying using a data-related algorithm to adaptively obtain the smoothness matrix. Label propagation based semi-supervised NMF ^[49] is developed to integrate class label propagation and matrix decomposition into a joint model by exploring the distribution relationship between labeled and unlabeled data instances. By employing the relationship between label information and feature representation, adaptive graph semi-supervised NMF ^[50] enhanced the recognition ability of feature representation and completes the classification task. Li et al. ^[51] integrated deep learning, matrix factorization, and view fusion into a matrix framework and thus proposed a novel adaptive-weighted multi-view method. Jia et al. ^[52] extended the conventional NMF by exploiting the similarity and dissimilarity regularizers to steer matrix factorization. Xing et al. ^[53] added the label information of some data to the objective of NMF as the regularization term.

Although NMF and its variants have strong mathematical theory and encouraging performance, there are still three important problems to be further addressed. First, above-mentioned approaches fail to use global and local structures of the data to enhance the decomposition ability of NMF simultaneously, which limits their application to real-world scenes. Local and global structures are applied to find a discriminative and compact representation ^[15,54]. CNMF and RSNMF ignored the local geometrical structure of data when they expanded NMF to semi-supervised scenario. Generally, the local geometric structure of data is are supposed to be locally invariant in data set. That is, nearest neighbor samples should have the same class label ^[33,55]. Both GNMF and RMNMF ^[45] only pay close attention to the local structure and ignore the global structure, thus losing discriminating power. Second, most semi-supervised NMF methods neglect the important role of instances from different classes in learning the representation of data. Like instances with the same class label, instances with different class labels can also provide discriminative information. In fact, it makes the result more intuitive and interpretable that instances involved in the same class are mapped closer, while those involved in different classes are mapped farther in the new representation space. Third, above-mentioned approaches become unstable and have disappointed performances when processed data contain noise and outliers. Because the residual of every instance gets into the loss function of NMF in the form of square, it is easy to generate outliers ^[56,57]. Kong et al. ^[58] put forward robust NMF to get around this problem, which applies the L_{2, 1}-norm cost function to achieve nonnegative matrix decomposition. Generally, real data in many applications are contaminated by noise and outliers. Therefore, it is necessary and important to investigate a novel algorithm to improve the robustness of NMF.

To address the above problems, we put forward a novel NMF algorithm for data representation, called robust constrained nonnegative matrix factorization (RCNMF), which discover the intrinsic geometric and discriminating structure of data in semi-supervised scenario. In the proposed RCNMF model, pairwise constraints are propagated to unlabeled instances for encoding global and local structures. Then, we construct a specific intrinsic graph to depict the between-cluster separability and the within-cluster compactness in the latent representation space. Additionally, we introduce the L2, 1-norm cost function to enhance the robustness of the new model. Hence, RCNMF can be naturally applied to practical learning tasks. The main contributions of the proposed algorithm are worth highlighting here:

1) Our algorithm explicitly exploits global and local structures of the original data space via constraint propagation and merges it into our model to guide matrix decomposition. The proposed RCNMF approach makes latent representations of instances involved by the same class closer and those of instances involved by different classes farther. Thus, the proposed RCNMF has more discriminating ability than other semi-supervised ones.

2) Different from CNMF, NMFCC and CPSNMF which are not robust to outliers and noise, the new model can address the problem of noise and outliers since RCNMF exploit the L_{2, 1}-norm loss to achieve the nonnegative matrix decomposition. Moreover, the new model imposes the L_{2, 1}-norm on the coding matrix to ensure the new representation sparse in rows.

3) The proposed RCNMF can take advantage of the ability of L_{2, 1}-norm NMF and constraint propagation, and characterize it as an optimization problem. The new model explores an efficient iterative algorithm to solve such an optimization problem with the theoretical analyses and the experimental verification. In addition, it is easy to observe that several algorithms, such as RNMF and CPSNMF, are special cases of the proposed algorithm. Thus, our method is a general framework.

4) Our method propagates cannot-link and must-link constraints to unlabeled samples, thus can get more supervised information. Moreover, the new model can adapt to class label and pairwise constraint scenarios. This naturally leads to various applications.

The rest of this paper is structured as follows. We briefly review related work in Section 2. We elaborate the proposed RCNMF model and the corresponding optimization in Section 3. We provide convergence proof and computational complexity of RCNMF in Section 4. Extensive experiments on clustering are reported in Section 5. Finally, we give some conclusions in Section 6.

2.   Related work

Given an original nonnegative data matrix $X = [{x}_{1}, ..., {x}_{N}]\in {\mathbb{R}}^{M\times N}$ with N instances, ${x}_{i}\in {\mathbb{R}}^{M}$ is an instance vector. NMF is to find two nonnegative matrix factors $U = \left[{u}_{ik}\right] \in {\mathbb{R}}^{M\times K}$ and $V = \left[{v}_{jk}\right] \in {\mathbb{R}}^{N\times K}$ so that

NMF makes use of the square of the Euclidean distance to solve the optimal approximation U and V, respectively. The Euclidean square distance of NMF is defined as ^[24,59]:

where ${\left\| \cdot \right\|}_{F}$ is the Frobenius norm of the matrix.

The problem (2) is not convex for optimizing two factors U and V simultaneously, but is convex when one variable is fixed and the other is solved. Thus, Lee and Seung ^[24] presented two iterative update rules to optimize the problem (2), which is formulated as:

2.1.   Manifold nonnegative matrix factorization (MNMF)

Cai et al. proposed the graph regularized NMF (GNMF) to GNMF ^[35] explicitly takes into account the local invariance of data and sets up the nearest neighbor graph to formulate the geometrical structure of the original data space. It depicts this graph structure as the Laplacian matrix, which is added to the loss function of NMF as the regularization term. Thus, GNMF optimizes the following problem:

where $\lambda \ge 0$ is a regularization parameter and $Tr(·)$ denotes the matrix trace. L = D – W is a Laplacian matrix of the neighbor graph. W denotes a connection weight matrix of the nearby instances and D denotes a diagonal matrix whose entries ${d}_{ii} = {\sum }_{j}{w}_{ij}$. Two alternate rules are exploited to iteratively solve the optimal model (5). The updating formulas are respectively described as followed:

Zhang et al. ^[37] expended GNMF to the nonlinear space for characterizing the nonlinear structure of the data, which is stated as followed:

where Φ can be a Laplacian matrix, e.g., formulated as the weight matrix I – W in the LLE ^[12].

Huang et al. ^[56] integrated GNMF and L_{2, 1}-NMF ^[47] into a joint framework and proposed a robust manifold NMF method (RMNMF). Wu et al. ^[59] also presented a robust manifold NMF algorithm similar to RMNMF. The objective function in ^[59] increases the constraint U $\geqslant 0$ and reduces the orthogonal constraint in comparison to RMNMF. We call the above four methods as Manifold Nonnegative Matrix Factorization (MNMF), since they also construct the nearest neighbor graph to depict the local information of the input space.

2.2.   NMF-based constrained clustering (NMFCC)

Zhang et al. ^[47] put forward an NMF-based constrained clustering method, called NMFCC. NMFCC enforces the similarity between two instances belonging to a must-link constraint to approach one and that of two instances belonging to a cannot-link constraint to approach zero, which is composed of a similarity matrix. It uses the square of the class indicator matrix to compute the similarity matrix and regards as a regularization term to cluster. NMFCC minimizes the following problem:

where $\circ$ refers to the dot product between two matrixes and $Q$ denotes the constraint matrix whose entry is 1 if $(i, j)\in ML$ (must-link set) or $i = j$ else 0. A is a coefficient matrix defined as

After the Lagrange function for Eq (10) is constructed and used to solve the derivatives with respect to U and V, NMFCC get the update rules of Eqs (11) and (12):

where

2.3.   Constrained nonnegative matrix factorization (CNMF)

Liu et al. ^[31] put forward a new semi-supervised NMF method, called CNMF. Different from the above-mentioned methods in this section, CNMF treats a small amount of class label as hard constraints to ensure that instances with the same label are embedded into the same low-dimensional space. Given l labeled instances and n-l unlabeled instances, CNMF first constructs the indicator matrix C where ${c}_{ij} = 1$ if ${x}_{i}$ belongs to class j; ${c}_{ij} = 0$ otherwise. The matrix A of label constraints is formulated as

CNMF introduces an auxiliary matrix Z to incorporate label constraint information and redefines a coefficient matrix V as V = AZ. Hence, CNMF solves the following problem:

The solutions of CNMF are expressed as:

2.4.   Discriminative nonnegative matrix factorization (DNMF)

Babaee et al. ^[60] presented a label constrained NMF method, called Discriminative Nonnegative Matrix Factorization (DNMF). Similar to CNMF, DNMF first constructs the indicator matrix $Q\in {\mathbb{R}}^{S\times N}$ where ${q}_{ij} = 1$ if ${x}_{i}$ belongs to class j; ${q}_{ij} = 0$ otherwise. Different from CNMF, unlabeled instances are assigned 0 in Q. Then, DNMF defines the label information constraint as:

where ${V}_{l} = {[{v}_{1}, ..., {v}_{c}, 0, ..., 0]}^{T}\in {\mathbb{R}}^{N\times K}$ and the matrix A which is calculated as part of the NMF optimization. Therefore, the formulation of DNMF is as follows:

DNMF uses the following iterative update rules and obtains the corresponding U, V, and A:

2.5.   Robust structured nonnegative matrix factorization (RSNMF)

A semi-supervised robust structured NMF algorithm (RSNMF) ^[8] is proposed to arrive at the separated low-dimensional space. The key idea of RSNMF is to use the block-diagonal structure of the labeled instances to increase the discriminating ability. Specifically, RSNMF introduces an indicator matrix $I = [\stackrel{-}{I}, \widehat{0}] \in {\mathbb{R}}^{r\times n}$, where $\widehat{0}\in {\mathbb{R}}^{r\times u}$ is a zero matrix for the unlabeled instances. Given labeled instances, the definition of $\stackrel{-}{I}\in {\mathbb{R}}^{r\times l}$ is expressed as follows:

in which ${\stackrel{-}{0}}_{c}\in {\mathbb{R}}^{m\times {n}_{c}}$ is the zero-matrix corresponding to c-th class. RSNMF describes the block-diagonal structure as ${\left\|I\odot V\right\|}_{F}^{2}$, where $\odot$ is the elementwise multiplication operator. RSNMF defines the following loss function:

Thus, RSNMF designs the following updating rules for these two matrix factors:

where ${d}_{kk} = p/2{\left\|{z}_{k}\right\|}_{2}^{2-p}$ and $Z = X-U{V}^{T}$.

3.   Robust constrained NMF

As mentioned above, NMF and its variants are unsupervised algorithms, and fail to exploit some supervised information to guide the decomposition progress and to improve the discriminating ability. In fact, utilizing a small amount of supervised information has always been an important issue in many fields of computer vision and machine learning ^[15,16,18]. Generally, supervised information has various forms. The two commonly used forms are pairwise constraint and class label, respectively. In this paper, we exploit cannot-link and must-link constraints to conduct matrix decomposition. A must-link constraint specifies that two instances have the same cluster label. A cannot-link constraint indicates that two instances have different cluster labels. In many applications, it is more practical to get pairwise constraints than to get class labels, because users can easily demonstrate whether two samples belong to the same cluster ^[16,31]. Besides, one can use the class label of the sample to obtain pairwise constraint, but not vice versa. Consequently, pairwise constraints are weaker supervised information than class label.

Inspired by recent research on NMF and semi-supervise learning ^[23,61], in this paper, we propose a novel robust constrained nonnegative matrix factorization (RCNMF), which explicitly combines constraint propagation and L2, 1-norm NMF in a new way. We use cannot-link and must-link constraints to propagate over the whole data set, thus obtain the constraint information as a regularizer added to the L2, 1-norm NMF. Next, we describe the RCNMF model in detail.

3.1.   L_{2, 1} norm NMF

For any matrix A, its j-th column, i-th row are denoted by a_j and aⁱ, respectively. Tr (B) means the trace of B if B is square. A^T is the transposed matrix of A. I denotes an identity matrix and 1 is a column vector whose entries are all 1. We define the L_{2, 1} norm of the matrix B as ^[62]:

One can use NMF and the L_{2, 1} norm to group the data matrix X into k clusters (${C}_{1}, ...{C}_{k}$) as:

where U denotes the basis matrix and V is the encoding matrix. Because of the constraints on V, the optimization problem (25) is difficult to solve. A commonly used method is to relax this constraint to orthogonality, i.e., V^TV = I. Thus, the problem (25) is rewritten as:

3.2.   Constraint propagation

For the data set $X = [{x}_{1}, ..., {x}_{N}] \in {\mathbb{R}}^{M\times N}$, we describe initial must-link constraints as $ML = \left\{\right({x}_{i}, {x}_{j}\left)\left|{l}_{i} = {l}_{j}\right.\right\}$ and initial cannot-link constraints as $CL = \left\{\right({x}_{i}, {x}_{j}\left)\left|{l}_{i}\ne {l}_{j}\right.\right\}$, where ${l}_{i}$ denote the clustering label of the instance ${x}_{i}$. To propagate both cannot-link and must-link constraints on the whole data set, Lu et al. ^[61] used "+1" and "-1" to represent the difference between the two types of constraints. The propagation operation aims to determine the constraint weight between two unconstrained instances, which essentially clusters instances between classes marked with +1 or classes marked with -1. Thus, the initial pairwise constraint matrix $Z = \left[{z}_{ij}\right]\in {\mathbb{R}}^{N\times N}$ is denoted as:

The matrix of propagated pairwise constraints is defined as $F = \left[{f}_{ij}\right]\in {\mathbb{R}}^{N\times N}$, where $\left|{f}_{ij}\right|\le 1$. The matrix F represents a set of pairwise constraints with relevant clustering weight. ${f}_{ij}\ge 0$ means $({x}_{i}, {x}_{j})\in ML$, while ${f}_{ij}\le 0$ means $({x}_{i}, {x}_{j})\in CL$. Constraint propagation in ^[61] is formulated as:

The specific algorithm of constraint propagation is formulated as:

1) Set up a nearest neighbor graph vis denoting its nearby weight $W\in {\mathbb{R}}^{n\times n}$ as:

if ${x}_{i}\in {N}_{p}\left({x}_{j}\right)$ or ${x}_{j}\in {N}_{p}\left({x}_{i}\right)$ and ${w}_{ij} = 0$, otherwise, where $a({x}_{i}, {x}_{j}) = \mathrm{e}\mathrm{x}\mathrm{p}(-{\left\|{x}_{i}-{x}_{j}\right\|}^{2}/\sigma)$ and ${N}_{p}\left({x}_{i}\right)$ denotes the set of p nearest neighbors of ${x}_{i}$.

2) Compute the matrix $L = {D}^{-1/2}W{D}^{-1/2}$, where D is a diagonal matrix whose i-th diagonal entry is ${\sum }_{j}{w}_{ij}$.

3) Compute the vertical constraint matrix ${F}_{v}(t+1) = \eta L{F}_{v}\left(t\right)+(1-\eta)Z$ until convergence, in which $\text{α}\text{}$ is limited to (0, 1).

4) Iterate the horizontal constraint matrix ${F}_{h}(t+1) = \eta {F}_{h}\left(t\right)L+(1-\eta){F}_{v}^{*}$ until convergence¹, in which ${F}_{v}^{*}$ denotes the limit of $\left\{{F}_{v}\right(t\left)\right\}$.

¹ Please refer to ^[61] for the proof of the convergence.

5) ${F}^{*} = {F}_{h}^{*}$ is the final representation of $F$, where ${F}_{h}^{*}$ denotes the limit of $\left\{{F}_{h}\right(t\left)\right\}$.

6) Compute the new weight matrix $\stackrel{-}{W} = \left[{\stackrel{-}{w}}_{ij}\right] \in {\mathbb{R}}^{n\times n}$ by utilizing ${F}^{*}$ and the original normalized weight matrix W:

According to the above analysis, the learned weight matrix has several distinct advantages:

1) The matrix $\stackrel{-}{W}$ is symmetric and nonnegative, and ${\stackrel{-}{w}}_{ij}\in \left[\mathrm{0, 1}\right]$. Thus, it can well describe the relationship between instances.

2) ${\stackrel{-}{w}}_{ij}\ge {w}_{ij}$ (or $< {w}_{ij}$) if ${f}_{ij}^{*}\ge 0$ ($< 0$). This shows that $\stackrel{-}{W}$ is derived from W. It is increased when ${f}_{ij}^{*}\ge 0$, and decreased when ${f}_{ij}^{*} < 0$.

3) $\frac{\partial {\stackrel{-}{w}}_{ij}}{\partial {w}_{ij}} = 1-\left|{f}_{ij}^{*}\right|$. This indicates that cannot-link and must-link constraints an equally significant role in computing the relationship between instances.

By using the constraint propagation approach, local and global structures is taken into account so that more pairwise constraint is obtained. Clearly, the propagated pairwise constraint matrix $\stackrel{-}{W}$ characterizes that nearby instance have the same clustering label, and instances with the same structure have the same clustering label. Then, one can use pairwise constraint information to build a new weight matrix in which instances involved by the same class have larger weight values and those involved by different classes have smaller weight values.

3.3.   Robust constrained nonnegative matrix factorization

We apply constraint propagation to guide the matrix decomposition process in the L_{2, 1}-norm NMF. For dimensionality reduction or classification, there are two kinds of consistency. One is that latent representations are considered locally consistent. That is, nearby representations are supposed to have the same label. Specifically, if the two representations ${v}_{i}$ and ${v}_{j}$ are close to each other, they belong to the same class. A k-nearest neighbor graph is constructed to figure the similarity between nearby instances. The other is that latent representations should be globally consistent, i.e., instances with the same structure have the same label. We introduce constraint propagation to find an appropriate propagated pairwise constraint matrix F for meeting the two properties. In summary, we construct a new weight graph to model the relationship between latent representations with the weight matrix $\stackrel{-}{W}$ :

If the two instances ${x}_{i}$ and ${x}_{j}$ have the same label, they should be close to each other in the input data space. ${f}_{ij}^{*}$ has a large positive value so that ${\stackrel{-}{w}}_{ij}$ also has a relatively large value in the light of Eq (29). Minimizing $J\left(V\right)$, the distance between the latent representations ${v}_{i}$ and ${v}_{j}$ should be small. Thus, ${v}_{i}$ and ${v}_{j}$ are neighbor in the low-dimensional space. On the other hand, if the two instances ${x}_{i}$ and ${x}_{j}$ belong to different classes, they should be kept away in the original data space. ${f}_{ij}^{*}$ has a large negative value and thus ${\stackrel{-}{w}}_{ij}$ has a relatively small value, which indicates that ${v}_{i}$ and ${v}_{j}$ are far from each other. Therefore, minimization Eq (30) makes the distance between data points belonging to must-link constraint as small as possible and the distance between data points belonging to must-link constraint as large as possible. Besides, the problem (30) has the same formulation as spectral dimensionality reduction ^[21,22], which plays a significant role in semi-supervised manifold learning algorithms and spectral clustering.

Combining Eqs (25) and (30), we propose a general NMF framework, called robust constrained nonnegative matrix factorization (RCNMF). RCNMF optimizes the following problem:

where α and β are two trade-off parameters. We use the L_{2, 1} norm on the basis matrix U as the regularization term to select the latent representation, since U is sparse and easy to be controlled by noise features.

3.4.   Optimization algorithm

Like other NMF-based methods, the objective function in the model (31) is not convex for optimizing two factors and simultaneously, but is convex when one variable is fixed and the other is solved. To this end, we introduce an iterative optimization to solve optimizing these two factors. We rewrite the objective function of RCNMF as follows:

where $\stackrel{-}{D}$ is a diagonal matrix with ${\stackrel{-}{d}}_{ii} = {\sum }_{j}{\stackrel{-}{w}}_{ij}$, and $\stackrel{-}{L} = \stackrel{-}{D}-\stackrel{-}{W}$. ${\psi }_{ik}$ and ${\phi }_{jk}$ are used as the Lagrangian multiplier of two matrix factors U and V, respectively, where $\mathit{\Psi} = \left[{\mathit{\psi} }_{ik}\right]$ and $\mathit{\Phi} = \left[{\mathit{\phi} }_{jk}\right]$. $\lambda > 0$ is a parameter to adjust the weight of the orthogonality condition. The corresponding Lagrange function $\mathcal{L}$ is written as

By using ${\left\|A\right\|}_{F}^{2} = Tr\left(A{A}^{T}\right)$, the partial derivative of $\mathcal{L}$ with respect to U and V is calculated as

where E and H are diagonal matrices and their diagonal elements are given by

Applying the Karush-Kuhn-Tucker (KKT) conditions ${\phi }_{ik}{u}_{ik} = 0$ and ${\phi }_{jk}{v}_{jk} = 0$, we obtain two equations for ${u}_{ik}$ and ${v}_{jk}$ as follows:

Thus, we get the following updating rules from Eqs (38) and (39):

Based on the above analysis, we can update U and V iteratively with Eqs (40) and (41) until the objective value of Eq (31) remains unchanged. The detailed optimization algorithm is described in Algorithm 1.

We can combine the KL divergence cost function with structure learning and the regularizer of the two factors. A novel KL divergence cost function is defined as

where $Z = \left[{z}_{ij}\right] = {V}^{T}V$.

Assuming that ${\psi }_{ik}$ and ${\phi }_{jk}$ are the Lagrange multipliers for ${u}_{ik} > 0$ and ${v}_{jk} > 0$, we can define the following Lagrange functions:

The partial derivatives of Eq (43) with respect to ${u}_{ik}$ and ${v}_{jk}$ are

If two instances ${x}_{i}$ and ${x}_{j}$ are adjacent, their corresponding low-dimensional representations ${v}_{i}$ and ${v}_{j}$ are close to each other. Thus, ${v}_{ik}/{v}_{jk}$ is close to 1. We adopt the following approximation:

With Eq (46), we can rewrite Eq (45) as

Since $\stackrel{-}{L} = \stackrel{-}{D}-\stackrel{-}{W}$, we can easily verify that ${\sum }_{i}({v}_{jk}-{v}_{ik}){\stackrel{-}{w}}_{ij}$ is equal to the j-th element of vector $\stackrel{-}{L}{V}_{k}$. Eq (47) is formulated as

We can obtain the following equations for ${u}_{ik}$ and ${v}_{jk}$ by adopting the KKT conditions ${\psi }_{ik}{u}_{ik} = 0$ and ${\phi }_{jk}{v}_{jk} = 0$ :

Two updating rules can be obtained:

We call the proposed algorithm based on the KL divergence cost function as RCNMF-KL.

4.   Convergence and analysis

4.1.   Proof of convergence

To get the optimal solution, we theoretically analyze the convergence of the proposed RCNMF. Similar to other NMF-based methods, we afford the convergence proof of the monotone property of the new model (31) under the alternate update rules of Eqs (40) and (41).

Theorem 1. The cost function $\mathcal{O}$ of Eq (31) is non-increasing under the alternate updating rules of Eqs (40) and (41).

To prove Theorem 1, we give a lemma about the auxiliary function.

Lemma 1. If $G\left(x, {x}^{\text{'}}\right)$ is an auxiliary function for $F\left(x\right)$ and meets the conditions $G(x, {x}^{\text{'}})\ge F\left(x\right)$ and $\text{G}(x, x) = F\left(x\right)$, then $F\left(x\right)$ is non-increasing under the following update:

Proof.

We first demonstrate that the cost function $\mathcal{O}$ of Eq (31) is decreasing under the update rule Eq (41) while fixing U with an appropriate auxiliary function. The cost function of RCNMF in Eq (31) can be rewritten

where ${e}_{ii} = 1/{\left\|{x}_{i}-U{\left({V}^{T}\right)}_{i}\right\|}_{2}$ and ${h}_{ii} = 1/{\left\|{u}_{i}\right\|}_{2}$.

With the help of (54), the auxiliary function regarding V is described as the following Lemma 2.

Lemma 2. Function

is an auxiliary function for $F\left(V\right)$ which

Proof. Clearly, $G(V, V) = F\left(V\right)$. We need to prove $G(V, {V}^{\text{'}})\ge F\left(V\right)$ in the light of the definition of the auxiliary function. With Eqs (55) and (56), we find that $G(V, {V}^{\text{'}})\ge F\left(V\right)$ is equivalent to

We exploit the following matrix inequality from the Lemma in ^[34]

where $A\in {\mathbb{R}}_{+}^{N\times N}$, $B\in {\mathbb{R}}_{+}^{K\times K}$, $S\in {\mathbb{R}}_{+}^{N\times K}$, $S\text{'}\in {\mathbb{R}}_{+}^{N\times K}$, and $A = {A}^{T}$, $\text{B} = {B}^{T}$. Ding et al. ^[34] proved that Eq (58) holds. The equality holds when $S = {S}^{\text{'}}$.

Setting $A = E$, $B = {U}^{T}U$, $S = V$, ${S}^{\text{'}} = {V}^{\text{'}}$ in Eq (58), then Eq (57) holds and $G(V, {V}^{\text{'}})\ge F\left(V\right)$. Clearly, $G\left(V, {V}^{\text{'}}\right)$ in Eq (55) is an auxiliary function for $F\left(V\right)$ in Eq (56). Thus, we have

This competes the proof of Lemma 2.

Next, we prove that the cost function $\mathcal{O}$ of (31) is decreasing under the updating rule (40) while fixing V. For the convenience of description, we use ${U}_{t}$ to represent the solution of t-th iteration.

Lemma 3. Let ${U}_{t+1}$ be the (t+1)-th value of U (on the left-hand-size of (40)) and ${U}_{t}$ be the t-th value of U (on the right-hand-size of (40)). With the updating rule (40), inequality (60) holds

where ${e}_{ii} = 1/{\left\|{x}^{i}-{u}^{i}{V}^{T}\right\|}_{2}$ and ${h}_{ii} = 1/{\left\|{u}^{i}\right\|}_{2}$.

Proof. It is easy to verify that Eq (40) is the solution to the following model:

Thus, in the t-th iteration, when V is fixed, we get

which is equivalent to

That is to say,

According to the Lemmas in ^[6], $\sqrt{a}-\frac{a}{2\sqrt{b}}\le \sqrt{b}-\frac{b}{2\sqrt{b}}$, we arrive at

and

Combining Eqs (62) to (64), we obtain

This completes the proof of Lemma 3. Thus, we arrive at

Based on Eqs (59) and (68), Theorem 1 is proved. Thus, we can obtain that the cost function in Eq (31) is non-increasing via exploiting the update rules of Eqs (40) and (41).

4.2.   Complexity analysis

In this section, the computational complexity of the proposed method will be analyzed. Generally, a capital symbol O is used to formulate the complexity of one approach.

According to the update rules of Eqs (40) and (41), the complexities to compute U and V are O (MNK+MK) and O (MNK+NK), respectively. If the proposed algorithm converges after t operations, the total computational complexity of calculating U and V is O (tNMK). After t iterations, the computational costs of E and H are O (t(NM+N)) and O (t(MK+N)) respectively, since they are diagonal matrices. Besides, the RCNMF method also costs O (MN²) to construct the k-nearest neighbor graph and O (pN²) to propagate constraints. Thus, the total computational complexity of the RCNMF method is O (tMNK + t (NM+N) + t (MK+M) + (M + p) N²).

5.   Experiments

In this section, we present the experimental results and analysis of the proposed RCNMF. Following ^[8,23,31,35], we verify the performance of our new method on the basis of clustering.

5.1.   Experimental setting

In our experiments, we apply six publicly available data sets to compare the performance of the RCNMF and other state-of-the-art methods. These data sets are derived from different application scenarios, including three face image data sets, i.e., UMIST, YaleB and ORL, two digital image data sets, i.e., USPS and MNIST, one Letter image data set Isolet. Negative elements in Isolet and USPS are set to zeros. There are 400 grayscale images of 40 objects in the ORL data set. we resize those images to 28 × 23. Thus, the feature size of each image is 644. The statistics of the six data sets are shown in Table 1.

To evaluate the superiority of our RCNMF for data representation, we compare it with six representative NMF-based methods, including unsupervised and semi-supervised ones. The compared methods are described below.

1) GNMF ^[35]: the GNMF encodes the local geometrical information of the data to the NMF objective function in an unsupervised learning scenario and is regarded as the baseline for comparison here.

2) MNMFL₂₁ ^[59]: It utilizes the L2, 1 norm to measure the quality of matrix factorization and the geometrical structure of the data to consider the local invariance; it is the sparse version of NMF.

3) CNMF ^[31]: It takes the class label as additional hard constraints to combine instances with the same class label in the low-dimensional space so that the part-based representation obtained by this method has the same label as the input data.

4) NMFCC ^[47]: It constructs a cost function to punish the violation of cannot-link and must-link constraints, which is considered as a regularization term added to NMF.

5) CPSNMF ^[23]: It applies pairwise constraint to preserve the geometrical structure of the input space, which promote the performance of the original NMF; it actually extends the GNMF to semi-supervised scenarios via using constraint propagation.

6) RSNMF ^[8]: It uses labeled instances to set up block-diagonal structure for learning the image representation so that instances involved in the same class are projected in the same low-dimensional subspace.

5.2.   Evaluation metric

After data presentations are learned, we comprehensively verify the performance of several methods in terms of two popular metrics widely applied in both DR and clustering approaches, i.e., normalized mutual information (NMI) and accuracy (ACC). For an approach, the higher NMI and ACC are, the better the clustering performance is. Given two random variables Y and Z, NMI ^[8,23,63] is defined as

where Y and Z represent the weight matrix of the real data label and clustering indicator provided by the algorithm, respectively. Specifically, if clustering indicator is achieved, NMI can be rewritten as

where ${n}_{i}$ denotes the number of instances belonging to ${C}_{i}$ ($1\le i\le K$) cluster, ${\widehat{n}}_{j}$ is the number of instances involved in the j-th class ($1\le j\le K$), and ${n}_{ij}$ describes the number of instances that are located at the intersection between the j-th class and cluster ${C}_{i}$.

The other metric is ACC that is employed to test the percentage of the result obtained by the clustering method. If the real data label and the clustering indicator are expressed as ${s}_{i}$ and ${r}_{i}$ respectively, ACC ^[8,23] is formulated as

where $\delta (a, b) = 1$ if a = b and $\delta (a, b) = 0$ otherwise. $map\left({r}_{i}\right)$ is a permutation mapping function, in which the clustering indicator ${r}_{i}$ is mapped into the real data label ${s}_{i}$.

5.3.   Parameter description

CNMF does not require any parameters. MNMFL₂₁ and GNMF have the graph regularization parameter α and the nearest neighbor size k. CPSNMF has a propagation parameter η except the above two parameters. NMFCC has two regularization parameters α and β. RCNMF has two regularization parameters, besides k and η. For CPSNMF, MNMFL₂₁, RCNMF, and GNMF, we specify the neighborhood size by setting k = 5 for all the data sets. Following CPSNMF, the propagation parameter η is set to 0.2. We choose the graph regularization parameter α within {10^-3, 10^-2, 10^-1, 1, 10¹, 10², 10³} for all the compared algorithms. For RCNMF, to satisfy the orthogonality, we set λ = 105 in the experiment. RSNMF has three essential parameters, the regularization parameter α, the norm parameter q and the dimensionality parameter m. According to RSNMF, the parameter q and m are set to 0.5 and 2, respectively. Values of various parameters are shown in Table 2.

5.4.   Results and analysis

To obtain the comprehensive comparison, we will conduct two types of experiments. One is that the evaluation is performed with different cluster numbers. The other is that the evaluation is done with different pairwise constraints. We describe the experiments as follow.

1) Since those typical NMF methods exploit lots of supervised information to guide matrix factorization, for the fair comparison, we apply ground-truth label to generate pairwise constraints to seek these two matrix factors. Specifically, we can randomly select 10% of all the given instances as labeled ones, which meets the requirements of CNMF and RSNMF. These labeled data are employed to generate pairwise constraints for NMFCC, CPSNMF and our RCNMF.

2) For the first type of experiment, we randomly choose 10% labeled instances for every category in the data set except the ORL data set. For ORL, we choose 20% labeled instances following ^[8,31], because each class has only one image if 10% labeled instances are chosen. The chosen labeled instances are applied to generate the corresponding cannot-link and must-link constraints. We randomly select different clusters k (1 ≤ k ≤ K) from each data set to check the performance of seven compared algorithms. For the second type of experiment, we take the number of ground-truth class as cluster numbers k for every data set. Furthermore, we randomly choose different labeled instances for each category in the data set to check the effectiveness of the compared algorithms.

3) For fair comparison, we exploit a random strategy to initialize these two matrix factors U and V. Following ^{[8,23,31,47,59]}, we use the classical K-means algorithm to cluster the learned coefficient matrix in the low-dimensional data space.

4) For given cluster number k, labeled instances, and pairwise constraints, we perform 20 experiments independently and report the average clustering results of these 20 experiments.

We conducted all experiments on an Intel CPU E5-1650 DUAL 3.60GHz with 16.0 GB RAM. Computational times for all algorithms are shown in Table 3. Figures 1 and 2 illustrate the graphical clustering results of ACC and NMI with different cluster numbers on the UMIST, YaleB, ORL, USPS, MNIST, and Isolet data sets, respectively. Figures 3 and 4 show the clustering results of ACC and NMI with different numbers of labeled instances on the UMIST, YaleB, USPS, Isolet, and MNIST data sets, respectively. In the second type of experiment, we do not compare the clustering performance of seven algorithms on ORL in the light of different numbers of labeled instances, since there are only 10 instances in each category of ORL. From the experimental results, a few interesting observations can be observed.

1) The proposed RCNMF algorithm can provide better performance on the given six data sets and is superior to other algorithms. This is due to the fact that our RCNMF can learn a compact and discriminating representation. Besides, the RCNMF is the only one to achieve high performance on all the data sets used by this paper. Obviously, local and global structures of data via constraint propagation play a significant role in formulating the intrinsic data representation. Therefore, the RCNMF is able to effectively apply the pairwise constraints to promote the performance of NMF-based algorithm.

2) RCNMF, RSNMF, CPSNMF, NMFCC and CNMF are consistently superior to the baseline method on almost data sets. This indicates that semi-supervised NMF learning from a combination of both labeled and unlabeled instances can guide matrix decomposition better than unsupervised peer. Interestingly, these semi-supervised algorithms have significant differences on the clustering performance. For example, for the MNIST data set, the proposed RCNMF method achieves the highest clustering performance of 68.45% by ACC, while CNMF just achieves 55.23%. For two unsupervised methods, as a sparse version of GNMF, MNMFL₂₁ always achieves better performance than GNMF.

3) The results show that RCNMF outperforms CPSNMF, although both RCNMF and CPSNMF use constraint propagation to discover discriminating representations for data. This is due to two reasons. One is that the L_{2, 1}-norm objective function of RCNMF is robust to noise and outliers. The loss function using L_{2, 1}-norm can substantially improve the performance of NMF, which is testified by NMF-based methods ^[8,56,58,59]. The other is that the L_{2, 1}-norm regularization term on the basis matrix U in RCNMF can guarantee U sparse in rows and selects some representative features. The sparse formulation can bring encouraging performance improvements. Additionally, it is easy to get the optimal solution for RCNMF because of the additional orthonormal constraint on the factor V in the objective function.

4) CPSNMF outperforms other three semi-supervised methods on most data sets. RSNMF embeds instances from the same class into the same subspace by exploiting the block-diagonal structure of data. NMFCC enforces a cannot-link to approximate 0 and a must-link to approximate 1, which is added to NMF as the regularization term. CNMF forces instances with the same label to have the same representation in the low-dimensional space. However, RSNMF, NMFCC and CNMF ignore the important role of the local structure of the data space for steering matrix decomposition. Besides, the three methods do not map instances from different classes sufficient far in the low-dimensional representation space. We can observe that NMFCC and CNMF perform relatively poorly among the five semi-supervised NMF methods. In addition to the above shortcomings, another disadvantage is that both NMFCC and CNMF are sensitive to data noise and outliers.

5) Another interesting observation is that semi-supervised NMF methods achieve relatively low clustering accuracy when a few labeled instances from data sets are chosen in the experiment. For example, on UMIST, YaleB and MNIST data set, MNMFL₂₁ is comparable with CPSNMF, RSNMF, NMFCC and CNMF. Few labeled instances cannot represent the data distribution well when the data set distribution is complex. In fact, two or three labeled instances of each class are not enough to characterize a data representation. However, as the number of available labeled instances, the performance of semi-supervised methods is steadily improved. The propose method can bring encouraging performance improvements compared to other semi-supervised and unsupervised NMF methods, when there are a small number of labeled instances. The reason is that RCNMF efficiently use the supervised information and sufficiently maps instances from different clusters far away from each other in the low-dimensional space.

5.5.   Robustness investigation

To investigate the robustness of these methods, we add salt & pepper noise with different densities to four data sets used in this paper. It is worth noting that the data with noise density of 0 is clean data. The experimental results shown in Figures 5 and 6. It can be observed that the performance of all algorithms decreases when the data are contaminated by noise. Moreover, the higher the noise density, the more performance degradation of the algorithm. Although the performance of the proposed RCNMF degrades when decomposing noisy data, it still outperforms the other compared algorithms. As we can see, RCNMF-KL can also obtain relatively satisfactory results. Compared with RCNMF, its performance decreases more with the increase of noise density of the data. MNMFL₂₁ and RSNMF are superior to the remaining algorithms. This is due to a fact that the L_{2, 1} norm-based cost function is robust to noise and outlier.

5.6.   Parameter selection

The RCNMF method has three necessary parameters: nearest neighbors p, two trade-off parameters α and β. The proposed algorithm will degenerate into the L_{2, 1}-norm NMF (L_{2, 1}-NMF) ^[58] when α = 0 and β = 0. Our RCNMF becomes the L_{2, 1} norm version of CPSNMF when β = 0. Figure 7 demonstrates how the average accuracy of the RCNMF becomes with the trade-off parameters α and β, respectively. We can see that different parameters have different effects on the performance of the algorithm. When these two parameters are in the range of [0.1,100], RCNMF can achieve consistently good performance.

Figure 8 shows that the performance of RCNMF becomes with the nearest neighbor parameter k. As we can see, different values of k have great influence on the RCNMF. Graph-based methods generally construct k-nearest graph to depict the local structure of the data space. These methods are based on the assumption that nearby instances have the same class label ^{[9,15,21,22,23,35,55,56]}. Obviously, this assumption likely fails to hold when k enlarges. This is why the performance of RCNMF drops with the increase of k. In fact, graph-based methods suffer from this torment as reported in ^[23,35]. Generally, the value of p ranges from an integer of 3 to 9.

5.7.   Convergence study

In Section 4, the convergence of the proposed method has been proven and also the computational complex is analyzed. Here, we inspect the convergence speed of the proposed algorithm. Figure 9 demonstrates the convergence cures of RCNMF on the two data sets. In every figure, the x-axis represents the iteration number and the y-axis describes the value of the cost function. We can observe that the updating rule of the proposed RCNMF method converge relatively fast. Generally, the iterations of our algorithm on these data sets are less than 300.

6.   Conclusions

We have proposed a novel robust semi-supervised nonnegative matrix factorization algorithm, called RCNMF. RCNMF models local and global structures of data via constraint propagation to make latent representations of instances involved by the same class are mapped closer and those of instances involved by different classes farther. The proposed method introduces the L_{2, 1}-norm into the objective function and thus is robust to noise and outliers. Furthermore, the L_{2, 1}-norm constraint for the factorial matrix is added to the loss function as the regularizer, which ensures the new representation sparse in rows. Experimental results on six real-world data sets show that our proposed framework is superior to other state-of-the-art algorithms.

Acknowledgments

This work was supported by Industry & University Research Cooperation Project of Jiangsu Province under Grant BY2020056. The authors extend their appreciation to the Deanship of Scientific Research at King Saud University for funding this work through research group no. RG-1441-331.

Conflict of interest

The authors declare no conflict of internet.