Robust Out-of-Sample Data Recovery

1 Introduction

Image recovery and reconstruction is an important research topic in computer vision and machine learning area. There exist many studies on image data recovery. One kind of popular methods is to use matrix factorization techniques [Lee and Seung, 1999; Duda et al., 2001; Aharon et al., 2006] which aim to learn an explicit low-rank recovery/representation for original high-dimensional data. In low-rank space, the noise can be suppressed and the class distribution becomes more apparent which significantly improves the machine learning results. In order to deal with gross errors or outliers, recent works use more robust matrix norms such as `1norm [Ke and Kanade, 2005; Kasiviswanathan et al., 2012; Peng et al., 2010; Zhao and Cham, 2011; Zhang et al., 2011; Feng et al., 2013; Yu et al., 2012], `21-norm [Ding et al., 2006; Kwak, 2008; Kong et al., 2011] to develop robust matrix factorization formulations which have been shown to be able to deal with gross errors or outliers effectively.

In additional to matrix factorization methods, trace norm based rank regularization approaches [Cai et al., 2010; Ma et al., 2009; Liu et al., 2010; Liu and Yan, 2011] have also been applied to reduce the rank of the data and thus can perform data recovery robustly. Among them, one of popular methods is Robust Principal Component Analysis (RPCA) [Wright et al., 2009a; Peng et al., 2010; Xu et al., 2012; Ma et al., 2009] which has been successfully applied in many problems such as data reconstruction, image denoising and background modeling, etc. Liu et al., [Liu et al., 2010] proposed a robust subspace segmentation and data recovery method based on Low Rank Representation (LRR). Liu and Yan [Liu and Yan, 2011] extend LRR to Latent Low Rank Representation (LatLRR) which uses both observed and unobserved hidden data and thus provides a more robust representation. Zhang et al., [Zhang et al., 2012] provided a matrix completion method via truncated nuclear norm regularization which can better approximate the matrix rank function. Recently, some other methods have also been proposed [Nie et al., 2014; Kim et al., 2015]. The above rank regularization methods can correctly recover underlying low-rank structure in the data, even in the presence of noise. One main advantage of these trace-norm based approaches is that the trace-norm is the convex envelop of matrix rank and thus the optimization is usually convex. A unique optimal solution exists.

However, one important issue for these trace norm recovery methods is how to do robust recovery for a new incoming 'query/test' sample, which we call out-of-sample data recovery. Since trace norm based methods are generally computed in a batch manner, i.e., they process the whole data set X0 simultaneously and thus can not naturally cope with the new incoming data. When a new query data x is added, one possible way is to re-compute the whole available data ¶x↪X0 ♦ simultaneously using traditional trace normmethods and then obtain the optimal recovery for the new data x. Obviously, this is computationally cost and also does not provide a prediction for the new data.

In this paper, we propose a new robust out-of-sample data recovery (ROSR) for trace norm based recovery methods. An effective iterative algorithm with the proof of convergence is presented to find the global optimal solution of the proposed ROSR problem. As an application, we apply our ROSR to face recognition and handwritten character recognition tasks. Experimental results on several datasets demonstrate the effectiveness and benefits of the proposed ROSR method.

2 Brief Review of LowRank Recovery

Let the input data matrix X = (x1↪ ▷▷▷↪ xn) 2 Rp⇥n contains the collection of n data vectors in p dimension space.

In image processing, each column xi is the linearized array of pixels gray levels. In many applications, the input data X usually contains noises, i.e., X = Z +E, where Z is the true signal data, and E is the sparse distortion. The aim of lowrank recovery is to find the optimal recovery Z by minimizing

where λ > 0 is a parameter and k · k` denotes the certain norms, such as Frobenius norm, `2↪1 and `1-norm. The explicit rank constraint rank(Z) is difficult to enforce in numerical computation. Many works suggest to use trace norm kZktr to approximate the rank constraint rank(Z). Thus, the above low-rank recovery becomes,

where kZktr = Tr(ZZ T )1◁2 . When k·k` denotes k·k1 norm, this model refers to robust PCA [Wright et al., 2009a; Cand`es et al., 2011] which has been shown robustly in dealing with corruption/sparse noise. When k · k` denotes k · k2↪1 norm, this model becomes to outlier pursuit model [Xu et al., 2012] which is better to pursuit the outliers in data recovery.

The above rank regularization methods can correctly recover underlying low-rank structure in the data, even in the presence of noise or outliers. Since trace norm is convex, the above optimization (Eq.(2)) is convex and a unique optimal solution exists.

3 Robust Out-of-Sample Recovery

Suppose we have obtained the optimal low-rank recovery Z 0 2 Rp⇥n from original observed data X0 2 Rp⇥n using the above RPCA model. Now, we consider a new query/test image data x 2 Rp⇥1 in original observed space, and wish to obtain its recovery/representation z in the low-rank space. Our aim in this paper is to seek a way to obtain z for x while fixing the already learned variable Z 0 . This can be formulated by solving the following model 1 ,

Since both X0 and Z 0 are fixed, this problem can be reduced as,

Using trace norm k · ktr replacement, this problem becomes

Let z⇤ be the optimal solution of model Eq.(5), then z⇤ can be regarded as a kind of recovery/reconstruction for the new query data x. In this paper, we call it Robust Out-of-Sample Recovery (ROSR). There is no new parameter in ROSR: β is set to the value when Z 0 are obtained.

Illustration. To illustrate the data recovery/reconstruction ability of ROSR model, we run ROSR on the occluded images selected from AT&T face dataset (more details are given in the Experiments section). Here, we select 8 images of each person for training and the rest 2 images for testing. Figure 1 (left) shows some examples of the occluded images X0 and corresponding low-rank reconstruction Z 0 of RPCA. Figure 1 (right) shows the occluded test image x and corresponding recovery z⇤ of ROSR. Each panel shows a test image with 3 different corruptions. Here we can note that large errors (occlusions) are suppressed in ROSR recovery. This clearly demonstrates the robust of ROSR method for out-of-sample data recovery.

1 Here we focus on `1. `2↪1 is similarly obtained.

4 Optimization

In this section, we derive an effective update algorithm to solve the proposed ROSR problem and provide the theoretical analysis on the convergence of the algorithm.

4.1 Computational algorithm

Given any initial z(0) , the algorithm updates the solution z(t) ↪ t = 1↪ 2▷▷▷ until convergence as summarized in Algorithm 1. Since the objective function of ROSR problem (Eq.(5)) is convex, thus staring from any initialization, the algorithm converges to the global optimal solution.

Algorithm 1 Robust Out-of-Sample Recovery

• 1: Input: Training data X0 ↪Z 0 2 Rp⇥n , query/test data x 2 Rp , parameters β, maximum number of iteration Tmax, and convergence tolerance ✏ > 0;
• 2: Initialize z(0) = 0↪ t = 0,
• 3: while t < Tmax or kz(t+1)-z(t) k2 kz(t) k2 > ✏ do
• 4: Compute w(t) and matrix B(t) as

• 5: Update z(t+1) as

where D(t) = diag(w(t)

• 6: end while

1 ↪w(t)

p ).

2 ↪ · · ·w(t)

• 7: Output: The converged recovery z⇤ = z(t+1) .

4.2 Convergence analysis

Let L(z) denote the objective function of ROSR problem Eq.(5). Since L(z) is a convex function of z, thus we only need to prove that the objective function value L(z) is nonincreasing in each iteration of Algorithm 1. This is summarized in Theorem 1.

Theorem 1 The objective function value L(z) of problem Eq.(5) is non-increasing,

along with each iteration of the update rule Eq.(8) in Algorithm 1.

To prove the Theorem 1, we need to prove the following three Lemmas firstly.

Lemma 2 For any matrices Y↪ Z with the same size, let A = (Y Y T )1◁2 ↪B = (ZZ T )1◁2 . Then, the following inequality holds,

The detail proof of this property can refer to the work [Luo et al., 2011].

Lemma 3 Define an auxiliary function

where B(t) = ([Z 0 ↪ z(t) ][Z 0 ↪ z(t) ]T )12 . Along with the ¶z(t) ↪ t = 0↪ 1↪ · · · ♦ sequence of the update rule Eq.(8) in Algorithm 1, the following inequality holds,

Proof Since the two terms in auxiliary function G(z) are semi-definite positive (SDP) problems, we can obtain the global optimal solution of G(z) by taking the derivatives and let them equal to zero.

Take the derivative of G(z) with respect to z, and we get

Let D(t) 2 Rp⇥p be the diagonal matrix with D(t) ii = w(t) i , then, Eq.(13) can be reformulated as follows,

Thus, we have

This completes the proof.

Lemma 4 The ¶z(t) ↪ t = 0↪ 1↪ 2↪ · · · ♦ sequence obtained by update rule Eq.(8) in Algorithm 1 has the following property,

Proof First, we rewrite problem Eq.(5) as,

Let ∆ = (L(z(t+1) ) - L(z(t) )) - (G(z(t+1) ) - G(z(t) ))▷ Then, substitute Eq.(17) and Eq.(11) in it, we obtain Eq.(18) can be rewritten as

According to Lemma 2, we have

where B(t) = ([Z 0 ↪ z(t) ][Z 0 ↪ z(t) ]T )1◁2 ▷ Substitute Eq.(20) into Eq.(19), we can have ∆  0. This completes the proof of Lemma 4.

From Lemma 3 and Lemma 4, we have,

which is to say

This completes the proof of Theorem 1.

Figure 2 shows the variation of objective function value L(z(t) ) across each iteration starting from random initialization. We can note that, as the iteration increases, the objective function L(z(t) ) decreases monotonously, demonstrating the convergence of the algorithm. As the iteration increases, the algorithm recoveries the true image more and more clearly. Also, the algorithm converges fast, generally in 20-30 iterations.

5 Experiments

5.1 Image recognition using ROSR

As an application for the proposed ROSR model, we have applied it to achieve face recognition and handwritten character recognition tasks. In short, the recognition process has the following two main steps.

In training phase, we obtain the low-rank recovery Z 0 from input data X0 using RPCA. In testing phase, for each test image x, we first obtain its ROSR recovery z⇤ and then identify it by K Nearest Neighbor (KNN) classifier or Sparse Representation Classification (SRC) [Wright et al., 2009b] methods. In KNN classification, the class identity of z⇤ is determined by its K nearest neighbors in Z 0 based on Euclidean distances. In SRC [Wright et al., 2009b] classification, we first compute the optimal coefficient ˆ↵ as

Then, we obtain the class identity of z⇤ as

where Z 0 i denotes the dataset of the i-th class, and ˆ↵i is the coding coefficient vector associated with the i-th class.

5.2 Datasets description

Six image datasets are used in the experiments, including three face datasets (AT&T face databases, Extended Yale Database B [Lee et al., 2005] and CMU-PIE [He et al., 2005a]) and three handwritten character datasets (Binary Alphabet Dataset 2 , MNIST handwritten digits Database, USPS Handwritten Digits Dataset 3 ). The details are introduced below and Table 1 summarizes them.

AT&T Faces Dataset contains 40 distinct persons with each person/class contains 10 different images. In our experiment, each face image was resized into 23⇥ 28 and reshaped into a vector of 644 dimension.

Extended Yale Database B consists of 38 different classes with each class contains about 64 frontal face images. In our experiment, each face image was resized into 28⇥32 and reshaped into a vector of 896 dimension.

CMU PIE face Database contains 68 different classes with 41368 face images as a whole. In our experiment, we randomly select 30 classes with each class containing 50 face images. Each face image was resized into 32 ⇥ 32 and reshaped into a 1024 dimension vector.

MNIST Hand-written Digit Dataset consists of 8-bit grayscale images of digits from "0" to "9", about 6000 examples of each class (digit). Each image is centered on a 28 ⇥ 28 grid. Here, we randomly select 100 images from each digit, and convert them to vectors of 784 dimension.

USPS Dataset contains 9298 handwritten digit images from "0" to "9". Each image is centered on a 16 ⇥ 16 grid. In our experiment, we select 1000 images (100 images for every digit) and convert them to vectors of 256 dimension.

Binary Alphabet Dataset contains 26 hand-written alphabets from A⇠Z with each alphabet consists 39 samples. Each sample is a 20 ⇥ 16 binary image. We reshape each image into one vector of 320 dimension.

2 http://olivier.chapelle.cc/ssl-book/benchmarks.html

3 http://www.cs.nyu.edu/ roweis/data.html

5.3 Results

To evaluate the robustness of our method, we conduct classification experiments on the corrupted images. Here, we randomly add corruptions on each image of the dataset, as shown in Figure 1. The percentage of corruption is about 10% of image size. All experiments are performed with ten-fold cross validation strategy, i.e., all data sets are randomly splitted into ten equal subsets, iteratively pick one subset for testing and the remaining nine subsets for training, then the performances are averaged over the ten loops.

For comparison, we compared our model with original raw data and other data recovery methods including standard Principal Component Analysis (PCA) [Duda et al., 2001], Locality Preserving Projection (LPP) [He et al., 2005a], Neighborhood Preserving Embedding (NPE) [He et al., 2005b] and L1-norm based PCA (L1PCA)[Ke and Kanade, 2005; Yu et al., 2012]. These compared methods can be used for out-of-sample data recovery or representation. For LPP and NPE, we first learn the optimal projection P 0 . Then, for a new query data x, we use P 0x as its representation. For L1PCA, we first learn the optimal U 0 from input data X0

Then, for a new query data x, we obtain its recovery as,

At last, we use U 0 v⇤ as the recovery for test image x, i.e.,

This is similar to PCA. We set the regularization parameter β in ROSR to 0▷8λ0, 1▷0λ0 and 1▷2λ0, respectively, where λ0 =

pp and p is the dimension of data. Note that λ = λ0 is used in RPCA model in the experiment. For PCA, LPP, NPE and L1PCA, we set the dimension d to 50 and 100, respectively.

Table 2 shows the comparison results of different recovery methods using KNN classification. We can observe that (1) L1PCA generally outperforms standard PCA, indicating the robustness of L1PCA recovery method. (2) ROSR performs better than L1PCA and gives the best classification results, which clearly demonstrates that ROSR can recover the noise images effectively and thus leads to better classification results. Figure 3 shows the comparison results of different recovery methods using SRC classification [Wright et al., 2009b]. Here, we perform SRC on the recovery images of different methods. We compare our ROSR method with original raw data, PCA and L1PCA method, because these methods can return a recovery for out-of-sample image, as shown in Eq.(25). We can note that our ROSR method obviously outperforms other methods, which further demonstrates the robustness of ROSR method on recovering the occluded images and thus leads to better recognition results.

6 Conclusions

This paper proposes a novel Robust Out-of-Sample Recovery (ROSR) method which conducts robust recovery for outof-sample data naturally based on trace norm regularization. An effective algorithm, with theoretical analysis on convergence, has been developed to solve ROSR problem. As an application, we apply our ROSR to image classification task. Experimental results demonstrate that ROSR is effective in recovering noise image data and thus obviously improves the classification results.

Acknowledgments

This work was supported by the National Key Basic Research Program of China (973 Program) (2015CB351705); National Nature Science Foundation of China (61472002); Co-Innovation Center for Information Supply & Assurance Technology, Anhui University; the Open Projects Program of National Laboratory of Pattern Recognition.