Deep Latent Low-Rank Fusion Network for Progressive Subspace Discovery

1 Introduction

Representation learning is always a fundamental problem to obtain the underlying explanatory factors and features for the subsequent data classification or clustering tasks [Chen et al., 2019 and 2020] [Zhang et al., 2016 and 2019]. Representation learning is still challenging in reality due to the complexity and diversity of data [Lu et al., 2019] [Su et al., 2019] [Acharya et al., 2019] [Ding et al., 2018].

Since most real data can be characterized using low-rank subspaces, low-rank coding methods can recover the underlying subspaces and obtain notable features [Liu et al., 2019] [Ren et al., 2019]. Low-Rank Representation (LRR) [Liu et al., 2013] is one of the most classical algorithms to discover multi-subspaces, but it is essentially a transductive method failing to handle new data efficiently. To address the out-ofsample issue, Inductive Robust Principal Component Analysis (IRPCA) [Bao et al., 2012] was recently proposed seeking a low-rank projection to map samples into underlying subspaces. To enable a solution for subspace segmentation and feature extraction, Latent LRR (LatLRR) [Liu et al., 2011], was proposed, which decomposed data into a principal feature part, a salient feature part and a sparse error. Although LatLRR resolves the insufficient sampling issue and obtains enhanced performance over LRR, it still suffers from a high computational cost due to using Nuclear-norm to approximate the rank function to constrain the subspaces, while the computation of the Nuclear-norm needs the time-consuming Singular Value Decomposition of matrices at each iteration, especially for large-scale datasets. To improve the efficiency, a Frobenius-norm based LatLRR (FLLRR) [Yu et al., 2018] was proposed, which approximates the rank function using Frobenius-norm. But the Frobenius-norm is sensitive to noise and outliers, which may produce inaccurate representations.

It is noteworthy that the above algorithms have a common drawback, i.e., they are "shallow" models using single-layer structures. As a result, they cannot obtain deep information and subspaces. But due to the strong representation ability of the deep neural networks [Kim et al., 2019], deep low-rank coding models equipped with carefully designed hierarchical structures should be able to obtain the enhanced performance. In fact, researchers have also designed some deep low-rank coding models, such as Weakly-supervised Deep Nonnegative Low-rank Model (WDNL) [Li et al., 2017a], which finds the intrinsic relations between images and tags by removing noise or irrelevant tags, but it is unclear how to handle images directly and the results are usually incomplete. Another deep model is Deep Low-Rank Subspace Ensemble (DLRSE) [Xue et al., 2019], where the Frobenius-norm is used as a low-rank constraint. DLRSE uses the deep matrix factorization to learn the diverse hierarchical structures and obtains the low-rank representations from extracted factors. But DLRSE is originally proposed for multi-view clustering, which clearly differs from our task. To cluster big data effectively, a Projective Low-rank Sub-space Clustering via Learning Deep Encoder (PLrSC) [Li et al., 2017] has been recently proposed.

PLrSC uses a small database randomly sampled from a big dataset and train a deep encoder, and then a deep encoder is used to compute the low-rank representations of all samples. However, it will be not easy to determine the sampling frequency based on different real datasets in practice.

In this paper, we mainly propose a general and progressive deep low-rank fusion network that can unfold existing latent low-rank methods into multilayers for the hierarchical representation and deep subspace discovery. The major contributions of this paper are summarized as follows:

(1) Technically, a simple yet effective progressive deep representation learning model termed Deep Latent Low-Rank Fusion Network (DLRF-Net) is derived. DLRF-Net can learn deep hierarchical information and subspaces from input data. The advantage of this practice is that multiple layer low-rank coding structures can deliver rich and useful hidden hierarchical information that has a great potential in learning more powerful deep representation and subspace structures. To be specific, DLRF-Net in each layer aims to refine the features and subspaces progressively from previous layers by fusion, i.e., it recovers deep hierarchical information by respectively congregating the projective and clustering subspaces in each layer to produce accurate results. We compare the traditional single-layer low-rank models with DLRF-Net in Figure 1.

1. The network of DLRF-Net is simple, general and easy to extend. Specifically, many existing latent low-rank coding models such as LatLRR and FLLRR can be easily extended from single-layer to multiple-layers using DLRF-Net. In this paper, we mainly explain our basic idea rather than deriving a complex formulation, two simple deep network models are constructed based on embedding LatLRR and FLLRR into DLRF-Net as examples for the multi-layer low-rank coding, which we call Nuclear-norm based DLRF-Net (nDLRF-Net) and Frobenius-norm based fast DLRF-Net (fDLRF-Net).

(3) Extensive simulations on public databases demonstrate that both nDLRF-Net and fDLRF-Net can deliver enhanced performance than the related single-layer models. That is, the multilayer idea of DLRF-Net is feasible and effective.

2 Related Work

We describe the closely-related low-rank coding algorithms.

2.1 LatLRR and FLLRR

Given a data matrix   1 2 , , n N N X x x x    , where n i x  is a sample represented using an n-dimensional vector and N

is the number of samples, then LatLRR improves LRR using the unobserved hidden data XH to extend the dictionary and overcome the insufficient data sampling issue. Specifically, LatLRR considers the following coding formulation:

where   rank is rank function and XO is the observed data matrix. Supposing that XO and XH are sampled from the same collection of low-rank subspaces, by using the Nuclear-norm to approximate the rank function and using sparse L1-norm on error term E, LatLRR recovers the hidden effects by

where * Z is the Nuclear-norm of Z [Liu et al., 2013] [Xie et al., 2017], i.e., the sum of its singular values, XZ and LX are principal features and salient features respectively, and  is a positive scalar. Since LatLRR uses the Nuclear-norm constraints on Z and L, the SVD process is involved, which is time-consuming. Note that Frobenius-norm F can also be used as the convex surrogate of the rank function [Yu et al., 2018]. Besides, the optimization of Frobenius-norm is very efficient. The objective function of FLLRR is defined as

from which multi-subspace structures can be recovered by Z and the notable features can be extracted using L.

2.2 Projective Low-rank Subspace Clustering via Learning Deep Encoder (PLrSC)

Assuming that ' 1 , ,        i k n N Y Y Y Y is a big dataset and over-sufficiently drawn from a union of k subspaces, where N is the number of samples in all subspaces. PLrSC assumes that 1 , , i k X X X X      n N   is a small dataset sampled randomly from Y and X is still sufficient. First, PLrSC learns a non-iterative deep encoder   ; de f X  , where is the learning parameter to approximate low-rank representations. Then, the deep encoder is utilized to obtain the low-rank codes for replacing the costly non-linear Singular Value Thresholding (SVT) [Cai et al., 2010] operations. Thus, the predictive lowrank decomposition of PLrSC can be written as follows:

where n N E   denotes a sparse error,  is the regularization parameter for E,  is a control parameter for approximation term   2 ; de F Z f X   .         2 ; = M i de f X g W g W g W X  is a deep encoder with M layers, where   g is an activation function (e.g., sigmoid or ReLU).  is a learning parameter set, where     2 1 1 2 , , , , M M l l l l M W W        . i l denotes the number of the units in the i-th layer ( 1 l d  and M l N  ). Then, PLrSC employs the alternating direction algorithm (ADM) [Liu et al., 2013] and a gradient descent algorithm (GD) [Li et al., 2015] to optimize the above problem. Finally, PLrSC applies the landmark-based spectral clustering (LSC) algorithm to cluster the big dataset Y [Li et al., 2017].

. . .

3 Proposed DLRF-Net

3.1 Objective Function

DLRF-Net designs a hierarchical and progressive approach, i.e., the representation in the uncovered subspaces are learnt layer by layer. That is, the deep principal features XZ0Z1…Zl-1 and deep salient features Ll-1…L1L0X from the (l-1)-th layer are fed into the l-th layer, which are further decomposed into a deep principal feature part, a deep salient feature part and a deep sparse error. The whole framework of our DLRF-Net is shown in Figure 2. Assuming that DLRF-Net has M layers, the decomposition process of our DLRF-Net framework in the l-th layer can be presented as follows:

where 1 l Z and 2 l Z are the deep coefficient matrices, 1 l L and 2 l L denote the deep projection matrices that are learned from XZ0Z1…Zl-1 and Ll-1…L1L0X in the l-th layer, respectively. Note that Z0 and L0 are included to simplify the descriptions, which are set to the identity matrices, i.e., the input of the first layer is the original data. It should be noted that for the optimization in the l-th layer, Z0, Z1, …, Zl-1, L0, L1, …, Ll-1 are known variables that are updated in the last layer. As such, intuitively from the multilayer leaning process, deep principal features XZ0Z1…Zl-1 and deep salient features Ll-1…L1L0X are learnt progressively from different layers, i.e., extracting fine-grained features from layer to layer.

Finally, deep principal features XZ0Z1…Zl and salient features Ll…L1L0X in the l-th layer can be obtained as

The above subspace fusion operation can potentially make the learned representations more accurate by fusing feature information from deep principal and salient features in previous layers. The above averaging operation can also prevent the feature information loss and balance the information from deep principal and salient features in each layer. As such, we have the following model for DLRF-Net in the l-th layer:

where p is the matrix p-norm, which can be Nuclear-norm or squared Frobenius-norm. l  is a positive tunable parameter that replies on the noise level of data [Liu et al., 2011]. We name the Nuclear-norm based DLRF-Net as nDLRF-Net and name the squared Frobenius-norm based DLRF-Net as fDLRF-Net. The objective function of fDLRF-Net can then be defined as follows for deep subspace discovery:

Next, we show the optimization procedures of DLRF-Net.

4 Optimization

We mainly describe the optimization of fDLRF-Net in detail, as the optimization of nDLRF-Net is similar. Since Zl, Pl and El depend on each other, we update them alternately. We use the inexact Augmented Lagrange Multiplier (Inexact ALM) algorithm [Lin et al., 2009] for efficiency.

Algorithm 1 Solving Eq.(9) by Inexact ALM (l-th layer) Inputs: Reconstructed data 1 l A  , tunable parameters , . l l   Initialization:           0 0 0 0 0 1 2 1 2 1 0, 0, 0, 0, 0, 0       l l l l l t Z Z L L E ,       0 0 0 2 1 2 6 0 6 7 max 0, 0, 0, 10 , =10 , =1.12, 10            l l l E Y Y .

While not converged do

1. Update the coefficients sub-matrices   1 1  t l Z and   1 2  t l Z by using Eq.(12-1e), and obtain       1 1 1 1 2 2      t t t l l l Z Z Z ;
2. Update the sparse errors   1 1  t l E and   1 2  t l E by Eq.(16-17);
3. Update the projection sub-matrices   1 1  t l L and   1 2  t l L by using Eq.(14-15), and obtain       1 1 1 1 2 2      t t t l l l L L L ;
4. Update the Lagrange multipliers   1 1  t l Y and   1 2  t l Y ;
5. Update the parameter l by   1 max =min ,     t t l l ;
6. Check for convergence: Suppose  1 1 1 1 1 1 ,        l l l l l l P P Z L P E  2 2 2 1 1 1          l l l l l l S S Z L S E , stop; else 1   t t . End while

Output: * 1 * 1 , .     t t l l l l Z Z P P

To simplify the descriptions of optimization, we train the model layer by layer. To learn features in the l-th layer (l=1, 2,…, M), the target function can be defined as

Denote by 1 0 1 ...    l l P XZ Z and 1 1 0 ... l l S L L X   = two auxiliary matrices, the Lagrange function of Eq.(9) can be obtained as

where 1 l Y and 2 l Y are Lagrange multipliers, and l denotes a positive parameter. Then, fDLRF-Net updates the variables by solving . Note that the optimization procedures of our fDLRF-Net in the l-th layer can then be detailed as follows:

Fix others, update Zl: For the optimization of l Z , we need to solve 1 l Z and 2 l Z . By removing the irrelevant terms, we can update 1 l Z and 2 l Z by the following reduced problem:

where 1 1 1 1 1 l l l l l P L P E        and 2 2 1 1 1 l l l l l S L S E        . We first show the optimization of 1 l Z . By taking the derivative of   1 2 ,  l l Z Z w.r.t. 1 l Z and zeroing the derivative, we can infer the coefficients matrix 1 l Z at the (t+1)-th iteration as follows:

where     1 1 1 1 1        t t t l l l l l P L P E . Similar to the optimization of 1 l Z , we can infer   1 2 t l Z  in the (t+1)-th iteration as

where     2 2 1 1 1        t t t l l l l l S L S E . After optimizing the   1 1  t l Z and   1 2  t l Z , we can obtain       1 1 1 1 2 2      t t t l l l Z Z Z .

Fix others, update Ll: By removing the irrelevant terms from , taking the derivatives of   1 2 ,  l l L L w.r.t 1 l L and 2 l L , , and zeroing the derivatives, we can similarly obtain

where     1 1 1 1 1 1 1 t t t l l l l l P P Z E        + and     1 2 2 1 1 1 1         t l l l l l t t S S Z E . After optimizing the projection matrices   1 1  t l L and   1 2  t l L , we can obtain       1 1 1 1 2 2      t t t l l l L L L .

Fix others, update 1 l E and 2 l E : By taking the derivative of Lagrange function w.r.t. 1 l E and 2 l E respectively and zeroing the derivatives, we can infer 1 l E and 2 l E as

which can be easily solved by the shrinkage operator [Lin et al., 2009], where 1 l and 2 l are auxiliary matrices defined as       1 1 1 1 1 1 1 1 t t t t l l l l l l l P Z L P Y         + and   1 2 2 1      t l l l S Z     1 2 2 1    + t t t l l l l L S Y . For complete presentation of our model, we summarized the optimization procedures of solving the sub-problem of Eq.(9) in the l-th layer in Algorithm 1.

5 Discussion

5.1 Relationship Analysis

We mainly discuss the relations of our DLRF-Net to LatLRR and FLLRR. To facilitate the analysis, we consider the special case that l=1.We first express this special case as

Since Z0 and L0 are initialized to the identity matrices in the optimization, the two constraints are the same. As such, it is clear that when we use the Frobenius-norm to constrain the matrices Z1 and L1, the problem identifies FLLRR; while we use the Nuclear-norm as constraints, the resulting problem is identical to LatLRR. That is, both FLLRR and LatLRR are the special causes of our DLRF-Net framework.

5.2 Computational Time Complexity

We analyze the complexity of each layer of our deep models. For fDLRF-Net, SVD is not used and the major computation is updating the matrices Zl and Ll. Thus, the time complexity of Algorithm 1 is equal to that of FLLRR. Thus, it is easy to infer that the total time complexity of fDLRF-Net is M times that of each layer, where M is the number of layers, which is usually a small value. For nDLRF-Net, the time complexity of each layer is the same as that of regular LatLRR and the total time complexity is M times that of each layer.

6 Experimental Results and Analysis

We conduct experiments to evaluate the effectiveness of our fDLRF-Net and nDLRF-Net, and show the comparison results with other related methods, including FLLRR, LatLRR, LRR, Robust LatLRR (rLatLRR) [Zhang et al., 2014b], Laplacian Regularized LRR (rLRR) [Zhang et al., 2014a], Sa-LatLRR [Wang et al., 2018] and PLrSC [Li et al., 2017b]. Three real image databases are involved, including two face datasets (i.e., CMU PIE [Sim et al., 2003], UMIST [Graham et al., 1998]) and the Fashion MNIST database [Xiao et al., 2017]. The details of used databases are described in Table 1. We follow the common procedure to resize each face image into 32×32 pixels and images of the Fashion MNIST dataset are resized into 28×28 pixels. We perform all experiments on a PC with Intel (R) Core (TM) i7-7700 CPU @ 3.6 GHz 8G.

6.1 Visual Image Analysis by Visualization

Visualization of coefficient matrix Z. To represent data appropriately, Z should have a block-diagonal structure. Each block denotes the coefficients for certain subject so that each sample can be reconstructed by the samples of one class as much as possible. We follow [Liu et al., 2011] to construct 10 independent subspaces  10 1 i i S  and apply this artificial data for DLRF-Net. The visualization of Z in the first four layers are illustrated in Figure 3. We see that all coefficient matrices Z have block-diagonal structures. But compared with the 1-th layer, the results of other layers have less noise and wrong inter-class connections. It can also be found that the subspace structures of Z are improved progressively, i.e., the learned structures from the 3-rd and 4-th layers are better that from the 2-nd layer. But the difference of the structures of Zs in the 3-rd and 4-th layers is small, i.e., our DLRF-Net can remove noise contained in features and recovery the subspaces of Z by using small number of layers. That is, the structures of the coefficient matrix Z will not become better, even though we use more layers involving high computational cost. In all the simulations, the results of fDLRF-Net and nDLRF-Net in the 1-th layer corresponds to FLLRR and LatLRR, respectively.

Visualization of the recovered features XZ. We evaluate fDLRF-Net and nDLRF-Net by visualizing recovered deep features XZ. Given a data matrix X, DLRF-Net decomposes it into principal features XZ, salient features LX and a sparse error E in each layer. CMU PIE face dataset is used. This face image database contains 68 persons with 41368 images under varying poses, illuminations and facial expressions. 170 near frontal images per person are employed for CMU PIE, which contains five near frontal poses (C05, C07, C09, C27, and C29). To evaluate the robustness properties, random Gaussian noise with variance 500 is included into the image data. Some original images, noisy images and recovered principal features in the first three layers are shown in Figure 4. We see find that fDLRF-Net and nDLRF-Net can effectively remove the shadow and noise in images in a progressive way, compared with the recovered results of FLLRR and LatLRR.

6.2 Quantitative Clustering Evaluations

We compare each model for clustering images. UMIST and Fashion MNIST are evaluated. UMIST has 1012 images from 20 different individuals. Fashion-MNIST has 10 classes and 70000 unique products. In this study on Fashion-MNIST, we choose 1000 samples per class, i.e., totally 10000 samples. To evaluate the performance, we follow the common procedures and use the coefficient matrix Z* of each method to construct the weights by   * * 2 T W Z Z   and then use the Normalized Cuts (NCut) [Shi et al., 2000] for clustering. For PLrSC and DLRF-Net, we use the coefficients from the final layer. For each number K of clusters, we choose K categories randomly and the results are averaged over 30 initializations.

The clustering accuracy (AC) [Cai et al., 2017] is used as the quantitative metric. The values of AC on evaluated databases are shown in Table 2. We see that: (1) the clustering accuracy of each method goes down as the number of categories increases, since clustering more data is difficult than clustering less; (2) Our fDLRF-Net and nDLRF-Net deliver higher ACs than the other competitors, especially for FLLRR and LatLRR, implying that DLRF-Net can learn more effective representations by mining deep information.

6.3 Noisy Image Clustering Against Corruptions

We investigate the robustness properties against noisy cases that images are corrupted. UMIST and Fashion MNIST are used. Random Gaussian noise with different variance (100, 200, …, 500) is added to examine the robustness. For each setting, we average the result over 30 random initialization for NCut. We set the number K of clusters as 5. Some noisy images and clustering accuracy are shown in Figure 5, where the clustering results of five layers of our fDLRF-Net and nDLRF-Net are described. We see clearly that: (1) generally speaking the clustering accuracy of each method goes down with the increasing level of noise, as clustering data of high noise level is more difficult than clustering that of low noise level; (2) the best records are usually obtained in the 2-nd layer and the 3-rd layer, by comparing with the other cases.

6.4 Investigation of Parameters

UMIST database is used. DLRF-Net has one parameter  , so we can select the most important one by a linear search from   8 6 6 8 10 ,10 ,...,10 ,10   . We set the number K of clusters to 5 and show the analysis results of the first three layers in Figure 6. For each layer, we select the best parameter, and then we fix it to learn deeper features of next layer. We find that  usually becomes a lager one with increasing number of layers, which is easy to understand. Since DLRF-Net recovers the subspaces progressively and learnt susbapces become clean layer by layer. Note that similar observations can be found from the other datasets, but the results will be not presented.

7 Conclusion

We proposed a new progressive deep latent low-rank fusion network to uncover deep hidden features and deep clustering structures. DLRF-Net discovers the subspaces by refining the principal and salient features from previous layers progressively and then fusing the subspaces. Specifically, DLRF-Net recovers hierarchical features by congregating the projective subspace and subspaces in each layer. Most existing latent low-rank coding models can also be easily extended to multilayer scenario for learning deep features. In future, more effective deep low-rank fusion strategies will be explored.

Acknowledgments

This work is supported by the NSFC (61672365, 61806035 and U1936217) and the Fundamental Research Funds for the Central Universities of China (JZ2019HGPA0102), and New Generation AI Major Project of Ministry of Science and Technology of China (2018AAA0100601). Zhao Zhang and Zheng Zhang are the corresponding authors of this paper.