Similarity preserving low-rank representation for enhanced data representation and effective subspace learning

Abstract

Latent Low-Rank Representation (LatLRR) delivers robust and promising results for subspace recovery and feature extraction through mining the so-called hidden effects, but the locality of both similar principal and salient features cannot be preserved in the optimizations. To solve this issue for achieving enhanced performance, a boosted version of LatLRR, referred to as Regularized Low-Rank Representation (rLRR), is proposed through explicitly including an appropriate Laplacian regularization that can maximally preserve the similarity among local features. Resembling LatLRR, rLRR decomposes given data matrix from two directions by seeking a pair of low-rank matrices. But the similarities of principal and salient features can be effectively preserved by rLRR. As a result, the correlated features are well grouped and the robustness of representations is also enhanced. Based on the outputted bi-directional low-rank codes by rLRR, an unsupervised subspace learning framework termed Low-rank Similarity Preserving Projections (LSPP) is also derived for feature learning. The supervised extension of LSPP is also discussed for discriminant subspace learning. The validity of rLRR is examined by robust representation and decomposition of real images. Results demonstrated the superiority of our rLRR and LSPP in comparison to other related state-of-the-art algorithms.

Introduction

Low-rank subspace recovery and matrix decomposition have been attracting increasing attention and research interests in the communities of machine learning and computer vision (Beck and Teboulle, 2009, Candes et al., 2011, Fukushima and Mine, 1981, Lin et al., 2009, Liu, Jiao et al., 2013, Liu et al., 2012, Liu et al., 2013, Liu et al., 2010, Liu and Yan, 2011, Liu and Yan, 2012, Nesterov, 1983, Wright, Ganesh et al., 2009, Zhang, Yan, and Zhao et al., 2013a, Zhou et al., 2010), since low-rank matrices can often be observed in various real applications (such as face recognition Qiao, Chen, & Tan, 2010b; Wright, Yang, Sastry, & Ma, 2009, video surveillance Candes et al., 2011; Wright, Ganesh et al., 2009, handwriting representation Zhang, Liu, & Zhao, 2013 and system identification Chandrasekaran, Sanghavi, Parrilo, & Willsky, 2011) due to the fact that high-dimensional data usually lie in or lie near a low-dimensional subspace (Candes et al., 2011, Jolliffe, 1986). The classical Principal Component Analysis (PCA) (Jolliffe, 1986) and the recently emerged matrix recovery techniques (Candes et al., 2011, Lin, Chen et al., 2009, Liu et al., 2013, Liu et al., 2010, Wright, Ganesh et al., 2009) are essentially based on the assumption that the data of interests is approximately drawn from low-rank subspaces.

Robust PCA (RPCA) (Candes et al., 2011, Wright, Ganesh et al., 2009) is one most representative criterion for recovering low-rank matrices. Note that under much broader conditions, as long as the given observation matrix $X_O$ is corrupted by sufficiently sparse errors $E$, RPCA can exactly recover the low-rank $X_L(X_O=X_L+E_O)$ from $X_O=Y+E$ via a convex nuclear norm minimization problem (Candes et al., 2011). RPCA implicitly assumes that the samples are drawn from a single low-rank subspace (Liu et al., 2013), but most real datasets are usually described by a union of multiple subspaces, thus the recovery of RPCA may be inaccurate in reality (Liu et al., 2013). To address this issue, a more reasonable general model called Low-Rank Representation (LRR) (Liu et al., 2013, Liu et al., 2010) is proposed by considering the case that data are approximately drawn from several low-rank subspaces. Similar to Sparse Representation (SR) (Cheng et al., 2010, Qiao et al., 2010b, Wright, Yang et al., 2009, Zhang, Yan, and Zhao et al., 2013b, Zhang et al., 2013, Zhou et al., 2011), LRR computes the low-rank representation among all candidates that represent the row space of data vectors as a linear combination of basis in a dictionary (Liu et al., 2013, Liu et al., 2010), but differently LRR aims to learn the low-rank representation of all data vectors jointly by a convex problem. In addition, LRR has been proved to be a promising subspace recovery method, and is robust to noise and outliers, especially when the data sampling is sufficient and errors are properly bounded (Liu et al., 2013, Liu et al., 2010).

Note that LRR performs error correction and subspace recovery using the observed data matrix as dictionary, but insufficient and/or grossly corrupted observations usually put its effectiveness in jeopardy in practice. More specifically, if the sampling of $X_O$ is insufficient, the optimal solution $Z^{\ast }$ of LRR is the trivial identity matrix (Liu & Yan, 2011), which will be invalid for clustering samples. To improve LRR, an enhanced version of LRR, called Latent LRR (LatLRR) (Liu et al., 2013, Liu and Yan, 2011), was recently proposed for recovering the hidden effects through integrating certain latent observations that is capable of providing extra information for low-rank basis estimation. For subspace recovery, LatLRR constructs the dictionary using both observed and unobserved hidden data $X_H$, so LatLRR can resolve the insufficient sampling issue that may be suffered by LRR (i.e., the number of points is equal to or larger than the rank of union of subspaces) on condition that the dictionary is sufficient to represent the subspaces (Liu & Yan, 2011). It is also elaborated that the hidden effects can also be approximately recovered via a convex nuclear norm problem (Liu et al., 2013, Liu and Yan, 2011). Unlike LRR, LatLRR reconstructs given data from two directions, i.e., row and column. Based on such strategy, reconstructing along both row space and column space simultaneously can work complementarily when handling missing values, i.e., LatLRR is more robust to noise than LRR (Liu & Yan, 2011). But it is important to note that the so-called hidden effects brought to the problem by $X_H$ are unclear. More importantly, low-rank representation similarly aims to encode close features to similar reconstruction coefficients as SR does (Zheng et al., 2011), but LatLRR cannot guarantee such property due to the fact that it does not consider preserving such dependence relationships among features. As a result, close features may be encoded as dissimilar and even different reconstruction coefficients, even if the dictionary is sufficient to represent the subspaces. As observed from the low-rank representation by LatLRR for two similar faces in Fig. 3, the low-rank reconstruction coefficients of the two faces are encoded as dissimilar ones. But note that such deficiency may potentially weaken the robustness of LatLRR for low-rank subspace recovery in reality. In this paper, we mainly focus on addressing this problem to enhance performance and improve the robustness of LatLRR for matrix recovery and decomposition by endowing it the capability to preserve the similarities among local features in the reconstructive procedures.

The following highlights the major contributions of this work. First, a Regularized Low-Rank Representation (rLRR) framework formulated on LatLRR is technically proposed. A data-dependent Laplacian regularization term is added to the LatLRR criterion for preserving the similarity of local features in the reconstructive process. With the similarity effectively preserved by rLRR, local features can be well grouped in close vicinity of a dense region, reflected in the low-rank reconstruction coefficients. Thus, more discriminant low-rank coefficients and robust representations can be produced by rLRR. It should be noted that the idea of Laplacian regularization has been widely used in many machine learning studies, such as Cai, He, Han, and Huang (2011), Gao, Tsang, Chia, and Zhao (2010) and Zheng et al. (2011). Second, the proposed rLRR framework possesses all properties of LatLRR, including the capability of recovering the hidden effects from unobserved data and extracting informative features from new data. In addition, rLRR also learns two-directional low-rank coefficients to reconstruct given data, and the effects from both observed and hidden data can be approximately recovered by a convex nuclear norm minimization problem efficiently. Although LatLRR and our regularized extension can effectively do feature extraction by a linear transformation using the low-rank left-reconstruction matrix (Liu & Yan, 2011), this process cannot reduce the dimensionality of data. To this end, we in this paper also propose a Low-rank Similarity Preserving Projections (LSPP) framework for unsupervised subspace learning and feature learning. For effective subspace learning and feature learning, LSPP can explicitly preserve the similarity and locality among both principal and salient features in the encoding process in addition to computing an orthogonal projection matrix to convert high-dimensional data to a reduced feature space. The detailed computational issues of both rLRR and LSPP are also shown, and the bi-directional reconstruction coefficients delivered by LatLRR can also be embedded into our LSPP framework for dimensionality reduction and feature learning. In addition, we also mathematically show that LSPP can easily be extended to supervised scenarios to perform discriminant subspace learning under an orthogonal trace ratio criterion (Jia et al., 2009, Wang et al., 2007).

The paper is outlined as follows. In Section  2, we briefly review the LatLRR formulation and the Augmented Lagrange Multipliers (ALM) method. Section  3 proposes the rLRR framework mathematically. Subsequently, Section  4 describes the presented LSPP algorithm. We in Section  5 show the simulation settings and evaluate the proposed methods over real datasets. Finally, the concluding remarks are offered in Section  6.