{'fraction_non_alphanumeric': 0.03334133845661223, 'fraction_numerical': 0.010926993275696446, 'mean_word_length': 4.8746766988008465, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust Subspace Discovery by Block-diagonal Adaptive Locality-constrained Representation

We propose a novel and unsupervised representation learning model, i.e., Robust Block-Diagonal Adaptive Locality-constrained Latent Representation (rBDLR). rBDLR is able to recover multi-subspace structures and extract the adaptive locality-preserving salient features jointly. Leveraging on the Frobenius-norm based latent low-rank representation model, rBDLR jointly learns the coding coefficients and salient features, and improves the results by enhancing the robustness to outliers and errors in given data, preserving local information of salient features adaptively and ensuring the block-diagonal structures of the coefficients. To improve the robustness, we perform the latent representation and adaptive weighting in a recovered clean data space. To force the coefficients to be block-diagonal, we perform auto-weighting by minimizing the reconstruction error based on salient features, constrained using a block-diagonal regularizer. This ensures that a strict block-diagonal weight matrix can be obtained and salient features will possess the adaptive locality preserving ability. By minimizing the difference between the coefficient and weights matrices, we can obtain a block-diagonal coefficients matrix and it can also propagate and exchange useful information between salient features and coefficients. Extensive results demonstrate the superiority of rBDLR over other state-of-the-art methods.

To recover the low-rank subspace structures, Robust Principal Component Analysis (RPCA) [7] and Low-Rank Representation (LRR) [10] are two most representative models. Specifically, LRR and RPCA recover the underlying structures by decomposing data into a recovered low-rank part and a sparse error fitting the noise or corruptions. RPCA only assumes that the data points are drawn from a single low-rank subspace, while LRR studies a more general case that the samples are described using a union of multiple subspaces and the subspace segmentation problem is also considered. Because real-world data usually have the mixed subspace structures in practice, the recovery result of LRR will be potentially more accurate than that of RPCA.
Although RPCA and LRR can recover the subspace structures of data to some extent, they are essentially transductive methods. Thus, they both cannot handle new data efficiently and have to recalculate over all data again when a new sample comes, which will result in high cost. To enable the low-rank methods for joint salient feature extraction, some inductive algorithms have been proposed, such as Inductive Robust Principal Component Analysis (IRPCA) [8], Latent Low-Rank Representation (LatLRR) [16] and Joint Low-Rank and Sparse Principal Feature Coding (LSPFC) [18]. IRPCA addresses the out-of-sample issue by seeking a low-rank projection to extract the low-rank salient features directly, while LSPFC exploits the low-rank and sparse properties of samples jointly and obtains the joint low-rank and sparse salient features [18]. In contrast, LatLRR, as a combination of LRR and IRPCA, improves the performance by integrating latent observations to recover the hidden effects for low-rank basis estimation. More specifically, LatLRR defines the dictionary by employing both observed and unobserved hidden data, which can also resolve the suffered insufficient sampling issue suffered in LRR for more accurate low-rank representation.
Based on discovering the hidden effects, LatLRR has delivered the enhanced recovery and segmentation results, but it still suffers from several problems to degrade the performance and efficiency. First, LatLRR uses the Nuclear-norm to approximate the rank function for low-rank coding, but the Nuclear-norm based optimization involves the Singular Value Decomposition (SVD) of matrices, which is usually time-consuming especially for large-scale cases [19]. To improve the efficiency, Frobeniusnorm based Latent Low-Rank Representation (FLLRR) [19] was recently proposed, which approximates the rank function using the Frobenius-norm rather than Nuclear-norm. But regularizing the Frobenius-norm on projection and coefficients directly will be sensitive to noise and outliers in data, which may produce the inaccurate representations. Second, both LatLRR and FLLRR fail to encode and preserve the locality structures of samples, so the discovered subspaces may be inaccurate in reality. To preserve the locality structures, Laplacian Regularized LatLRR (rLRR) [17] was recently derived, which includes a data-dependent Laplacian regularization over coefficients and salient features into LatLRR. Note that rLRR pre-calculates a graph adjacency matrix from original data to encode the locality, but it cannot ensure the coefficients to be strictly block-diagonal, which is also suffered in LatLRR, and rLRR also suffers from the inefficiency issue due to the SVD process for solving the Nuclear-norm based problem. Moreover, the pre-obtained weights of rLRR cannot be ensured to be joint optimal for subsequent representation and also rLRR cannot ensure the graph Laplacian to be adaptive to different datasets by fixing the neighborhood size. Third, LatLRR, FLLRR and rLRR perform the representation learning in original space that usually contains various noise or even errors, therefore their discovered subspaces may not be accurate as well. The locality of rLRR is also encoded in original input space, which may cause inaccurate similarities due to the negative effects of noise.
In this paper, we mainly propose effective strategies to solve the above drawbacks for more efficient and enhanced subspace recovery. The major contributions are given as follows: (1) Technically, a novel and effective Robust Block-Diagonal Adaptive Locality-constrained Latent Representation model called rBDLR is proposed, which uses the Frobenius-norm for low-rank coding as FLLRR for the efficient representation by avoiding the SVD similarly. To recover the subspaces more accurately, rBDLR encodes the adaptive locality and compute the robust and strict block-diagonal representations. Specifically, the setting of rBDLR integrates the robust strict block-diagonal representation and adaptive locality-based salient feature extraction by robust autoweighting into a unified representation learning framework.
(2) To enable the coefficients to deliver strict block-diagonal structures for enhancing the representations, rBDLR performs the auto-weighting by minimizing the reconstruction error based on robust adaptive locality-constrained features, constrained by a block-diagonal regularizer over adaptive weights, motivated by Block-Diagonal Representation (BDR) [20]. Different from BDR, we did not use an arbitrary matrix for the representation matrix, but use the adaptive locality based regularizer to make the result interpretable, which can also encode the codes more accurately to characterize the subspace structures and pairwise similarities. The adaptive weighting selects the most compact samples to represent data, thus it can make the extracted salient features discriminative and adaptive to different subject classes although the learning manner is unsupervised. Then, rBDLR minimizes the approximation error between the adaptive weight matrix and codes so that the coefficient matrix can have a block-diagonal structure as well. Besides, such an operation can also propagate certain useful information between features and codes.
(3) To improve the robustness to noise and outliers in data, rBDLR performs the block-diagonal representation, salient local feature extraction and adaptive weighting in a recovered clean data space, inspired by the recent Robust LatLRR (rLatLRR) [26]. But rLatLRR only performs robust representation learning, which is different from rBDLR. In addition, rLatLRR suffers from the inefficiency issue as LatLRR, cannot preserve the locality of samples and ensure the block-diagonal structures of codes.
The paper is outlined as follows. Section 2 reviews the related work briefly. Section 3 presents rBDLR. Section 4 illustrates the connections between rBDLR and other methods. Section 5 shows the experimental results. Finally, Section 6 concludes the paper.

RELATED WORK
We briefly review the closely-related LatLRR, FLLRR and BDR.

LatLRR and FLLRR
Given a set of training samples   12 ,, x  is a sample represented by using an n-dimensional vector and N denotes the number of samples, LatLRR improves LRR using unobserved hidden data H X to extend the dictionary and overcome the insufficient sampling problem of LRR. Specifically, LatLRR considers the following low-rank coding problem: where   rank is the rank function and O X is the observed data. If O X and H X are all sampled from the same collection of lowrank subspaces, by using the Nuclear-norm to approximate the rank function and using L1-norm on the sparse error E, LatLRR can recover the hidden effects by minimizing , . .
where * Z is the Nuclear-norm of Z [16][17][21], i.e., the sum of its singular values, XZ and PX are principal features and salient features respectively, and  is a positive weighting factor.
Note that LatLRR uses the Nuclear-norm constraint on Z and P, so the time-consuming SVD process will be involved. Note that Frobenius-norm F can also be used as the convex surrogate of rank function [19]. Besides, the optimization of Frobenius-norm is more efficient compared with Nuclear-norm. The Frobeniusnorm based objective function of FLLRR is defined as

Block Diagonal Representation (BDR)
Existing LRR based methods [9][ [16][17][18] usually approximate the block-diagonal representation matrix by using different structure priors, such as sparsity and low-rankness, which are all indirect methods. BDR uses a block-diagonal matrix induced regularizer for pursuing a block-diagonal representation directly. Based on the block-diagonal regularizer, recent BDR solves the subspace clustering problem by using the block-diagonal structure prior in ideal case. The k-block diagonal regularizer is defined as where  , 1, denotes a column vector of all ones and B1 is the product between the matrix B and vector 1.
Based on the k-block diagonal regularizer, BDR considers the following problem for handling data with noise: where k is a k-block diagonal matrix based regularizer and the representation matrix B should be nonnegative and symmetric, which are necessary to define the block-diagonal regularizer. But the restrictions on B may limit its representation power, so BDR alleviates it by introducing an intermediate term The above problems in Eqs. (6) and (7) are equivalent as λ > 0 is sufficiently large. can make the problem for updating Z and B strongly convex and hence the solutions are unique and stable. But the matrix B is arbitrarily defined, which has no specific meanings. Although minimizing 2 F ZB  forces Z to deliver the block-diagonal structures by approximating it using B, the obtained Z may not be accurate to characterize the subspace structures and similarities, which may also cause the overfitting in reality, since the constraint 2 F ZB  is too strong and hard.

Objective Function
We introduce the formulation of rBDLR algorithm in this section. rBDLR mainly improves the representation ability from twofold. First, it defines a block-diagonal regularizer with clear definition and interpretability on the representation matrix so that the recovered subspaces are more accurate. Specifically, rBDLR first calculates an adaptive weight matrix W using the salient features PX by minimizing the reconstruction error over PX, and then uses it to define the representation matrix, which is different from BDR that applies an arbitrary matrix for the representation matrix. To avoid the overfitting issue and relax the constraint will contain some mixed signs and noise in W. Thus, the initial problem of rBDLR in noise-free case can be defined as (8) By imposing the block-diagonal constraint k on W, one can obtain a strict block-diagonal auto-weighting matrix W. By the minimization of 2 F PX PXW  , extracted salient features PX will have the adaptive locality preserving power, and moreover will be joint discriminative and adaptive to different subject classes although the learning process is unsupervised. By minimizing 2   T F WZ 1 , one can explicitly ensure the coefficient matrix Z to have block-diagonal structures. Note that W is obtained from the salient features PX, and both Z and PX are the low-rank coefficients and salient features of X respectively. Thus, Z and PX should share certain important local geometrical information. So, minimizing to make Z infinitely close to W will be reasonable. Besides, minimizing can also propagate some hidden information from salient features PX to coefficients Z, which can make the decomposition more accurate.
Since real application data often have various noise and errors, the obtained representation and weights may be inaccurate in reality. To tackle this issue, rBDLR considers the joint robust representation and weighting. Specifically, rBDLR first de-noises X by correcting errors similarly as [26] using L2,1-norm [21] and then performs representation and auto-weighting in a recovered clean space X-E, which leads to the following objective function: where   0 diag W  can avoid the trivial solution W=I, and A+ and A-are two auxiliary matrices that are defined as Note that the flow-diagram of our rBDLR is illustrated in Fig.1, where the relations of the recovered data, salient features and adaptive coefficients are shown clearly. The problem of rBDLR can be performed alternately between the following two steps: (1) Robust block-diagonal subspace discovery We first fix the block-diagonal representation matrix W for the robust subspace recovery and feature extraction. When W is known, we have the following problem from Eq. (9): , , .
(2) Adaptive locality based block-diagonal representation: When the projection P, representation coefficients Z and sparse error E are given, we can seek the block-diagonal representation matrix W from the following simplified problem: Next, we describe the optimization procedures of our rBDLR.

Optimization
It is easy to check from Eq.(9) that the involved variables depend on each other. Following the common procedures, we solve Eq.(9) by updating the variables alternately and use inexact Augmented Lagrange Multiplier method (ALM) [22] for efficiency. Let U be an auxiliary matrix, we first convert the problem into   . w.r.t.
Next, we will show the procedures of updating the variables.
where   2) Fix Z, P W,  , update E and U: By removing the terms irrelevant to E and U from Eq. (14), we have the following reduced formulation: According to [ After the sparse error 1 t E  is updated at each iteration, we can update the auxiliary matrix U by

3) Fix others, update the block-diagonal matrix W:
When the projection P, coefficients Z and error E are known, we can update the block-diagonal matrix W. By removing the terms irrelevant to W from Eq. (14), we have the following problem:  . (27) For the complete presentation of optimization, we summarize the procedures in Algorithm 1. About the convergence of rBDLR, firstly the convergence property of inexact ALM has been well studied as the number of blocks is at most two [7]. But it is still not easy to prove that the solution of models converge to global optimum theoretically when having over two blocks. We also approach our model by solving the blocks alternately, which are easily solvable at each iteration, similarly as IRPCA, LRR and LatLRR, etc. The time complexity of rBDLR is the same as that of FLLRR. The value of k in the k-block-diagonal regularizer is set to the number of subject classes in the following simulations.

RELATIONSHIP ANALYSIS
Connection between FLLRR and rBDLR. Recall the objective function of rBDLR in Eq. (9), if 0 =  , 0   , and the constraints on W are removed, we have the following reduced problem: (28) By comparing the above formulation with that of FLLRR in Eq.(3), the two problems are very similar in form. But note that although FLLRR and rBDLR can also obtain a coefficient matrix Z and a projection P, and correct the sparse error E in the data at the same time, their mechanisms are still different. Specifically, FLLRR clearly seeks Z and P from X, while rBDLR performs in the recovered space X-E. Thus, FLLRR is a special case of rBDLR.
By comparing the problems, we find that BDR minimizes the reconstruction error for learning Z, while rBDLR performs latent representation for jointly learning codes and adaptive localitypreserving salient features. Besides, BDR uses a hard constraint and defines a block-diagonal representation matrix as an arbitrary matrix, while rBDLR uses a flexible constraint and unifies the auto-weighting to calculate the interpretable adaptive weights for block-diagonal representation.

SIMULATION RESULTS AND ANALYSIS
We show the visual and quantitative comparison results of our rBDLR with those of several related algorithms, i.e., RPCA [7], LRR [10], IRPCA [8], I-LSPFC [18], rLRR [17], LatLRR [16], rLatLRR [26], FLLRR [19], BDR [20], Isoprojection (IsoP) [29] and Locality Preserving Projections (LPP) [28] for feature extraction and classification. Five public databases are evaluated, including two face recognition databases: UMIST [23] and AR [31], two object databases: COIL100 [24] and ETH80 [25], one handwriting database: USPS [27]. For data classification, samples are divided into a training set and a test set, where the training set is to learn a recovered subspace, and the test set is to evaluate the accuracy. Following the common practice, we resize all the face and object images into 32 32  pixels, which corresponds to a 1024-D data point in vector space. For fair comparison, all parameters of each method are chosen carefully. We perform all simulations on a PC with Intel (R) Core (TM) i7-7700 CPU @ 3.6 GHz 8G.

Investigation of Parameter Selections
Since the parameter selection is still an open problem, a heuristic way is to select the most important ones. ETH80 database is used and we use the features of [15]. The ETH80 database has 8 big categories. In each big category, 10 subcategories are included, each of which has 41 images. That is, it contains 3280 images of 80 objects. In this paper, we consider an eight-class categorization problem, i.e., each of the eight big categories is treated as a single class. We randomly select 4 images from each class as training set and test on the rest. rBDLR has three parameters, so we aim to fix one of them and explore the effects of other two by grid search. To see the effects of different parameters, we first fix =1  , then tune  and  by grid search from the candidate set  Fig.2(a), from which we find that rBDLR with -7 10 0.1   can deliver good results. Then we fix to observe the effects of  and  in Fig.2(b), from which we see that rBDLR with to investigate the effects of  and  in Fig.2(c), and we see that rBDLR also performs well in most cases. Note that similar findings are obtained from other datasets, thus we can simply select

Convergence Results
We present some convergence results of rBDLR on four image databases, i.e., UMIST, ETH80, COIL100 and USPS, as examples.
For each database, we select 10 images per class for training and the averaged convergence results over 10 splits are shown in Fig.3. We find that our rBDLR often converges with the number of iterations ranging from 30 to 80 in most cases.

Visual Image Analysis by Visualization
Visualization of coefficients Z. In this study, we follow [16] to construct 10 independent subspaces   ,, X X X X    by sampling 9 (that is smaller than the rank of subspace) data vectors from each subspace by ,1 9 data matrix. Then, we use this artificial data matrix for coding by LatLRR, FLLRR, BDR and rBDLR. The visualization results of coefficients are shown in Fig. 4. We find that: (1) the coefficients matrix Z of each algorithm have block-diagonal structures. But compared with those of BDR and our rBDLR, the coefficients of LatLRR and FLLRR in the off-diagonal are noisy and contains some wrong inter-class connections. Due to the deployment of a block-diagonal regularizer, a strict block-diagonal coefficients matrix Z is delivered for BDR and rBDLR, but the connectivity within each block of the codes of BDR is worse than rBDLR. This improvement can be attributed to the adaptive weighting with a block-diagonal regularizer to approximate the coefficients.
Visualization of recovered features XZ. We then evaluate rBDLR by visualizing the recovered faces XZ, that is, principal features. For a face data matrix X, rBDLR firstly de-noises it and decomposes it into the principal features XZ and salient features PX. In this study, AR database is used, since it has more facial variations, including illumination changes, face expressions, and occlusions by sunglasses and scarf. Random Gaussian noise with variance=500 is added into the face images to examine the robust properties of each method for face recovery. Some original faces, noisy faces and recovered features are shown in Fig.5. We see that the recovery process of rBDLR can remove the occlusions in the face images, and the recovered images of FLLRR, LatLRR, rLRR, BDR contain more noise than those of our rBDLR.  Table 1. We find that the result of each approach can be improved when       Recognition results on COIL100 database. We evaluate each method for object recognition under various numbers of training samples using COIL100. This database has 7200 images from 100 objects placed on a motorized turntable against a black background. We use the principal components features extracted by Principal Component Analysis (PCA) [30] and the dimension is 400. We train on 5, 10, 15 and 20 samples per object class and the recognition results are shown in Table 2. We find that rBDLR performs the best. Specifically, the superiority over the others is more obvious when the training size is relatively small.

Application to Image Recognition
Recognition results on ETH80 database. We evaluate each method for object recognition on the ETH80 object database. For object recognition, we randomly select 2, 4, 6 and 8 images from each category as training set and test on the rest. The averaged results of each algorithm over 10 runs are shown in Table 3. We find that: (1) the increasing number of training data improves the result of each method; (2) our rBDLR performs the best among all the compared methods, followed by rLRR and I-LSPFC.
Recognition results on USPS database. This digit database has 9298 handwritten digits ('0'-'9') and each sample is flattened to a 256 dimensional vector. We randomly select 10, 20, 30 and 40 images per class for training and test on the rest. We show the averaged results in Table 4. We find that rBDLR outperforms the other methods. FLLRR and rBDLR are comparable with each other and are superior to the other methods in most cases.

Image Recognition against Corruptions
We explore the robustness property of each method. UMIST and USPS databases are evaluated. To corrupt data, random Gaussian noise with the fixed variance is added. The number of training images per class is set to 10 for UMIST and USPS. The noisy recognition results are shown in Fig.7, where variance is set to 100, 200, … , 500, and some examples of noisy images are also illustrated. We find that: (1) the results are decreased when the noise level is increased; (2) our rBDLR delivers higher accuracies than other methods under different noise levels. Specifically, rBDLR degrades slower than other methods with the increasing of variance, which means that our rBDLR method is less sensitive to the noise and corruptions than other methods.

Quantitative Clustering Evaluations
We evaluate each method for clustering images. Two databases, i.e., UMIST face and USPS digits, are used. The clustering task is conducted by performing the K-means clustering algorithm with cosine distance on the recovered or reconstructed data of all the samples for each model. Specifically, for each fixed number K of clusters, we choose K categories from the dataset randomly and use K-category data to form the data matrix for representation learning. For each setting, the results are averaged based on 30 random initialization for K-means. Clustering accuracy (AC) and F-measure are used as evaluation metrics. The values of AC and F-measure on the two databases are described in Table 5 and 6. We find that: (1) generally speaking, the clustering accuracy of each model goes down as the number of categories increases, because clustering more data is usually difficult than clustering less. (2) rBDLR delivers better results than competitors, implying that rBDLR obtains effective data representations for clustering.