{'fraction_non_alphanumeric': 0.03139895742479869, 'fraction_numerical': 0.0064907405529299605, 'mean_word_length': 4.54952723998199, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Manifold Partition Discriminant Analysis

We propose a novel algorithm for supervised dimensionality reduction named Manifold Partition Discriminant Analysis (MPDA). It aims to find a linear embedding space where the within-class similarity is achieved along the direction that is consistent with the local variation of the data manifold, while nearby data belonging to different classes are well separated. By partitioning the data manifold into a number of linear subspaces and utilizing the first-order Taylor expansion, MPDA explicitly parameterizes the connections of tangent spaces and represents the data manifold in a piecewise manner. While graph Laplacian methods capture only the pairwise interaction between data points, our method capture both pairwise and higher order interactions (using regional consistency) between data points. This manifold representation can help to improve the measure of within-class similarity, which further leads to improved performance of dimensionality reduction. Experimental results on multiple real-world data sets demonstrate the effectiveness of the proposed method.


INTRODUCTION
Linear Discriminant Analysis (LDA) is a classical supervised dimensionality reduction method. It aims to find an optimal low-dimensional projection along which data points from different classes are far away from each other, while those belonging to the same class are as close as possible. In the resultant low-dimensional space, the performance of classifiers could be improved. Because of this, LDA is especially useful for classification tasks. Due to its effectiveness, LDA is widely employed in different applications such as face recognition and information retrieval [1], [2], [3], [4]. However, when the input data are multimodal or mainly characterized by their variances, LDA cannot perform very well. This is caused by the assumption implicitly adopted by LDA that data points belonging to each class are generated from multivariate Gaussian distributions with the same covariance matrix but different means. If data are formed by several separate clusters or lie on a manifold, this assumption is violated, and thus LDA obtains undesired results.
To solve this problem, some extensions of LDA have been proposed, which resort to discovering local data structures. Marginal Fisher Analysis (MFA) [5] [7] also focuses on discovering local data structures. It can be viewed as performing LDA on the local area around each data point. LFDA is a very effective algorithm and has many applications. Recently, LFDA (combined with PCA) was applied to the pedestrian reidentification problem and achieved the state-of-the-art performance [8]. Despite of different names and motivations, these methods, in fact, fall into the same graph Laplacian based framework. All of them employ the Laplacian matrix on specific graphs to characterize data structures locally, and share the same idea that if nearby examples x i , x j have the same class label y, they should be projected as close as possible, otherwise, they should be well separated. By exploiting the local structures around each data point, they are able to process the data on which LDA cannot achieve reasonable results. As widely recognized, graphs are often used as a proxy for the manifold. Therefore, these methods, to some extent, can be viewed as the combinations of manifold learning and LDA.
Although the above methods overcome the drawback of LDA, they rely on the graph Laplacian to capture the manifold structure, where only pairwise differences are considered whereas regional consistency is ignored. The regional consistency can be characterized by tangent spaces of the data manifold, which could be very useful to enhance the performance of discriminant analysis in some situations [9] [10]. Moreover, the definition of closeness of these graph Laplacian based methods is rather vague. Along which direction can we decide if the closeness of the mapped data points is achieved? We advocate that in order to preserve the manifold structure as much as possible, the closeness of the embeddings should be achieved along the direction that is consistent with the local variation of the data manifold.
During recent years, tangent space based methods have received considerable interest in the area of man-ifold learning [10], [11], [12], [13]. They utilize tangent spaces to estimate and extract the topological and geometrical structure of the underlying manifold. Local Tangent Space Alignment (LTSA) [11] constructs tangent spaces at each data point and then aligns them to obtain a global coordinate through minimizing the reconstruction error. Similar to LTSA, Manifold Charting [12] tries to unfold the manifold by aligning local charts. Tangent Space Intrinsic Manifold Regularization (TSIMR) [10] estimates a local linear function on the manifold which has constant manifold derivatives. Parallel Vector Field Embedding (PFE) [13] represents a function along the manifold from the perspective of vector fields and requires the vector field at each data point to be as parallel as possible. Due to exploiting the regional consistency reflected by tangent spaces, these tangent space based methods work well for representing the manifold structure. However, because of their unsupervised nature, they have no ability to capture the discriminative information from class labels, and thus are not optimal for supervised dimensionality reduction. Then how should we utilize the regional consistency of tangent spaces to improve the performance of supervised dimensionality reduction?
Besides the methods mentioned above, there are many other works that have been done in the field of dimensionality reduction. Supervised Local Subspace Learning (SL 2 ) [14] learns a mixture of local tangent spaces that are robust to under-sampled regions for continuous head pose estimation, so that it can avoid overfitting and be robust to noise. Linear Spherical Discriminant Analysis (LSDA) [15] performs discriminant analysis based on the cosine distance metric to improve speaker clustering performance. By building a sparse projection matrix for dimension reduction, Double Shrinking Algorithm (DSA) [16] compresses image data on both dimensionality and cardinality to obtain better embedding or classification performance. Least-Squares Dimension Reduction (LSDR) [17] adopts a squared-loss variant of mutual information as a dependency measure to perform sufficient dimensionality reduction. Wang et al. proposed an exponential framework for dimensionality reduction [18]. By using matrix exponential to measure data similarity, this framework emphasizes small distance pairs, and can avoid the small sample size problem. Although all of these methods have their own merits, none of them solves the above mentioned two problems.
In this paper, we propose a novel supervised dimensionality reduction method called Manifold Partition Discriminant Analysis (MPDA), which solves the above two problems. In MPDA, pairwise differences and piecewise regional consistency are considered simultaneously, so that the manifold structure can be well preserved. MPDA aims to find a linear embedding space where the within-class similarity is achieved along the direction that is consistent with the local variation of the data manifold, while nearby data belonging to different classes are well separated. Compared with existing methods, MPDA has several desirable properties that should be highlighted: • MPDA partitions the data manifold into a number of non-overlapping linear subspaces and discovers regional manifold structures in a piecewise manner. • With the partitioned manifold, MPDA is able to construct tangent spaces with varied numbers of dimensions. This provides MPDA with more flexibility to handle non-uniformly distributed or complex data. • By using the first-order Taylor expansion, MPDA establishes a manifold representation which is characterized by both the pairwise differences and piecewise regional consistency of the underlying manifold. • Thanks to the proposed manifold representation, MPDA improves the measure of within-class similarity, and is able to obtain a projection that is consistent with the local variation of the underlying manifold. The rest of this paper is organized as follows. In Section 2, we briefly introduce the graph Laplacian based framework, under which many supervised dimensionality reduction methods can be considered within the same category. Then the Manifold Partition Discriminant Analysis (MPDA) algorithm is presented in Section 3. Section 4 discusses the connection and difference between MPDA and related works. In Section 5, MPDA is tested on multiple real-world data sets compared with existing supervised dimensionality reduction algorithms. Finally, we give concluding remarks in Section 6.

GRAPH LAPLACIAN BASED FRAMEWORK FOR DISCRIMINANT ANALYSIS
Representing data on a specific graph is a popular way to characterize the relationships among data points. Given an undirected weighted G = {X, W } with a vertex set X and a symmetric weight matrix W ∈ R n×n , these relationships can be easily characterized by G, where each example serves as a vertex of G, and W records the weight on the edge of each pair of vertices. Generally, if two examples x i and x j are "close", the corresponding weight W ij is large, whereas if they are "far away", then the W ij is small. Provided a certain W , the intrinsic geometry of graph G can be represented by the Laplacian matrix [19], which is defined as where D is a diagonal matrix with the i-th diagonal element being D ii = j =i W ij . The Laplacian matrix is capable of representing certain geometry of data according to a specific weight matrix. This property is very helpful for developing dimensionality reduction methods.
Let X be a data set consisting of n examples and labels, example, y i ∈ {1, 2, . . . , C} denotes the class label corresponding to x i , and C is the total number of classes. Classical LDA aims to find an optimal linear projection t along which the between-class scatter is maximized and the within-class scatter is minimized [20]. The objective function of LDA can be written as: where ⊤ denotes the transpose of a matrix or a vector, S b and S w denote the between-class and within-class scatter matrices, respectively. The definitions of S b and S w are given as follows: where n c is the number of data from the c-th class, µ = 1 n n i=1 x i is the mean of all the data points, and µ c = 1 nc {i|yi=c} x i is the mean of the data from class c. Apart from the above formulations, S b and S w can also be formulated via the graph Laplacian [7]: where L w and L b are the Laplacian matrices constructed by the weight matrices W w and W b with The objective function (2) can be converted to a generalized eigenvalue problem: whose solution can be easily given by the eigenvector with respect to the largest eigenvalue. From the above formulations, it is clear that the graph Laplacian plays a key role in deriving LDA, where the weight matrices W b and W w measure the similarity of each pair of data points, and their characteristics varies as the criterion of similarity changes. This provides a general and flexible framework to develop new dimensionality reduction algorithms by constructing appropriate Laplacian matrices.
In order to improve the performance of LDA, many local structure based extensions of LDA have been proposed in the recent decades. Representative methods include Marginal Fisher Analysis (MFA) [5], Locality Sensitive Discriminant Analysis (LSDA) [6], Local Fisher Discriminant Analysis (LFDA) [7], etc. Unlike traditional LDA, they compute the between-class and within-class scatter based on local data structures rather than the global mean values. Although these methods improve the performance of discriminant analysis by solving the problem caused by the improper assumption adopted by LDA, none of them extends beyond the graph Laplacian based framework. Their differences merely lie in the different ways of constructing the Laplacian matrices L b and L w .
In spite of its effectiveness, the graph Laplacian based framework still has several limitations. The betweenclass and within-class scatter are computed by only aggregating all pairwise differences between data points across the entire graph, whereas the regional consistency, which is reflected by the regional structure around a local area of the underlying manifold, is ignored. Moreover, by minimizing the aggregation of within-class data pairs (6), the objective function (2) tends to find a direction along which some "averaged" within-class similarity is achieved. However, it is unclear that how the "averaged" similarity can precisely reflect the topological and geometrical structure of the underlying manifold.

MANIFOLD PARTITION DISCRIMINANT ANALYSIS
In this section, we propose a novel supervised dimensionality reduction algorithm named Manifold Partition Discriminant Analysis (MPDA). Unlike previous methods that mainly rely on the graph Laplacian [5], [6], [7], MPDA exploits both pairwise differences and piecewise regional consistency to preserve the manifold structure. It aims to find a linear embedding space where the within-class similarity is achieved along the direction that is consistent with the local variation of the data manifold, while nearby data belonging to different classes are well separated. To this end, we first need to extract the piecewise consistency from the data manifold, which can be achieved by partitioning the data manifold into non-overlapping pieces, and estimating tangent spaces for each piece. Then we can represent the data manifold by combining pairwise differences with piecewise consistency. The resultant manifold representation is able to characterize the local variation of the data manifold, and improve the measure of within-class similarity, which eventually leads to the MPDA algorithm. Specifically, we mainly solve the following problems: P1 How to partition the data manifold into a number of non-overlapping pieces, and estimate an accurate tangent space? P2 How to combine pairwise differences with piecewise regional consistency in representing the data manifold? P3 How to find a linear subspace where the withinclass similarity is achieved along the direction that is consistent with the local variation of the data manifold?
Next, we first solve P2 and P3 in Section 3.1 and 3.2, respectively, and defer the treatment of P1 to Section 3.3.

Manifold Representation
In order to combine pairwise differences with piecewise regional consistency in representing the data manifold, we are interested in estimating a function f defined on an m-dimensional smooth manifold M, where M is embedded in R d . This function f can serve as a direct connection between the data representation in d and mdimensional spaces. For simplicity, we first consider to represent data in a one-dimensional Euclidean space R.
According to the first-order Taylor expansion at x 0 , f can be expressed as follows [10], [13], [21]: is a matrix formed by the orthonormal bases of T x0 M, and characterizes the regional consistency of the manifold structure around x 0 . Generally, T x0 can be estimated by performing PCA on the neighborhood of x 0 [11], [22]. v x0 is an m-dimensional tangent vector and represents the manifold derivative of f at x 0 with respect to u x0 (x), which reflects the local variation of the manifold at x 0 .
Given two nearby data points z and z ′ lying on the manifold M, we can use the first-order Taylor expansion at z ′ to express f (z) as follows: If M is smooth enough, the second-order derivatives of f tend to vanish. Furthermore, when z and z ′ are close to each other, z − z ′ 2 becomes very small. Therefore, the remainder in (8) can be omitted, which leads to: With the above results, it is clear that for any nearby data points z and z ′ lying on the manifold M, the lowdimensional embeddings f (z) and f (z ′ ) should satisfy (9), and the difference between both sides of (9) should be as small as possible. This can serve as a good criterion to preserve the manifold structure, which establishes the connection between each pair of nearby data points. Assume that the data manifold can be well approximated by the union of a number of non-overlapping linear subspaces. In this case, each linear subspace can serve as a tangent space, and each tangent space has a tangent vector. With the partitioned manifold, we are able to construct tangent spaces and tangent vectors for each linear subspace rather than each data point. If z ′ lies in a tangent space T p M with a tangent vector v p , (9) becomes: where T p is estimated by performing PCA on the data falling into T p M. This can be justified by the fact that the manifold derivative of a linear subspace is a constant function. This means that for the data falling into the same linear subspace, their corresponding tangent vectors are equal, and can be represented by only one tangent vector v p . It is worth noting that since PCA entails mean subtraction, each tangent space estimated by PCA will have a separate mean. This seems to cause the discrepancy of tangent spaces. However, this discrepancy is not a problem in our case. Once the orthonormal basis T p has been estimated, the effect of mean subtraction is just to center data to the origin of the corresponding subspace. Notice that only the data falling into T p M or those around T p M are involved in the projection of T p . These data points implicitly reflect the mean of the corresponding subspace. Therefore, we can directly use the orthonormal basis T p to compute the projection without mean subtraction. Figure 1 illustrates the concept of the above strategy (we call it the manifold partition). Intuitively, after partitioning the manifold, M is approximated by the union of the linear subspaces, where each linear subspace serves as a tangent space. Therefore, (10) combines pairwise differences with piecewise regional consistency in representing the data manifold.

The MPDA Algorithm
Based on the above results, we propose our MPDA algorithm. Consider a data set X = {(x i , y i )} n i=1 belonging to C classes where x i ∈ R d and y i ∈ {1, 2, . . . , C} is the class label associated with the data point x i . Generally, we assume that data in different classes are generated from different manifolds. Provided that X = {x 1 , . . . , x n } = P p=1 X p has been partitioned into P patches, where data of each patch have the same class label, and we have obtained the orthonormal basis matrices {T p } P p=1 of tangent spaces for each data patch. Our goal is to find an embedding space where the within-class similarity is achieved along the direction that is consistent with the local variation of the data manifold, while nearby data belonging to different classes are well separated.
In order to gather within-class data based on the manifold structure, we first construct the within-class graph G = {X, W } to represent the geometry of the data manifold. If x i is among the k-nearest neighbors of x j with y i = y j , an edge connecting x i to x j is added with the weight W ij = W ji = 1. If there is no edge connecting x i to x j , W ij = 0. With the results in Section 3.1, for each pair of nearby within-class data points, we can obtain: We require the difference between both sides of (11) to be as small as possible. In the scenario of linear dimensionality reduction, f (x) represents a one-dimensional embedding of x, and we aim to find a linear projection.
To this end, f (x) is further approximated as a linear function f (x) = t ⊤ x where t ∈ R d is a linear projection vector. Then, if nearby data points x i , x j belong to the same class, we can measure their similarity as follows: where π i ∈ {1, . . . , P } is an index indicating the patch x i belongs to. Moreover, we also need to measure the similarity between nearby tangent spaces. By substituting (11) into (12), we have: From the above equation, we know that the two vectors are approximately perpendicular or the row vector (T πj v πj −T πi v πi ) ⊤ approximately equals to a zero vector. However, the perpendicular case can not be satisfied for every pair of nearby data points on the manifold. For instance, consider there are three nearby data points on the manifold. Each pair of them should satisfy the above equation, while only two of them are, in general, justified in the perpendicular case. On the other side, the case of zero row vectors can be justified for all the data pairs, and leads to T πj v πj ≈ T πi v πi . Finally, by multiplying both sides of this equation with T ⊤ πi and using T ⊤ πi T πi = I, it follows that: It is clear that for each pair of nearby tangent spaces the difference between both sides of (14) should be as small as possible. Therefore, the similarity between nearby tangent spaces can be measured as follows: With the above results, the data manifold with respect to each class can be estimated by relating data with a discrete weight W ij , which leads to an objective function as follows: where γ is a trade-off parameter controlling the influence between (13) and (15). It is clear that if x i and x j belong to the same class and fall into the same tangent space, their similarity only depends on their pairwise difference. If x i and x j belong to the same class but lie in different tangent spaces, apart from the pairwise difference, their similarity also depends on the angle between v πj and T ⊤ πj (x i − x j ), which means that x i and x j can be viewed as similar data points when v πj and Since v πj reflects the varying direction of the data manifold around x j , by optimizing (16), we can deem that the within-class similarity is achieved along the direction that is consistent with the local variation of the data manifold.
It is worth noting that the above derivation is based on the first-order Taylor expansion of the function f . If we employ the zero-order Taylor expansion, the terms related to v πi (i = 1, . . . , n) vanish. Then the objective function is simplified as follows: where L = D − W is the Laplacian matrix and D is a diagonal matrix with the i-th diagonal element being D ii = j =i W ij . This formulation is identical to the graph Laplacian based within-class scatter (6). From the aspect of manifold approximations, this means that in theory the proposed method is able to approximate the underlying manifold with a smaller approximation error O(||x i − x j || 2 ) than the graph Laplacian whose approximation error is O(||x i − x j ||). Compared with (16), the graph Laplacian based scatter fails to consider the regional consistency that is explicitly parameterized by the proposed manifold representation. Although it can implicitly reflect regional relationships by minimizing the distance between each pair of nearby data points, the graph Laplacian has no ability to capture the regional consistency which is determined by all the nearby data around a given data point. On the other hand, the proposed manifold representation is capable of preserving both the pairwise geometry and the piecewise regional consistency, and thus can capture more structural information from the data manifold than the graph Laplacian. In other word, (16) better measures the within-class similarity than the graph Laplacian based scatter (6), because it can extract the regional consistency of each tangent space, and explicitly establishes the connections among tangent spaces by estimating tangent vectors {v p } P p=1 . Notice that although we assume that the data manifold can be approximated by a union of piece-wise subspaces, it does not mean that the proposed manifold representation is inferior to the graph Laplacian. To verify this, we can split the within-class objective function (16) into two parts. The first part includes the terms related to v, and the second part has the other terms. The piece-wise manifold assumption only affects the first part, while the second part is still based on the generic manifold assumption. In fact, the second part of (16) is just identical to the graph Laplacian based withinclass scatter. This implies that the proposed manifold representation is at least as good as, if not better than, the graph Laplacian, as each tangent vector v πi can be a zero vector.
To separate data in different classes, we construct a between-class graph G ′ = {X, W ′ }. If y i = y j , we add an edge between x i and x j with the weight W ′ ij = 1/n. If y i = y j , the corresponding weight is set to be W ′ ij = A ij (1/n−1/n c ). n c is the number of data points from the c-th class, and A ij is a weight that indicates the similarity between x i and x j , whose definition is given as follows: where N k (i) denotes the k-nearest neighbor set of x i , and σ i is heuristically set to be the distance between x i and its k-th nearest neighbor. Then we can formulate the following objective function to separate nearby betweenclass data points: The methods for constructing G ′ have been well studied in the literature [5], [6]. Here, we employed the one in [7] because of its effectiveness in enhancing the betweenclass separability.
It is easy to see that (16) can be reformulated as a canonical matrix quadratic as Due to the space limitation, the detailed derivation of S is provided in the supplementary material, which is a modification of the derivation of a similar quantity used in [10]. By simple algebra formulations, (17) can where L ′ is the Laplacian matrix constructed by W ′ . In order to preserve the manifold structure while separating nearby between-class data points, we can optimize the objective functions (16) and (17) simultaneously, which leads to the following objective function: arg max where we have defined f = (t ⊤ , v ⊤ ) ⊤ , and the Tikhonov regularizer with a trade-off parameter α has been employed to avoid the numerical singularity of S. Trade-off parameters γ (γ > 0). Output: d × r transformation matrix T .
Apply certain method to partition the data in each class into a total of P patches {X p } P p=1 ; for p = 1 to P do Construct T p by performing PCA on X p ; end for Construct the within-class graph G and the betweenclass graph G ′ ; Compute the eigenvectors f 1 , f 2 , . . . , f m of (19) with respect to the top m eigenvalues; T = (t 1 , t 2 , . . . , t m ).
The optimization of (18) is achieved by solving a generalized eigenvalue problem: whose solution is the eigenvector f * = (t * ⊤ , v * ⊤ ) ⊤ with respect to the largest eigenvalue. Then we can use the first part of f * to obtain a one-dimensional embedding of any x ∈ R d by computing b = t * ⊤ x. If we want to project x into an m-dimensional subspace, we can just compute m eigenvectors f 1 , . . . , f m corresponding to the m largest eigenvalues of (19). Then the m-dimensional embedding b of x is computed as b = T ⊤ x, where T = (t 1 , . . . , t m ). Algorithm 1 gives the pseudo-code for MPDA.

Partitioning the Manifold
In this section, we propose a manifold partition algorithm to solve the last problem (P1). Since tangent spaces are linear subspaces in essence, the better the data manifold can be linearly approximated by the partitioned pieces, the more accurately the resultant tangent spaces can reflect the regional consistency of the underlying manifold. In order to estimate tangent spaces which approximately lie on the manifold surface, we first need to introduce a criterion to measure the linearity of subspaces.
Given a data set X as well as its pairwise Euclidean distance matrix D E and geodesic distance matrix D G (approximated by the shortest path algorithms such as Dijkstra's algorithm), we can measure the degree of linearity between two data points x i and x j by computing the ratio R ij = D G ij /D E ij , which is also referred to as the tortuosity [23]. D E ij is the Euclidean distance between x i and x j , and D G ij is their geodesic distance. It is clear that D G ij is never smaller than D E ij . If D G ij ≈ D E ij , then R ij ≈ 1 and we can deem that x i and x j lie on a straight line.
When it comes to a data patch X p , we can measure its linearity as follows: where N p denotes the number of data in X p . It is clear that the smaller R p is, the better the data in X p fit a linear subspace.
With the above measure of linearity, we can partition the manifold by hierarchical clustering [24]. There are mainly two branches of hierarchical clustering depending on their search strategies. In this paper, we use the top-down hierarchical divisive clustering rather than the bottom-up hierarchical agglomerative clustering because of two reasons. For one thing, if we need to partition the data set into P patches, as P is usually much smaller than the number of data points, top-down methods are more efficient than bottom-up ones. For another, topdown methods tend to construct patches with the same or similar sizes. As a result, the tangent spaces estimated by these patches tend to have similar dimensionalities, which fits the manifold assumption better. Specifically, given a data set X = {x 1 , . . . , x N }, our top-down partition algorithm aims to partition X into a number of patches (subsets) until there is no patch (subset) containing more than M data points, which consists of the following steps: Compute the Euclidean distance matrix D E , the geodesic distance matrix D G (approximated by the shortest path algorithms such as Dijkstra's algorithm), and the patch linearity R 1 according to (20). 2) From {X p } P p=1 , select the patch X p (p ∈ 1, . . . , P ) having the highest value of R p · N p . From X p , select two data points x l and x r having the largest geodesic distance D G lr . Create two new patches X p l = {x l } and X p r = {x r }. Update X p ← X p \ {x l , x r }.
3) Construct the k ′ -nearest neighbor sets of X p l and X p r denoted by N p l and N p r , respectively. Construct the joint neighbor set N p . 5) Compute the patch linearity R p l and R p r for X p l and X p r , respectively. Let N l and N r be the number of data in X p l and X p r . If R p l · N l > R p r · N r , update X p r ← X p r ∪ N p joint , or update X p l ← X p l ∪ N p joint otherwise. Repeat steps 3) ∼ 5) until X p = ∅. 6) X p has been partitioned into X p l and X p r . Update P ← P + 1, X p ← X p l , X P ← X p r . Go to step 2), until there is no patch having N p > M , where M is the maximum patch size. Generally, in order to obtain the patch in which data lie in a linear subspace, we should divide the patch with the largest R p in each turn of partition. In our algorithm, we combine the patch linearity R p and its size N p together to select the patch that should be further divided, because the scope of subspaces should be small enough so that the Taylor expansion in (11) and (12) can be justified. Two parameters in the proposed partition algorithm should be determined, i.e., the neighborhood size k ′ and the maximum patch size M . It is worth noting that to estimate tangent spaces accurately, each patch should satisfy two competing requirements. On the one hand, we should keep sufficient data in each patch so that the tangent space can be well estimated. On the other hand, the patch should be small enough to preserve the local manifold structure. Therefore, we use M rather than the number of subspaces P as the threshold to control the termination of the algorithm.
Besides extracting the piecewise regional consistency, partitioning the manifold can provide additional benefits. It is clear that an accurate estimation of tangent spaces is crucial for tangent space based methods. Usually, tangent spaces are estimated by performing PCA on the k-nearest neighbors of each data point. This approach fixes the neighborhood size, which may fail to estimate the correct tangent spaces when data are sampled nonuniformly or the manifold has a varying curvature. In contrast, the proposed MPDA method is more likely to get a robust estimation, because PCA is performed on the data in each linear subspace where data naturally lie on the manifold surface. Figure 2 shows an example that performing PCA on the fixed-sized neighborhood fails to capture the correct tangent space. As can be seen, T p M and T p ′ M reflect the correct manifold structure, whereas T z M computed by z and its two-nearest neighbors is incorrect. In addition, real data are often complex whose underlying manifold dimensionality could vary at different regions. Therefore, it would be better to adjust the manifold dimensionality for different parts of the manifold instead of setting a fixed one. As the number of data varies in each linear subspace, MPDA adaptively determines the number of dimensions of each linear subspace by simply employing PCA to preserve certain percentages of energy, say 95%. This provides MPDA with more flexibility to handle complex data in practice.

Pairwise-variate MPDA
For now, we have presented the MPDA algorithm which considers both preserving the manifold structure and distinguishing data from different classes. Since the data manifold is partitioned into a number of nonoverlapping tangent spaces, MPDA discovers the regional consistency of the data manifold in a piecewise manner, where the manifold partition strategy plays a key role in deriving MPDA. If we relax the piece-wise manifold assumption to the general one, and directly derive the proposed method from (9) rather than (10) without partitioning the manifold, we can obtain a Pairwise-variate MPDA (PMPDA). Then, the objective function (16) becomes: where the orthonormal basis matrix T xi is computed by performing PCA on the k-nearest within-class neighbors of x i . Similar to (16), (21) can also be reformulated as a quadratic form The rest steps of PMPDA are just the same as MPDA except that S is replaced by S p . Finally, PMPDA solves the following generalized eigenvalue problem: Compared with MPDA, PMPDA no longer needs to partition the manifold, but has to estimate tangent vectors and tangent spaces for each data point, while MPDA estimates only P of them. On the one hand, PMPDA is more effective to preserve the manifold geometry, because it is based on a more general manifold assumption. On the other hand, PMPDA has to determine tangent vectors and construct tangent spaces at each data point, which not only leads to tremendous computational overheads, but results in severe storage problems when it is performed on large data sets. Consequently, PMPDA can only be performed on small data sets and is hardly practical. In brief, PMPDA is able to make a better manifold estimation at the expense of its efficiency, and the strategy of partitioning the manifold can be viewed as a trade-off between effectiveness and efficiency of the manifold estimation. Like PMPDA, some tangent space based methods such as TSIMR [10] and PFE [13] also suffer from similar computational and storage problems. This implies that although the manifold partition strategy is a crucial part of MPDA, we can also apply it to the tangent space based methods to make them more efficient. We provide some preliminary results in the supplementary material.

Time Complexity
In this section, we briefly analyze the computational complexity of both PMPDA and MPDA. The main computational costs of PMPDA lie in building tangent spaces for n data points and solving the generalized eigenvalue problem. PMPDA takes O((d 2 k +k 2 d)×n) for estimating n tangent spaces by performing PCA on the k-nearest neighborhood of each data point. Note that we can obtain at most k meaningful orthonormal bases for each tangent space, since there are only k+1 data points as the inputs of PCA. Therefore, the dimensionalities of tangent vectors and tangent spaces are at most k. This means that PMPDA takes O((d + kn) 3 ) for solving the generalized eigenvalue problem (22).
MPDA first partitions the manifold into P linear subspaces, whose time complexity is dominated by computing the geodesic distance matrix D G and the hierarchical divisive clustering for data in each class. Computing D G based on a k ′ -NN graph by the Dijkstra's algorithm with Fibonacci heaps takes O(n 2 log n+k ′ n 2 /2). The computational complexity of the hierarchical divisive clustering can be approximated as O( where n c is the number of data in the c-th class, and P c is the number of patches partitioned from the data in the c-th class with With the above results, we can find that the most consuming parts of PMPDA and MPDA lie in the generalized eigenvalue decomposition. PMPDA needs to decompose S p , a large matrix sized (d + mn) × (d + mn), which will takes O((d + kn) 3 ). Compared with PMPDA, MPDA manipulates a much smaller matrix S sized (d + mP ) × (d + mP ) and only needs to estimate P tangent spaces rather than n. Since P ≪ n, this leads to significant computational savings.

Further Improvement
Based on the above analysis, it is clear that MPDA avoids both computing tangent spaces for every data point and solving the eigenvalue problem with a large matrix, so that it have less computational complexity. In fact, we can make it more scalable. Note that we use the product R p · N p to determine the patch that should be further divided and the manner that how this patch is divided, where N p is predominant to control our partition algorithm. When the number of data is very large, we can deem that the Euclidean distance is approximately equal to the geodesic distance within a small region, which leads to R p ≈ 1. Therefore, the partition algorithm can be simplified by omitting the computation of D G and R p , so that we can save the time for performing Dijkstra's algorithm and computing R p .
In addition, the computational costs of MPDA can be reduced by estimating tangent vectors and tangent spaces only at anchor points. In this case, we are interested in selecting a portion of points from the original data set as the anchor points, and the rest can be represented according to the first-order Taylor expansion at their nearest anchor points. Therefore, the data manifold can be estimated by using the anchor points only. It is natural to specify the center of each linear subspaces, which is not necessary a data point among the training set, as the anchor point. As a result, MPDA can be performed on only P anchor points rather than the whole data set, such that the corresponding computational complexity for solving the generalized eigenvalue problem can be reduced to O((d + P ) 3 ).
Moreover, the two-stage strategy [25] can be adopted to further reduce the computational costs. We can separate the generalized eigenvalue problem (19) into two stages. The first stage maximizes (17) via QR decomposition to find its solution space. The second one solves (19) in the solution space of (17). Since S ′ is just the extension of 2XL ′ X ⊤ , the rank of S ′ is at most d. Consequently, the time for solving (19) can be reduced to O(d 3 ). Please refer to [25] for more details.

DISCUSSION
Several works have been done to manipulate data in local subspaces for dimensionality reduction [26], [27], [28], [29]. Basically, they share the same spirit in aligning local subspaces to build a global coordinate, where the connections of local subspaces are considered implicitly. The main difference between MPDA and these methods is that MPDA constructs tangent spaces in a piecewise manner and explicitly characterizes their connections by estimating tangent vectors.
Local Linear Coordination (LLC) [26] and Coordinated Factor Analysis (CFA) [27] construct linear subspaces through the mixture of factor analyzers (MFA) which can serve as an alternative way to partition the data manifold. However, MFA is optimized by the expectationmaximization (EM) algorithm, which can be slow and unstable. Moreover, the number of factor analyzers and the dimensionality of each linear subspace should be specified as a priori knowledge, which are difficult to determine. In contrast, the proposed manifold partition algorithm for constructing linear subspaces is more efficient, and the dimensionality of each linear subspace can be determined automatically by using PCA.
Compared with MPDA, Maximal Linear Embedding (MLE) [29] also constructs a number of linear subspaces based on the measure of linearity but follows a different principle. MLE prefers to construct the linear subspaces whose sizes should be as large as possible, while MPDA constructs a number of linear subspaces with similar and relatively small sizes to justify the manifold assumption as well as the Taylor expansion. Another difference between MPDA and MLE is that although MPDA partitions the data manifold to extract piecewise regional consistency, it still use all the data to discover the underlying manifold, whereas MLE only uses a portion of data to obtain the resultant global coordinate. This means that MPDA utilizes more information from data sets than MLE. Locally Multidimensional Scaling (LMDS) [28] can be seen as a sparsified version of LTSA. It constructs tangent spaces based on a set of overlapping local subspaces where the number of subspaces should be as small as possible. This strategy allows LMDS to avoid estimating tangent spaces for each data point, and thus makes LMDS more efficient than LTSA. However, if the local subspaces are non-overlapping, LMDS cannot work normally any more, because as an alignment based method, it needs the overlapping parts of local subspaces to serve as the implicit connections for aligning a global coordinate. In contrast, since MPDA explicitly characterizes the connections among tangent spaces by estimating tangent vectors, it can construct a global coordinate based on non-overlapping local subspaces.

Real-World Data Sets
We focus on supervised dimensionality reduction tasks and test the proposed PMPDA and MPDA on multiple real-world data sets. Comparisons are made with: 1) Classical baseline methods including PCA and LDA; 2) Graph Laplacian based methods including Marginal Fisher Analysis (MFA) [5], Locality Sensitive Discriminant Analysis (LSDA) [6] and Local Fisher Discriminant Analysis (LFDA) [7], which are the most related counterparts of MPDA; 3) Tangent space based methods Linear Local Tangent Space Alignment (LLTSA) [30] and linearized PFE (we call it LPFE) which are the linear variations of LTSA and PFE, respectively; 4) Other types of supervised dimensionality reduction methods Least-Squares Dimension Reduction (LSDR) [17]. Seven realword data sets are used including COIL20, COIL100 [31], Face Detection [32], a subset of MNIST [33] containing the first 2k training and test images, and three UCI data sets including OptDigits, Semeion Handwritten and Vehicle [34]. The configuration of each data set is shown in Table 1.
The parameters k, α and γ for both PMPDA and MPDA are determined by 4-fold cross validation, and the parameters k ′ and M for the partition algorithm in MPDA are set to be k ′ = 6 and M = 10 empirically. Furthermore, all the parameters for MFA, LSDA, LFDA, LLTSA, and LPFE are selected by 4-fold cross validation. The measure for each round of cross validation is the classification accuracy on the validation set. Specifically, after training different dimensionality reduction algorithms on the training set, we first perform dimensionality reduction on both the training and validation sets, and then train a classifier using the training set in the discovered subspace. Finally, by classifying data in the validation set, we can determine the values of parameters according to the classification results. Originally, LPFE is an unsupervised method. For a fair comparison, LPFE is performed based on a supervised graph which is identical to the within-class graph G used in MPDA. For each data set, we randomly split certain rates of data as the training set to compute the subspace, and then classify the rest of data by the nearest neighbor classifier (1-NN) in the discovered subspace. Every experimental result is obtained from the average over 20 splits. For computational efficiency, we use PCA to preserve 95% energy for the data sets whose dimensionality are larger than 100. In addition, we also compare the baseline method that just employs the 1-NN classifier in the original space without performing dimensionality reduction.
Generally, the classification performance varies with the dimensionality of the subspace. For each method, the best performance as well as the corresponding dimensionality of the subspace are reported. PMPDA is not tested on the COIL100 and OptDigits data sets because of out of memory. LSDR is not tested on the COIL100 and OptDigits data sets since the execution time is too long. Table 2 shows the average error rates of each method with corresponding dimensionality on different data sets, where the best method and the comparable one based on Student's t-test with a p-value of 0.05 are highlighted in bold font. We see that PMPDA or MPDA outperforms other methods in a statistical significant manner for all the data sets except the Vehicle data set. This means that compared with the graph Laplacian based methods, our methods improve the performance of supervised dimensionality reduction by taking advantage of the regional consistency from tangent spaces and keeping in mind that the within-class similarity shall be achieved along the varying direction of the data manifold. LPFE fails to get reasonable results, which is probably because it has no ability to separate data from different classes, and it may lose too much (non-linear) information due to the linearization. It is worth noting that although MPDA can be viewed as the approximation of PMPDA, it still obtains comparable or better results than PMPDA. This suggests that the manifold partition strategy itself is able to improve the performance of dimensionality reduction, because it provides MPDA with more flexibility to estimate tangent spaces. In addition, although not shown in Table 2, if we remove PMPDA out of the comparison, MPDA becomes the best method based on t-test with p=0.05. This demonstrates that MPDA is consistently better than its counterparts. Figure 3 depicts how the mean classification accuracy varies with respect to the dimensionality of embedding spaces on different data sets. It shows that MPDA and PMPDA work quite well. Particularly, except for the Vehicle data set, MPDA and PMPDA (if applicable) consistently obtain the best results with respect to the dimensionality of embedding spaces. To further evaluate the effectiveness of MPDA, we also conduct experiments on the data sets that have been tested by the authors of its counterparts. In this case, results from the existing algorithms can be cited from the corresponding original paper for fairer comparisons. According to Table 2, LFDA seems to be the best algorithm except for MPDR and PMPDR. Because of this, we focus on comparing MPDA with LFDA on the USPS handwritten digit data set according to the configuration of LFDA's original paper. Again, MPDR and PMPDR outperform their counterparts with statistical significance. Please refer to the supplementary material for details.

Parameter Sensitivity
In this section, we evaluate the parameter sensitivity of MPDA on the Semeion Handwritten data set. Specifically, we aim to test how the performance of MPDA varies with its parameters k, γ, M , and k ′ , respectively. To this end, the default values of k, γ, M and k ′ are set to be 5, 1, 10 and 6, respectively. And we alternately change one of these parameters to evaluate the performance of MPDA when the other parameters are fixed. Figure 4 implies that k and M are more important than γ and k ′ . Their values should be determined properly, while those of γ and k ′ seem to have no significant influence on the performance of MPDA. Overall, MPDA get stable results as its parameters change, where the classification accuracy ranges from 90% to 92%. Therefore, MPDA is relatively insensitive to the changes of parameters.

CONCLUSION
In this paper we have proposed a tangent space based linear dimensionality reduction method named Manifold Partition Discriminant Analysis (MPDA). By considering both pairwise differences and piecewise regional consistency, MPDA can find a linear embedding space where the within-class similarity is achieved along the direction that is consistent with the local variation of the data manifold, while nearby data belonging to different classes are well separated. Different to graph Laplacian methods that capture only the pairwise interaction between data points, our method capture both pairwise as well as higher order interactions (using regional consistency) between data points.
As a crucial part of MPDA, the manifold partition strategy plays a key role in preserving the manifold structure to improve the measure of the within-class similarity. It not only enables MPDA to adaptively determine the number of dimensions of each linear subspace, but also can be adopted by other tangent space base methods to make them more efficient. The experiments on multiple real-world data sets have shown that compared with existing works MPDA can obtain better classification results.