An Improved Latent Low Rank Representation for Automatic Subspace Clustering

1 Introduction

Subspace clustering has been widely studied in the fields of computer vision and machine learning, such as motion segmentation , face segmentation and image clustering [Lai et al., 2017]. Vidal[Vidal, 2011] roughly divides subspace clustering algorithms into four groups: algebraic, statistical learning, iterative learning , and spectral clustering based methods. Spectral clustering based methods construct a similar matrix between different data points, and then apply spectral clustering to segment the samples. Spectral clustering can be viewed as the graph-based clustering because its performance is directly determined by the obtained graph[Jie et al., 2018]. As a successful example of spectral clustering, LRR is developed to learn the lowest-rank representation of data samples[Liu et al., 2010]. After that, a series of improvement approaches based on LRR are proposed, and have achieved certain success[Liu et al., 2011;Zhuang et al.,2017]. However, existing search methods still have clear limitations. For example, 1)LRR can effectively discovers the global structure of data. However, it is inability to identify local structure, which can affect the expression of the model;2)Usually, the observed sample matrix itself is selected as the dictionary, but it is inappropriate when the observations are insufficient and/or grossly corrupted.

Besides, when we apply spectral clustering to segment the samples, the cluster number is a pre-specified parameter in traditional subspace clustering which cannot adaptive determine the number of effective clusters and find out the optimal clustering scheme, and efficiency of subspace clustering approaches, in which first clustering and then enumerating all the possible cases, were greatly affected by the number of clusters.

Is there a solution that can address the aforementioned research challenge?In this paper, an improved latent LRR model and a novel automatic subspace clustering method are developed, which aim to address the aforementioned challenges. Although the observations are insufficient and/or grossly corrupted, the improved latent LRR method can better capture the underlying local structure information in dataset and enhance the interpretation of model. After that, we employ the automatic subspace clustering approach to segment the samples.

2 Contributions

2.1 Improve Latent LRR Model

In this work, we apply a effective Euclidean distance and non-negative constraint jointly to the latent LRR model. Euclidean distance constraint help to learn low dimensional representation of invariance of rotation and offset, and adaptive select few nearest neighbor samples for representation. Non-negative constraint can eliminate the undesired solution, and then we can obtain a better similar matrix between data points. After that, the sparse and local information can be preserved in this way. By jointly introduce the two constraint, the novel improved latent LRR

subject to Z X X X H O O ] , [ = , ( ) 0 = Z diag and 0  Z . Here, the concatenation of O X and H X is used as the dictionary, O X and H X represent the observed and unobserved sample matrix respectively. Note that the diagonal elements of graph is set to zero, which can remove the influence of self-representation. In practice, a fraction of the samples are grossly corrupted, so a sparse error term should be incorporated. We can derive the joint objective

, n Z E i j

Z X X X H O O ] , [ = , ( ) 0 = Z diag and 0  Z , where 1  and 2  are the trade-off parameters. Then, the optimization can be solved through an efficiently iterative algorithm. After that, we can obtain the graph Z , where Z is derived from a non-negative affinity matrix and can be used to cluster.

2.2 Automatic Subspace Clustering

Modeling the cluster number in the optimization framework is intractable especially on the complex data space.In this work, we can model the cluster number automatically via the bias and variance trade-off. Automatic subspace clustering features an open cluster-number in the clustering phase, where the cluster number can be automatically added and discarded on the fly.Specifically, automatic subspace clustering is capable of initiating its cluster number from scratch without a fixed number. Its number automatically evolves in respect of the NS formula which produces an estimate of the data bias and variance[Andri et al., 2019]. Here, the NS formula is defined as the expectation of the squared predictive errors 2 [( ) ] E C C - , where C represents

the true class label and the C represents the predictive class label . After several mathematical derivation steps, we can obtain the bias formulas 2 ( [ ] ) E C C - and variance formulas

2 2 ( [ ] [ ] ) E C E C - respectively. Then we can monitor the quality of the subspace clustering automatically and not rely on the pre-specified cluster-number. In other words, the cluster number automatically augments 1 K K = + if it appear a high bias or decreases 1 K K = - if it signifies a high variance. It is noteworthy that the computational cost of this method is inexpensive especially on the complex data space, because the NS formulas is comparatively simple and can be calculated recursively.

Finally,we verify the performance of proposed latent LRR and automatic subspace clustering on both synthetic and real benchmark datasets by clustering accuracy(Acc) and normalized mutual information (NMI), and compares with the state-of-art baseline methods in the above aspects. We also verifies the convergence of the algorithm and analysis the computation complexity. However, the trade-off parameters about improve latent LRR need to be set respectively based on different datasets in order to obtained the desired performance.

3 Related Work

Subspace clustering base on LRR has been studied extensively in the fields of computer vision and machine learning. Liu propose latent LRR model base on the traditional LRR model, which aims to address the insufficiency of the observed data[Liu et al., 2011]. Recently, many researchers shown the locality preserving is critical to the expression of the model.Although NNLRS model achieve adaptive select few samples for data representation, the sparsity of this model doesn't guarantee[Zhuang et al., 2017]. Jie et al. proposed the LRR with adaptive graph regularization and can efficiently capture the local and sparse information of data simultaneously, but the performance of model is poor when the observations are insufficient and/or grossly corrupted[Jie et al., 2018]. In this paper, an improve latent LRR is presented to address the aforementioned issues, and then we can obtain a better graph for cluster. Traditional subspace clustering characterizes a fixed numbers of cluster, which isn't beneficial to make model selection automatically. We proposed an automatic subspace cluster approach via the bias and variance trade-off, which can identify the cluster number automatically.

4 Future Work

Future work should consider that the performance of proposed latent LRR depends on compute speed, memory demand and accuracy, so we envision that a more complex nonlinear model could be constructed in order to bridge that gap. Besides, the noise has much more complex statistical structures in practice, so we can construct a novel model under the Bayesian framework, which can fit a wide range of noises such as Gaussian, Laplacian, sparse noises and any combinations of them. The proposed latent LRR also should be applied to other tasks, such as large image classification, feature extraction and background modeling, etc.