Low rank representation with adaptive distance penalty for semi-supervised subspace classification

Highlights

• A novel LRR with adaptive distance penalty method is proposed for SSL.

• LRRADP can better capture both the global structure and local affinity of the data.

• The projected based LRRADP(LRRADP²) shows impressive robustness.

• Extensive experiments demonstrate the effectiveness of the proposed method.

Abstract

The graph based Semi-supervised Subspace Learning (SSL) methods treat both labeled and unlabeled data as nodes in a graph, and then instantiate edges among these nodes by weighting the affinity between the corresponding pairs of samples. Constructing a good graph to discover the intrinsic structures of the data is critical for these SSL tasks such as subspace clustering and classification. The Low Rank Representation (LRR) is one of powerful subspace clustering methods, based on which a weighted affinity graph can be constructed. Generally, adjacent samples usually belong to a union of subspace and thereby nearby points in the graph should have large edge weights. Motivated by this, in this paper, we proposed a novel LRR with Adaptive Distance Penalty (LRRADP) to construct a good affinity graph. The graph identified by the LRRADP can not only capture the global subspace structure of the whole data but also effectively preserve the neighbor relationship among samples. Furthermore, by projecting the data set into an appropriate subspace, the LRRADP can be further improved to construct a more discriminative affinity graph. Extensive experiments on different types of baseline datasets are carried out to demonstrate the effectiveness of the proposed methods. The improved method, named as LRRADP², shows impressive performance on real world handwritten and noisy data. The MATLAB codes of the proposed methods will be available at http://www.yongxu.org/lunwen.html.

Introduction

In many big data related applications, the problem of effectively connecting unlabeled data with labeled data is of central importance [1], [2]. For example, in the applications of image based web searching and image based object recognition, the labeled data is usually limited and the unlabeled data are rich and available in internet. In these problems, the target goal is to build the connection between unlabeled data and labeled data and then identify the labels of the unlabeled data. Semi-supervised Subspace Learning (SSL) [3], [4], [5], [6] is a family of techniques that exploits the “manifold structure” of the data by using both labeled and unlabeled samples [7], [8].

Constructing a graph of the local connectivity of data is an effective strategy for SSL due to its success in practice [9], [10], [11]. The graph based SSL methods treat both labeled and unlabeled samples from the data set as nodes in a graph, and then instantiate edges among these nodes which are weighted according to the affinity between the corresponding pairs of samples. Suppose that the data set is noiseless and embeds in independent subspaces, the graph identified by the respective SSL method should be a block-diagonal matrix and each block corresponding to a subspace. Subspace clustering is able to produce exactly correct clustering result based on the block-diagonal matrix. To address this issue, we build a weight graph $G=(V,W)$, where V is the vertex set denoting nodes of the graph corresponding to N data points and W ∈ R^{N × N} is a symmetric non-negative weight matrix representing the relationship among the nodes. A non-zero weight reflects the affinity between corresponding nodes and a zero weight denotes that there is no edge jointing them. An ideal similarity matrix W, hence an ideal weight graph G, is one in which nodes that correspond to points from the same subspace are connected to each other and there is no edge between any two nodes that correspond to points belonging to different subspaces. Thus, given a data set, the problem of graph construction is to determine the weight matrix W. A perfect similarity graph built by SSL has n independent connected components corresponding to n subspaces and then by applying spectral clustering the labels can be propagated from the labeled samples to unlabeled samples over the graph [12], [13], [14], [15].

The recently Low Rank Representation (LRR) [13], [14] is a promising weight graph construction method. The target of the LRR aims at finding the lowest-rankness representation among all candidates that can express the data vectors as linear combinations of the basis in a proper dictionary. Consider a set of data $X=[x_1,x_2,\dots ,x_n]$ in R^d, each column of which is a sample that can be represented by the linear combination of a basis of d vectors. If we form the basis matrix as $A=[a_1,a_2,\dots ,a_m]$, the X can be represented as:

$$X=AZ,$$

where $Z=[z_1,z_2,\dots ,z_n]$ is the coefficient matrix with each z_i characterizing how other samples contribute to the representation of x_i. Since the data can only be essentially represented by those data in the same subspace, the nonzero elements in z_i represents that the corresponding samples are in the same subspace. Therefore, minimizing rankness of the data vector space could be an appropriate criterion to cluster data drawn from multiple linear subspaces. That is, LRR discovers the lowest rankness of the representation of the data set as follows.

$$\underset{Z}{min}rank\left(Z\right),s.t.X=AZ,$$

where rank(•) denotes the rankness of a matrix. The low rankness constraint guarantees that the coefficients of samples coming from the same subspace are highly correlated. When the data are clean and exactly from linearly independent subspaces, the similarity matrix built by this way is an ideally n block diagonal matrix corresponding to n subspaces.

LRR is an effective framework for exploring the multiple subspace structures of data. Based on the LRR, lots of recent efforts have been made to exploit ways of constructing a discriminative graph for SSL [16], [17], [18], [19]. Liu et al. [18] proposed a latent low rank representation method for subspace clustering by approximating and using the unobserved data hidden in the observed data to resolve the issue of insufficient sampling. Zhang et al. [19] extended the latent LRR by choosing the sparest solution in the solution set to increase the robustness of the method. Wei et al. [20] proposed a robust shape interaction by preprocessing the data using robust PCA [21] and then applying LRR to build the similarity matrix. By combining the sparsity and global structure, Zhuang et al. [22], [23] proposed a nonnegative low-rank and sparse graph for semi-supervised learning. Fang et al. [24], [25] combined the nonnegative low-rank representation with the semi-supervised clustering learning within one framework achieving acceptable classification performance.

Conventional LRR based methods usually consider much on construction of the global subspace structure. However, a good graph should not only capture global structures of all the data but also reveal the intrinsic neighbor relationship among the data [26]. In this paper, we propose a Low Rank Representation with Adaptive Distance Penalty (LRRADP) method, which constructs the linear combination by using the nearby samples as much as possible via the adaptive distance penalty. The affinity graph built by the LRRADP can better both capture the global subspace structure of a whole data set and preserve local neighbor relationships among the data samples. The similarity graph/matrix identified by the LRRADP can work well with conventional semi-supervised classification method, such as Gaussian Fields and Harmonic Functions (GFHF) [8], for the label prediction of unlabeled samples. Moreover, the LRRADP is improved to LRRADP² by projecting the data set into an appropriate subspace.

The remainder of this paper is organized as follows. Section 2 introduces the related works of the low rank representation and semi-supervised subspace classification methods. Section 3 proposes an LRR with adaptive distance penalty method (LRRADP) for subspace classification. Section 4 extends the LRRADP to LRRADP² by projecting the data into an appropriate subspace. Section 5 presents the experimental results and Section 6 concludes this paper.