An Optimization Approach to Supervised Principal Component Analysis

Abstract

Supervised dimensionality reduction has become an important theme in the last two decades. Despite the plethora of models and formulations, there is a lack of a simple model that aims to project the set of patterns into a space defined by the classes (or categories). We set up a model where each class is represented as a 1D subspace of the vector space formed by the features. Assuming the set of classes does not exceed the cardinality of the features, the model results in multi-class supervised learning in which the features of each class are projected into the class subspace. Class discrimination is guaranteed via the imposition of the orthogonality of the 1D class sub-spaces. The resulting optimization problem—formulated as the minimization of a sum of quadratic functions on a Stiefel manifold—while being non-convex (due to the constraints), has a structure for which we can identify when we have reached a global minimum. After formulating a version with standard inner products, we extend the formulation to a reproducing kernel Hilbert space and similarly to the kernel version. Comparisons with the multi-class Fisher discriminants and principal component analysis showcase the relative merits toward dimensionality reduction.

1. Introduction

Dimensionality reduction and supervised learning have long been active tropes in machine learning. For example, principal component analysis (PCA) and the support vector machine (SVM) are standard bearers for dimensionality reduction and supervised learning. Even now, machine learning researchers are accustomed to performing PCA when seeking a simple dimensionality reduction technique, even though it is an unsupervised learning approach. In the past decade, there has been considerable interest in including supervision (expert label information) in dimensionality reduction techniques. Beginning with the well-known EigenFaces versus FisherFaces debate [1], considerable activity has centered around using Fisher linear discriminants (FLD) and other supervised learning approaches in dimensionality reduction. Since the Fisher linear discriminant has a multi-class extension, it is natural to begin there. However, asking if this is the only possible approach is also natural. In this work, with a fundamental goal, we design a category space approach using multi-class information to reduce dimensionality.

The venerable Fisher discriminant is a supervised dimensionality reduction technique wherein a maximally discriminative one-dimensional subspace is estimated from the data. The criterion used for discrimination is the ratio between the squared distance of the projected class means and a weighted sum of the projected variances. This criterion has a closed-form solution yielding the best 1D subspace. The Fisher discriminant also has an extension to the multi-class case. Here, the criterion used is more complex and highly unusual: the squared distance ratio between each class’s projected mean compared to the total projected mean and the sum of the projected variances. This, too, results in a closed-form solution but with the subspace dimension cardinality being one less than the number of classes.

The above description of the multi-class FLD sets the stage for our approach. We assume the set of categories (classes) is a subspace of the original feature space (similar to FLD). However, we add the restriction that the category bases are mutually orthogonal with the origin of the vector space belonging to no category. Given this restriction, the multi-class category space dimensionality reduction criterion is quite straightforward. We maximize the square of the inner product between each pattern and its category axis to discover the category space via this process. (Setting the origin is a highly technical issue and, therefore, not described here.) The result is a sum of quadratic objective functions on a Stiefel manifold—the category space of orthonormal basis vectors. This very interesting objective function has coincidentally received quite a bit of treatment recently [2, 3, 4, 5]. Furthermore, there is no need to restrict ourselves to sums of quadratic objective functions provided we are willing to forego useful analysis of this base case. The unusual aspect of the objective function comprising sums of quadratic objective functions is that we can formulate a criterion that guarantees that we have reached a global minimum if the achieved solution satisfies it.

While numerous alternatives exist to the FLD (such as canonical correlation analysis [6, 7]) and while there are many nonlinear unsupervised dimensionality reduction techniques (such as local linear embedding [8, 9, 10], ISOMAP [11, 12] and Laplacian Eigenmaps [13, 14, 15]), we have not encountered a simple dimensionality reduction technique which is based on projecting the data into a space spanned by the categories. Unfortunately, no algorithm at present can a priori guarantee satisfaction of this criterion; hence, we can only check on a case-by-case basis. Despite this, our experimental results show that we get efficient solutions, competitive with those obtained from other dimensionality reduction algorithms.

2. Related work

Traditional dimensionality reduction techniques like principal component analysis (PCA) [16, 17, 18] and supervised algorithms such as Fisher linear discriminant analysis [19] seek to retain significant features while removing insignificant, redundant, or noisy features. Many real-world problems have been solved using these algorithms as preprocessing steps before applying a classification algorithm. A limitation of most methods is that there is no specific connection between the dimensionality reduction technique and the supervised learning-driven classifier. Dimensionality reduction techniques such as canonical correlation analysis (CCA) [20], and partial least squares (PLS) [21, 22] on the one hand and classification algorithms such as support vector machines (SVM) [23] on the other seek to optimize different criteria. In contrast, in this paper, we analyze dimensionality reduction from the perspective of multi-class classification. Using a category vector space (with dimension equal to class cardinality) is an integral aspect of this approach.

In supervised learning, it is customary for classification methodologies to regard classes as nominal labels without having any internal structure. This remains true regardless of whether a discriminant or classifier is sought. Discriminants are designed by attempting to separate patterns into opposing classes [24, 25, 26]. When generalization to a multi-class classifier is required, many oppositional discriminants are combined, with the final classifier being a winner-take-all (or voting-based) decision w.r.t. the set of nominal labels. Convex objective functions based on misclassification error minimization (or approximation) are not that different either. Least-squares or logistic regression methods set up convex objective functions with nominal labels converted to binary outputs [27, 28]. When extensions to multi-class are sought, the binary labels are extended to one of K encoding, with K being the number of classes.

Support vector machines (SVMs) were inherently designed for two-class discrimination, and all formulations of multi-class SVMs extend this oppositional framework using one-versus-one or one-versus-all schemes. Below, we begin by describing the different approaches to the multi-class problem. This is not meant to be exhaustive but provides an overview of some popular methods and approaches researched in classification and dimensionality reduction. Folley and Sammon [29, 30] studied the two class problems and feature selection and focused on criteria with the greatest potential to discriminate. Feature selection aims to find a set of features with the best discrimination properties. To identify the best feature vectors, they chose the generalized Fisher optimality criterion proposed by [31]. The selected directions maximize the Fisher criterion, which has attractive discrimination properties. Principal components analysis (PCA) permits the reduction of dimensions of high dimensional data without losing significant information [16, 20, 32]. Principal components identify patterns or significant features without considering discriminative considerations [33]. Supervised PCA (SPCA), derived from PCA, is a method for obtaining useful sub-spaces when the labels are considered. This technique was first described in [34] under the title “supervised clustering.” The idea behind SPCA is to perform selective dimensionality reduction using carefully chosen subsets of labeled samples. This is used to build a prediction model [35]. Unfortunately, despite the superficial similarity to our work, SPCA does not carefully reformulate supervised dimensionality reduction as an optimization problem (as we do) and develop an algorithm that projects vectors into the space of categories- the present work’s goal. While we have addressed the most popular techniques in dimensionality reduction and multi-class classification, this is not an exhaustive study of the literature. We focus primarily on discriminative dimensionality reduction methods that improve multi-class classification performance. The closest we have seen in relation to our work on category spaces is the work in [36, 37]. They mention the importance and usefulness of modeling categories as vector spaces for document retrieval and explain how unrelated items should have an orthogonal relationship. This is to say that they should have no features in common. The structured SVM in [38] is another effort at going beyond nominal classes. Here, classes can have internal structures in the form of strings, trees, etc. However, explicitly modeling classes as vector spaces is not carried out.

From the above, the modest goal of the present work should be clear. We seek to project the input feature vectors to a category space—, a subspace formed by category basis vectors. The multi-class FLD falls short of this goal since the number of projected dimensions is one less than the number of classes. The multi-class (and more recently multi-label) SVM [39] literature is fragmented due to a lack of agreement regarding the core issue of multi-class discrimination. The varieties of supervised PCA do not begin by clearly formulating a criterion for category space projection. Variants such as CCA [40, 41], PLS [42, 43], and structured SVM’s [38] while attempting to add structure to the categories do not go as far as the present work in attempting to fit a category subspace. Kernel variants of the above also do not touch the basic issue addressed in the present work. Nonlinear (and manifold learning-based) dimensionality reduction techniques [8, 11, 13, 44, 45] are unsupervised and therefore do not qualify.

3. Dimensionality reduction using a category space formulation

3.1 Maximizing the square of the inner product

The principal goal is a new form of supervised dimensionality reduction. Specifically, when we seek to marry principal component analysis with supervised learning, the simplest synthesis is category space dimensionality reduction with orthogonal class vectors. Assume the existence of a feature space with each feature vector $x_i\in {\mathbf{R}}^D$. We aim to perform supervised dimensionality reduction by reducing the number of feature dimensions from D to K where $K\le D$. Here K is the number of classes, and the first simplifying assumption made in this work is that we will represent the category space using K orthonormal basis vectors $\left\{w_k\right\}$ together with an origin $x_0\in {\mathbf{R}}^D.$ The second assumption we make is that each feature vector $x_i$ should have a large magnitude inner product with its assigned class. From the orthonormality constraint above, this automatically implies a small magnitude inner product with all other weight vectors. A candidate objective function and constraints following the above considerations are

$$E\left(W\right)=-\frac{1}{2}\sum _{k=1}^K\sum _{i_k\in C_k}{\left[w_k^T\left(x_{i_k}-x_0\right)\right]}^2$$E1

and

$$w_k^T{w}_l=\left\{\begin{array}{cc}1,& k=l\\ 0,& k\ne l\end{array}\right.$$E2

respectively. In Eq. (1), $W=\left[w_1,w_2,\dots ,w_K\right]$. Note that we have referred to this as a candidate objective function for two reasons. First, the origin $x_0$ is still unspecified, and obviously, we cannot minimize Eq. (1) w.r.t. $x_0$ as the minimum value is not bounded from below. Second, it is unclear why we cannot use the inner product’s absolute value or other symmetric functions. Both these issues are addressed later in this work. We currently resolve the origin issue by setting $x_0$ to the centroid of all the feature vectors (with this choice getting a principled justification below).

The objective function in Eq. (1) is the negative of a quadratic function. Since the function $-x^2$ is concave, it admits a Legendre transform-based majorization [46] using the tangent of the function. That is, we propose to replace objective functions of the form $-\frac{1}{2}{x}^2$ with ${min}_y-\mathit{xy}+\frac{1}{2}{y}^2$ which can quickly be checked to be valid for an unconstrained auxiliary variable y. Note that this transformation yields a linear objective function w.r.t. x, which is to be expected from the geometric interpretation of a tangent.

Consider the following Legendre transformation of the objective function in Eq. (1). The new objective function is

$$E_{\text{quad}}\left(W,Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[z_{{\mathit{ki}}_k}\left(-w_k^T{x}_{i_k}+w_k^T{x}_0\right)+\frac{1}{2}{z}_{{\mathit{ki}}_k}^2\right]$$E3

where $Z=\left\{z_{{\mathit{ki}}_k}|k\in \left\{1,\dots ,K\right\},i_k\in \left\{1,\dots ,|C_k|\right\}\right\}$. Consider this an objective function over $x_0$ as well. We require additional constraints to avoid minima at negative infinity (i.e., for the objective function to be coercive). One such constraint (and perhaps not the only one) is of the form ${\sum }_{i_k\in C_k}{z}_{{\mathit{ki}}_k}=0,\forall k$. When this constraint is imposed, we obtain a new objective function,

$$E_{\text{quad}}\left(W,Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-z_{{\mathit{ki}}_k}{w}_k^T{x}_{i_k}+\frac{1}{2}{z}_{{\mathit{ki}}_k}^2\right]$$E4

to be minimized subject to the constraints

$$\sum _{i_k\in C_k}{z}_{{\mathit{ki}}_k}=0,\forall k$$E5

which are in addition to the orthonormal constraints in Eq. (2). This objective function yields a Z, which removes the class-specific centroid of $C_k$ for all classes.

3.2 Maximizing the absolute value of the inner product

We have justified our choice of centroid removal mentioned above indirectly obtained via constraints imposed on Legendre transform auxiliary variables. The above objective function can be suitably modified using different forms (absolute inner product, etc.). To see this, consider the following objective function, which minimizes the negative of the magnitude of the inner product:

$$E\left(W\right)=-\sum _{k=1}^K\sum _{i_k\in C_k}\mid w_k^T\left(x_{i_k}-x_0\right)\mid .$$E6

Since $-\mid x\mid$ is also a concave function, it too can be majorized. Consider first replacing the non-differentiable objective function $-\mid x\mid$ with $-\sqrt{x^2+ϵ}$ (also concave) where $ϵ$ can be chosen to be a suitably small value. Now consider replacing $-\sqrt{x^2+ϵ}$ with ${min}_y-\mathit{xy}-ϵ\sqrt{1-y^2}$ which can again quickly checked to be valid for a constrained auxiliary variable $y\in \left[-1,1\right]$. The constraint is somewhat less relevant since the minimum w.r.t. y occurs at $y=\frac{x}{\sqrt{x^2+{ϵ}^2}}$ which lies within the constraint interval. Note that this transformation yields a linear objective function w.r.t. x. As before, we introduce a new objective function

$$E_{\mathrm{abs}}\left(W,Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-z_{{\mathit{ki}}_k}{w}_k^T{x}_{i_k}-ϵ\sqrt{1-z_{{\mathit{ki}}_k}^2}\right]$$E7

to be minimized subject to the constraints ${\sum }_{i_k\in C_k}{z}_{{\mathit{ki}}_k}=0,\forall k$ and $z_{{\mathit{ki}}_k}\in \left[-1,1\right]$ which are the same as in Eq. (5) in addition to the orthonormal constraints in Eq. (2).

3.3 Extension to RKHS kernels

The generalization to RKHS kernels is surprisingly straightforward. First, we follow standard kernel PCA and write the weight vector in terms of the RKHS projected patterns $\varphi \left(x_l\right)$ to get

$$w_k=\sum _{i=1}^N{\alpha }_{\mathit{ki}}\varphi \left(x_i\right).$$E8

Note that the expansion of the weight vector is in overall patterns rather than just the class-specific ones. This assumes that the weight vector for each class lives in the subspace (potentially infinite dimensional) spanned by the RKHS projected patterns—the same assumption as in standard kernel PCA. The orthogonality constraint between weight vectors becomes

$$\begin{array}{l}⟨w_k,w_l⟩=⟨\sum _{i=1}^N{\alpha }_{\mathit{ki}}\varphi \left(x_i\right),\sum _{i=1}^N{\alpha }_{\mathit{li}}\varphi \left(x_i\right)⟩\\ =\sum _{i=1}^N\sum _{j=1}^N{\alpha }_{\mathit{ki}}{\alpha }_{\mathit{kj}}⟨\varphi \left(x_i\right),\varphi \left(x_j\right)⟩\\ =\sum _{i=1}^N\sum _{j=1}^N{\alpha }_{\mathit{ki}}{\alpha }_{\mathit{kj}}K\left(x_i,x_j\right)\end{array}$$E9

which is equal to one if $k=l$ and zero otherwise. In matrix form, the orthonormality constraints become

$${\mathit{AGA}}^T=I_K$$E10

where ${\left[A\right]}_{\mathit{kl}}\equiv {\alpha }_{\mathit{ki}}$ and ${\left[G\right]}_{\mathit{ij}}=K\left(x_i,x_j\right)$ is the well-known Gram matrix of pairwise RKHS inner products between the patterns.

The corresponding squared inner product and the absolute value of the inner product objective functions are

$$E_{\text{Kquad}}\left(A,Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-\sum _{j=1}^N{z}_{{\mathit{ki}}_k}{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)+\frac{1}{2}{z}_{{\mathit{ki}}_k}^2\right]$$E11

and

$$E_{\text{Kabs}}\left(A,Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-\sum _{j=1}^N{z}_{{\mathit{ki}}_k}{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)-ϵ\sqrt{1-z_{{\mathit{ki}}_k}^2}\right]$$E12

respectively. These have to be minimized w.r.t. the orthonormal constraints in Eq. (10) and the origin constraints in Eq. (5). Note that the objective functions are identical w.r.t. the matrix A. The parameter $ϵ$ can be set to a very small but positive value.

4. An algorithm for supervised dimensionality reduction

We now return to the objective functions and constraints in Eqs. (4) and (7) prior to tackling the corresponding kernel versions in Eqs. (11) and (12) respectively. It turns out that the approach for minimizing the former can be readily generalized to the latter, with the former being easier to analyze. Note that the objective functions in Eqs. (4) and (7) are identical w.r.t. W. Consequently, we dispense with the optimization problems w.r.t. Z, which are straightforward and focus on the optimization problem w.r.t. W.

4.1 Weight matrix estimation with orthogonality constraints

The objective function and constraints on W can be written as

$$E_{\text{equiv}}\left(W\right)=-\sum _{k=1}^K\sum _{i_k\in C_k}{z}_{{\mathit{ki}}_k}{w}_k^T{x}_{i_k}$$E13

and

$$w_k^T{w}_l=\left\{\begin{array}{cc}1,& k=l\\ 0,& k\ne l\end{array}\right..$$E14

Note that the set Z is not included in this objective function despite its presence in the larger objective functions of Eqs. (4) and (7). The orthonormal constraints can be expressed using a Lagrange parameter matrix to obtain the following Lagrangian:

$$L\left(W,\mathrm{\Lambda }\right)=-\sum _{k=1}^K\sum _{i_k\in C_k}{z}_{{\mathit{ki}}_k}{w}_k^T{x}_{i_k}+\text{trace}\left\{\mathrm{\Lambda }\left(W^{T}W-I_K\right)\right\}.$$E15

Setting the gradient of L w.r.t. W to zero, we obtain

$${\nabla }_{W}L\left(W,\mathrm{\Lambda }\right)=-Y+W\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)=0$$E16

where the matrix Y of size $D\times K$ is defined as

$$Y\equiv \left[\sum _{i_1\in C_1}{z}_{1i_1}{x}_{i_1},\dots ,\sum _{i_k\in C_k}{z}_{{\mathit{ki}}_k}{x}_{i_k}\right].$$E17

Using the constraint $W^{T}W=I_K$, we get

$$\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)=W^{T}Y.$$E18

Since $\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)$ is symmetric, this immediately implies that $W^{T}Y$ is symmetric. From Eq. (16), we also get

$$\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)W^{T}W\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)={\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)}^2=Y^{T}Y.$$E19

Expanding Y using its singular value decomposition (SVD) as $Y=U\mathrm{\Sigma }{V}^T,$ the above relations can be simplified to

$$Y=U\mathrm{\Sigma }{V}^T={\mathit{UV}}^T\left(V\mathrm{\Sigma }{V}^T\right)=W\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)$$E20

giving

$$\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)=V\mathrm{\Sigma }{V}^T$$E21

and

$$W={\mathit{UV}}^T.$$E22

We have shown that the optimal solution for W is the polar decomposition of Y, namely $W={\mathit{UV}}^T$. Since Z has been held fixed during the estimation of W, in the subsequent step, we can hold W fixed and solve for Z and repeat. We obtain an alternating algorithm that iterates between estimating W and Z until a convergence criterion is met.

4.2 Estimation of the auxiliary variable Z

The objective function and constraints on Z depend on whether we use objective functions based on the square or absolute value of the inner product. We separately consider the two cases. The inner product squared effective objective function

$$E_{\text{quadeff}}\left(Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-z_{{\mathit{ki}}_k}{w}_k^T{x}_{i_k}+\frac{1}{2}{z}_{{\mathit{ki}}_k}^2\right]$$E23

is minimized w.r.t. Z subject to the constraints ${\sum }_{i_k\in C_k}{z}_{{\mathit{ki}}_k}=0,\forall k$. The straightforward solution obtained via standard minimization is

$$\begin{array}{l}{z}_{{\mathit{ki}}_k}=w_k^T{x}_{i_k}-\frac{1}{\left|C_k\right|}{\sum }_{i_k\in C_k}{w}_k^T{x}_{i_k}\\ =w_k^T\left(x_{i_k}-\frac{1}{\left|C_k\right|}{\sum }_{i_k\in C_k}{x}_{i_k}\right).\end{array}$$E24

The absolute value effective objective function

$$E_{\text{abseff}}\left(Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-z_{{\mathit{ki}}_k}{w}_k^T{x}_{i_k}-ϵ\sqrt{1-z_{{\mathit{ki}}_k}^2}\right]$$E25

is also minimized w.r.t. Z subject to the constraints ${\sum }_{i_k\in C_k}{z}_{{\mathit{ki}}_k}=0,\forall k$. A heuristic solution obtained (eschewing standard minimization) is

$$z_{{\mathit{ki}}_k}=\frac{w_k^T{x}_{i_k}}{\sqrt{{\left(w_k^T{x}_{i_k}\right)}^2+{ϵ}^2}}-\frac{1}{\left|C_k\right|}\sum _{i_k\in C_k}\frac{w_k^T{x}_{i_k}}{\sqrt{{\left(w_k^T{x}_{i_k}\right)}^2+{ϵ}^2}}$$E26

which has to be checked to be valid. The heuristic solution acts as an initial condition for constraint satisfaction (which can be efficiently obtained via 1D line minimization). The first order Karush-Kuhn-Tucker (KKT) conditions obtained from the Lagrangian

$$L_{\text{abseff}}\left(Z,M\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-z_{{\mathit{ki}}_k}{w}_k^T{x}_{i_k}-ϵ\sqrt{1-z_{{\mathit{ki}}_k}^2}\right]-\sum _{k=1}^K{\mu }_k\sum _{i_k\in C_k}{z}_{{\mathit{ki}}_k}$$E27

are

$$-w_k^T{x}_{i_k}+ϵ\frac{z_{{\mathit{ki}}_k}}{\sqrt{1-z_{{\mathit{ki}}_k}^2}}-{\mu }_k=0,\forall k$$E28

from which we obtain

$$z_{{\mathit{ki}}_k}=\frac{w_k^T{x}_{i_k}+{\mu }_k}{\sqrt{{\left(w_k^T{x}_{i_k}+{\mu }_k\right)}^2+{ϵ}^2}}.$$E29

We see that the constraint $z_{{\mathit{ki}}_k}\in \left[-1,1\right]$ is also satisfied. For each category $C_k$, there exists a solution to the Lagrange parameter ${\mu }_k$ such that ${\sum }_{i_k}{z}_{{\mathit{ki}}_k}=0$. This can be obtained via any efficient 1D search procedure like golden section [47].

4.3 Extension to the kernel setting

The objective function and constraints on the weight matrix A in the kernel setting are

$$E_{\text{Kequiv}}\left(A\right)=-\sum _{k=1}^K\sum _{i_k\in C_k}\sum _{j=1}^N{z}_{{\mathit{ki}}_k}{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)$$E30

with the constraints

$${\mathit{AGA}}^T=I_K$$E31

where ${\left[A\right]}_{\mathit{ki}}={\alpha }_{\mathit{ki}}$ and ${\left[G\right]}_{\mathit{ij}}=K\left(x_i,x_j\right)$ is the $N\times N$ kernel Gram matrix. The constraints can be expressed using a Lagrange parameter matrix to obtain the following Lagrangian,

$$L_{\ker }\left(A,\mathrm{\Lambda }\right)=-\sum _{k=1}^K\sum _{i_k\in C_k}\sum _{j=1}^N{z}_{{\mathit{ki}}_k}{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)+\text{trace}\left\{{\mathrm{\Lambda }}_{\ker }\left({\mathit{AGA}}^T-I_K\right)\right\}.$$E32

Setting the gradient of $L_{\ker }$ w.r.t. A to zero, we obtain

$$-Y_{\ker }+\left({\mathrm{\Lambda }}_{\ker }+{\mathrm{\Lambda }}_{\ker }^T\right)\mathit{AG}=0$$E33

where the matrix $Y_{\ker }$ of size $K\times N$ is defined as

$${\left[Y_{\ker }\right]}_{\mathit{kj}}\equiv \sum _{i_k\in C_k}{z}_{{\mathit{ki}}_k}K\left(x_j,x_{i_k}\right).$$E34

Using the constraint ${\mathit{AGA}}^T=I_K$, we obtain

$$\left({\mathrm{\Lambda }}_{\ker }+{\mathrm{\Lambda }}_{\ker }^T\right){\mathit{AGA}}^T\left({\mathrm{\Lambda }}_{\ker }+{\mathrm{\Lambda }}_{\ker }^T\right)={\left({\mathrm{\Lambda }}_{\ker }+{\mathrm{\Lambda }}_{\ker }^T\right)}^2=Y_{\ker }{G}^{-1}{Y}_{\ker }^T.$$E35

Expanding $Y_{\ker }{G}^{-\frac{1}{2}}$ using its singular value decomposition as $Y_{\ker }{G}^{-\frac{1}{2}}=U_{\ker }{S}_{\ker }{V}_{\ker }^T$, the above relations can be simplified to

$$\left({\mathrm{\Lambda }}_{\ker }+{\mathrm{\Lambda }}_{\ker }^T\right)=U_{\ker }{S}_{\ker }{U}_{\ker }^T$$E36

and

$${\mathit{AG}}^{\frac{1}{2}}=U_{\ker }{V}_{\ker }^T\Rightarrow A=U_{\ker }{V}_{\ker }^T{G}^{-\frac{1}{2}}.$$E37

We have shown that the optimal solution for A is related to the polar decomposition of $Y_{\ker }{G}^{-\frac{1}{2}}$, namely $A=U_{\ker }{V}_{\ker }^T{G}^{-\frac{1}{2}}$. Since Z has been held fixed during the estimation of A, in the subsequent step, we can hold A fixed and solve for Z and repeat. We thereby obtain an alternating algorithm that iterates between estimating A and Z until a convergence criterion is met. This is analogous to the non-kernel version above.

The solutions for Z in this setting are very straightforward to obtain. We eschew the derivation and merely state that

$$\begin{array}{c}{z}_{{\mathit{ki}}_k}={\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)-\frac{1}{\left|C_k\right|}{\sum }_{i_k\in C_k}{\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)\\ ={\sum }_{j=1}^N{\alpha }_{\mathit{kj}}\left(K\left(x_j,x_{i_k}\right)-\frac{1}{\left|C_k\right|}{\sum }_{i_k\in C_k}K(x_j,x_{i_k})\right)\end{array}$$E38

for the squared inner product kernel objective and

$$z_{{\mathit{ki}}_k}=\frac{{\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)}{\sqrt{{\left({\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)\right)}^2+{ϵ}^2}}-\frac{1}{\left|C_k\right|}\sum _{i_k\in C_k}\frac{{\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)}{\sqrt{{\left({\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)\right)}^2+{ϵ}^2}}$$E39

for the absolute valued kernel objective. This heuristic solution acts as an initial condition for constraint satisfaction (which can be efficiently obtained via 1D line minimization). Following the line of Eqs. (27)–(29) above, the solution can be written as

$$z_{{\mathit{ki}}_k}=\frac{{\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)+{\mu }_k}{\sqrt{{\left({\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)+{\mu }_k\right)}^2+{ϵ}^2}}.$$E40

For each category $C_k$, as before, there exists a solution to the Lagrange parameter ${\mu }_k$ such that ${\sum }_{i_k}{z}_{{\mathit{ki}}_k}=0$. Once again, this can be obtained via any efficient 1D search procedure like golden section [47].

4.4 Analysis

4.4.1 Euclidean setting

The simplest objective function in the above sequence, analyzed in the literature, is based on the squared inner product. Below, we summarize this work by closely following the treatment in [2, 48]. First, to bring our work in sync with the literature, we eliminate the auxiliary variable Z from the squared inner product objective function (treated as a function of both W and Z here):

$$E_{\text{quadeff}}\left(W,Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-z_{{\mathit{ki}}_k}{w}_k^T{x}_{i_k}+\frac{1}{2}{z}_{{\mathit{ki}}_k}^2\right].$$E41

Setting $z_{{\mathit{ki}}_k}=w_k^T\left(x_{i_k}-\frac{1}{\left|C_k\right|}{\sum }_{i_k\in C_k}{x}_{i_k}\right)$ which is the optimum solution for Z, we get

$$E_{\text{quad}}\left(W\right)=-\frac{1}{2}\sum _{k=1}^K{w}_k^T{R}_k{w}_k\equiv -\frac{1}{2}\sum _{k=1}^K\sum _{i_k\in C_k}{\left[w_k^T\left(x_{i_k}-\frac{1}{\left|C_k\right|}\sum _{i\in C_k}{x}_i\right)\right]}^2$$E42

where $R_k$ is the class-specific covariance matrix:

$$R_k\equiv \sum _{i_k\in C_k}\left(x_{i_k}-\frac{1}{\left|C_k\right|}\sum _{i\in C_k}{x}_i\right){\left(x_{i_k}-\frac{1}{\left|C_k\right|}\sum _{i\in C_k}{x}_i\right)}^T.$$E43

We seek to minimize Eq. (42) w.r.t. W under the orthonormality constraints $W^{T}W=I_K$.

A set of K orthonormal vectors $\left\{w_k\in {\mathbf{R}}^D,k\in \left\{1,\dots ,K\right\}\right\}$ in a D-dimensional Euclidean space is a point on the well-known Stiefel manifold, denoted here by $M_{D,K}$ with $K\le D$. The problem in Eq. (42) is equivalent to the maximization of the sum of heterogeneous quadratic functions on a Stiefel manifold. The functions are heterogeneous in our case since the class-specific covariance matrices $R_k$ are not identical in general. The Lagrangian corresponding to this problem (with Z removed via direct minimization) is

$$L_{\text{quad}}\left(W,\mathrm{\Lambda }\right)=-\frac{1}{2}\sum _{k=1}^K{w}_k^T{R}_k{w}_k+\text{trace}\left[{\mathrm{\Lambda }}^T\left(W^{T}W-I_K\right)\right].$$E44

Setting the gradient of the above Lagrangian w.r.t. W to zero, we obtain

$$\left[R_1{w}_1,R_2{w}_2,\dots ,R_K{w}_K\right]=W\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right).$$E45

Noting that $\mathrm{\Lambda }+{\mathrm{\Lambda }}^T$ is symmetric and using the Stiefel orthonormality constraint $W^{T}W=I_K$, we get

$$\left(\mathrm{\Lambda }+{\mathrm{\Lambda }}^T\right)=W^T\left[R_1{w}_1,R_2{w}_2,\dots ,R_K{w}_K\right].$$E46

The above can be considerably simplified. First we introduce a new vector $\mathbf{w}\in M_{D,K}$ defined as $\mathbf{w}\equiv {\left[w_1^T,w_2^T,\dots ,w_K^T\right]}^T$ and then rewrite Eq. (45) in vector form to get

$$R\mathbf{w}=S\left(\mathbf{w}\right)\mathbf{w}$$E47

where

$$R\equiv \left[\begin{array}{cccc}{R}_1& 0_K& \cdots & 0_K\\ 0_K& R_2& \cdots & 0_K\\ 0_K& \cdots & \ddots & 0_K\\ 0_K& \cdots & \cdots & R_K\end{array}\right]$$E48

is a $\mathit{KD}\times \mathit{KD}$ matrix and

$$S\left(\mathbf{w}\right)\equiv \left[\begin{array}{ccc}{w}_1^T{R}_1{w}_1{I}_K& \cdots & \frac{1}{2}\left(w_1^T{R}_1{w}_K+w_K^T{R}_K{w}_1\right)I_K\\ \frac{1}{2}\left(w_1^T{R}_1{w}_2+w_2^T{R}_2{w}_1\right)I_K& \cdots & \frac{1}{2}\left(w_2^T{R}_2{w}_K+w_K^T{R}_K{w}_2\right)I_K\\ ⋮& \ddots & ⋮\\ \frac{1}{2}\left(w_1^T{R}_1{w}_K+w_K^T{R}_K{w}_1\right)I_K& \cdots & w_K^T{R}_K{w}_K{I}_K\end{array}\right]$$E49

a $\mathit{KD}\times \mathit{KD}$ symmetric matrix. The reason S(w) can be made symmetric is because it is closely related to the solution to ${\left(\mathrm{\Lambda }+\mathrm{\Lambda }\right)}^T,$ which has to be symmetric. The first and second order necessary conditions for a vector ${\mathbf{w}}_0\in M_{D,K}$ to be a local minimum (feasible point) for the problem in Eq. (42) are as follows:

$$R{\mathbf{w}}_0=S\left({\mathbf{w}}_0\right){\mathbf{w}}_0$$E50

and

$${\left.\left(R-S\left({\mathbf{w}}_0\right)\right)\right|}_{\mathit{TM}\left({\mathbf{w}}_0\right)}$$E51

is negative semi-definite. In Eq. (51), $\mathit{TM}\left({\mathbf{w}}_0\right)$ is the tangent space of the Stiefel manifold at ${\mathbf{w}}_0$. In a tour de force proof, Rapcsák further shows in [2] that if the matrix $\left(R-S\left({\mathbf{w}}_0\right)\right)$ is negative semi-definite, then a feasible point ${\mathbf{w}}_0$ is a global minimum. This is an important result since it adds a sufficient condition for a global minimum for the problem of minimizing a heterogeneous sum of quadratic forms on a Stiefel manifold.¹

4.4.2 The RKHS setting

We can readily extend the above analysis to the kernel version of the squared inner product. The complete objective function w.r.t. both the coefficients A and the auxiliary variable Z is

$$E_{\text{Kequiv}}\left(A,Z\right)=\sum _{k=1}^K\sum _{i_k\in C_k}\left[-\sum _{j=1}^N{z}_{{\mathit{ki}}_k}{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)+\frac{1}{2}{z}_{{\mathit{ki}}_k}^2\right].$$E52

Setting $z_{{\mathit{ki}}_k}={\sum }_{j=1}^N{\alpha }_{\mathit{kj}}K\left(x_j,x_{i_k}\right)$ which is the optimum solution for Z, we get

$$\begin{array}{ll}{E}_{\text{Kquad}}\left(A\right)& =-\frac{1}{2}{\sum }_{k=1}^K{\sum }_{i_k\in C_k}{\left[{\sum }_{j=1}^N{\alpha }_{\mathit{kj}}\left(K\left(x_j,x_{i_k}\right)-\frac{1}{\left|C_k\right|}{\sum }_{i_k\in C_k}K(x_j,x_{i_k})\right)\right]}^2\\ & =-\frac{1}{2}{\sum }_{k=1}^K{\mathit{\alpha }}_k^T{G}_k{\mathit{\alpha }}_k\end{array}$$E53

where ${\left[{\mathit{\alpha }}_k\right]}_j={\alpha }_{\mathit{kj}},A={\left[{\mathit{\alpha }}_1,{\mathit{\alpha }}_2,\dots ,{\mathit{\alpha }}_K\right]}^T$ (and)

$${\left[G_k\right]}_{\mathit{jm}}\equiv \sum _{i_k\in C_k}\left(K\left(x_j,x_{i_k}\right)-\frac{1}{\left|C_k\right|}\sum _{i\in C_k}K(x_j,x_i)\right)\cdot \left(K\left(x_m,x_{i_k}\right)-\frac{1}{\left|C_k\right|}\sum _{i\in C_k}K(x_m,x_i)\right)$$E54

The constraints on A can be written as

$${\mathit{AGA}}^T=I_K\Rightarrow {\left(G^{\frac{1}{2}}{A}^T\right)}^T\left(G^{\frac{1}{2}}{A}^T\right)=I_K.$$E55

Introducing a new variable $B=G^{\frac{1}{2}}{A}^T$, we may rewrite the kernel objective function and constraints as

$$E_{\text{Kquadnew}}\left(B\right)=-\frac{1}{2}\sum _{k=1}^K{\mathit{\beta }}_k^{T}H{\mathit{\beta }}_k\equiv -\frac{1}{2}\sum _{k=1}^K{\mathit{\beta }}_k^T{G}^{-\frac{1}{2}}{G}_k{G}^{-\frac{1}{2}}{\mathit{\beta }}_k$$E56

(where $B\equiv \left[{\mathit{\beta }}_1,{\mathit{\beta }}_2,\dots ,{\mathit{\beta }}_K\right]$) and

$$B^{T}B=I_K$$E57

respectively. This is now in the same form as the objective function and constraints in Section 4.4.1, and therefore, the Rapcsák analysis of that section can be directly applied here. The above change of variables is predicated on the positive definiteness of G. If this is invalid, principal component analysis has to be applied to G, resulting in a positive definite matrix in a reduced space, after which the above approach can be applied.

In addition to providing necessary conditions for global minima, the authors in [4] developed an iterative procedure as a method for a solution. We have adapted this to suit our purposes. A block coordinate descent algorithm which successively updates W and Z is presented in Algorithm 1.

Algorithm 1. Iterative process for minimization of the sum of squares of inner products objective function.

• Input: A set of labeled patterns ${\left\{x_{i_k}\right\}}_{i_k=1}^{\mid C_k\mid },\forall k\in \left\{1,\dots ,K\right\}$.

• Initialize:

  • Convergence threshold $\delta$.

  • Arbitrary orthonormal system $W^{\left(0\right)}$.

• Repeat

  • Calculate the sequence $\left\{W^{\left(1\right)},W^{\left(2\right)},\dots ,W^{\left(m\right)}\right\}$. Assume $W^{\left(m\right)}$ is constructed for $m=\mathrm{0,1,2},\dots$

  • Update the auxiliary variable $Z^{\left(m+1\right)}$ satisfying ${\sum }_{i_k\in C_k}{z}_{{\mathit{ki}}_k}=0$:

  • * $z_{{\mathit{ki}}_k}^{\left(m+1\right)}={\left(w^{\left(m\right)}\right)}_k^T{x}_{i_k}-\frac{1}{\left|C_k\right|}{\sum }_{i_k\in C_k}{\left(w^{\left(m\right)}\right)}_k^T{x}_{i_k}.$

  • Perform the SVD decomposition on $\left[{\sum }_{i_1\in C_1}{z}_{1i_1}^{\left(m+1\right)}{x}_{i_1},\dots ,{\sum }_{i_k\in C_k}{z}_{{\mathit{ki}}_k}^{\left(m+1\right)}{x}_{i_k}\right]$ to get $U^{\left(m+1\right)}{S}^{\left(m+1\right)}{\left(V^{\left(m+1\right)}\right)}^T$ where $S^{\left(m+1\right)}$ is $K\times K$.

  • $W^{\left(m+1\right)}=U^{\left(m+1\right)}{\left(V^{\left(m+1\right)}\right)}^T$, the polar decomposition.

• Loop until ${‖W^{\left(m+1\right)}-W^{\left(m\right)}‖}_{\mathcal{F}}\le \delta$.

• Output: W

5. Experimental results

5.1 Quantitative results for linear and kernel dimensionality reduction

In practice, dimensionality reduction is used in conjunction with a classification algorithm. By definition, the purpose of dimensionality reduction, as it relates to classification, is to reduce the complexity of the data while retaining discriminating information. Thus, we utilize a popular classification algorithm to analyze the performance of our proposed dimensionality reduction technique. In this section, we report the results of several experiments with dimensionality reduction combined with SVM classification. In the multi-class setting, we compare against other state-of-the-art algorithms that perform dimensionality reduction and then evaluate the performance using the multi-class one-vs-all linear SVM scheme. The classification technique uses the traditional training and testing phases, outputting the class it considers the best prediction for a given test sample. We measure the accuracy of these predictions averaged over all test sets. In Table 1, we demonstrate the effectiveness of both the sum of quadratic and absolute value functions, denoted as category quadratic space (CQS) and category absolute value space (CAS), respectively. Then, we benchmark their overall classification accuracy against several classical dimensionality reduction techniques, namely, least squares linear discriminant analysis (LS-LDA) [27], Fisher linear discriminant (MC-FLD) [19], principal component analysis (PCA) [33] and their multi-class and kernel counterparts (when applicable). In each experiment, we chose two-thirds of the data for training, and the remaining third of the samples were used for testing. The results are shown in Table 1.

Name (#Classes)	CQS	CAS	LS-LDA	PCA	MC-FLD
Vehicle (4)	53.91	53.05	76.56	55.36	76.82
Wine (3)	96.07	96.82	95.51	77.19	97.28
Iris (3)	97.55	96.88	96.11	96.77	96.77
Seeds (3)	90.39	90.79	95.15	92.53	95.79
thyroid (3)	94.02	94.08	94.02	92.57	93.92
Satellite (6)	85.30	85.20	86.38	85.45	86.52
Segmentation (7)	93.14	93.44	94.62	94.40	94.43
Vertebral (3)	84.13	82.79	81.45	80.05	81.18

Table 1.

Linear dimensionality reduction w/SVM classification.

Databases: To illustrate the performance of the methods proposed in Section 3, we conducted experiments using different publicly available data sets taken from the UCI machine learning data repository [49]. We have chosen a variety of data sets that vary in terms of class cardinality (K), samples (N), and number of features (D) to demonstrate the versatility of our approach. For a direct comparison of results, we chose the same data sets: Vehicle, Wine, Iris, Seeds, Thyroid, Satellite, Segmentation, and Vertebral Silhouettes recognition databases. More details about the individual sets are available at the respective repository sites.

We divide the results into the linear and kernel groups (as is normal practice). Table 1 shows the results for linear dimensionality reduction with SVM linear classification. All dimensionality reduction algorithms were implemented and configured with a linear SVM classifier for optimal classification results (via cross-validation). It can be seen that the category space projection scheme consistently provides a good projection for standard classification algorithms to be executed. Several of the data sets comprise only three classes, and it can be seen that the proposed method is competitive in performance and, in some instances, performs slightly better.

Also, for comparison, Table 2 reports the performance of the proposed kernel formulations followed by a linear SVM classifier. These proposed methods also achieve accuracy rates similar to their kernel counterparts with angle classification shown in Table 3.

Name (# Classes)	K-CQS	K-CAS	K-PCA	K-MC-FLD
Vehicle (4)	40.27	40.92	44.81	74.35
Wine (3)	92.95	95.63	95.95	96.88
Iris (3)	95.55	93.33	95.55	94.44
Seeds (3)	90.21	90.47	91.53	93.65
thyroid (3)	41.97	40.24	43.08	72.34
Satellite (6)	81.54	86.23	89.69	90.61
Segmentation (7)	72.96	77.24	83.01	92.43
Vertebral (3)	70.96	69.53	70.96	82.25

Table 2.

Kernel dimensionality reduction w/SVM classification.

Name (# Classes)	K-CQS-A	K-CAS-A
Vehicle (4)	67.96	68.24
Wine (3)	95.32	95.32
Iris (3)	95.55	95.18
Seeds (3)	91.79	91.79
thyroid (3)	67.90	66.79
Satellite (6)	83.33	76.29
Segmentation (7)	50.21	48.94
Vertebral (3)	77.59	77.77

Table 3.

Kernel dimensionality reduction w/angle classification.

The iterative approach in Algorithm (1) was applied to obtain an optimal orthonormal basis W (which is $D\times K$) for the category space, where D dimensional input patterns can be projected to the smaller K dimensional category space if $D>K$. We start with a set of N labeled, input vectors $x_i\in {\mathbf{R}}^D$ drawn randomly from multiple classes $C_k,k\in \left\{1,\dots ,K\right\}$. The optimization technique searches over Steifel manifold elements, as explained above. The algorithm is terminated when the Frobenius norm difference between iterations, $\parallel W^{\left(m-1\right)}-W^{\left(m\right)}{\parallel }_F\le \delta$ (with $\delta ={10}^{-8}$). Once we have determined the optimal W, the patterns are mapped to the category space by the transformation $y_i=W^T{x}_i$ to obtain the corresponding set of N samples $y_i\in {\mathbf{R}}^K$, where K is the reduced dimensional space.

The results above show that our proposed methods lead to classification rates that can be compared to classical approaches. However, the main focus of this work is to provide an algorithm that retains important classification information while introducing a geometry (category vector subspace) with attractive semantic and visualization properties. The results suggest that our classification results are competitive with other techniques while learning a category space.

5.2 Visualization of kernel dimensionality reduction

Another valuable aspect of this research can be seen in the kernel formulation, which demonstrates the warping of the projected patterns toward their respective category axes. This suggests a geometric approach to classification, i.e., we could consider the angle of deviation of a test set pattern from each category axis to measure class membership. Within the category space, a base category is represented by the bases (axes) that define the category space. Class membership is, therefore, inversely proportional to the angle between the pattern and the respective category axis. Figures 1 through 3 illustrate the warped space for various three class problems, for a variation in the width parameter $\left(\sigma \right)$ of a Gaussian radial basis function kernel in the range $\sigma =\left[\mathrm{0.1,0.8}\right]$. Note the improved visualization semantics of the category space approach when compared to the other dimensionality reduction techniques.

Figure 1.

Reduced dimensionality projection for a medium σ value: From top to bottom: Row 1: Vertebral, Row 2: Thyroid, Row 3: Wine, Row 4: Iris, Row 5: Seeds.

Figure 2.

Reduced dimensionality projection for a small σ value. From top to bottom: Row 1: Vertebral, Row 2: Thyroid, Row 3: Wine, Row 4: Iris, Row 5: Seeds.

Figure 3.

Reduced dimensionality projection for a large σ value. From top to bottom: Row 1: Vertebral, Row 2: Thyroid, Row 3: Wine, Row 4: Iris, Row 5: Seeds.

6. Conclusions

In this work, we presented a new approach to supervised dimensionality reduction—that attempts to learn orthogonal category axes during training. The motivation for this work stems from the observation that the semantics of the multi-class Fisher linear discriminant are unclear, especially w.r.t. defining a space for the categories (classes). Beginning with this observation, we designed an objective function comprising sums of quadratic and absolute value functions (aimed at maximizing the inner product between each training set pattern and its class axes) with Stiefel manifold constraints (since the category axes are orthonormal). It turns out that recent work has characterized such problems and provided sufficient conditions for the detection of global minima (despite the presence of non-convex constraints). The availability of a straightforward Stiefel manifold optimization algorithm tailored to this problem (which has no step size parameters to estimate) is an attractive by-product of this formulation. The extension to the kernel setting is entirely straightforward. Since the kernel dimensionality reduction approach warps the patterns toward orthogonal category axes, this raises the possibility of using the angle between each pattern and the category axes as a classification measure. We conducted experiments in the kernel setting and demonstrated reasonable performance for the angle-based classifier, suggesting a new avenue for future research. Finally, visualization of dimensionality reduction for three classes showcases the category space geometry with clear semantic advantages over standard principal components and multi-class Fisher.

Several opportunities exist for future research. We notice a clustering of patterns near the origin of the category space, clearly calling for an origin margin (as in support vector machines) [43]. At the same time, we can also remove the orthogonality assumption (in the linear case) while continuing to pursue multi-class discrimination. Finally, extensions to the multi-label case [42] are warranted and suggest interesting opportunities for future work.

Additional information

An earlier version of this chapter was previously published as a preprint in: 1. Smith AO, Rangarajan A. A Category Space Approach to Supervised Dimensionality Reduction [Internet]. arXiv.org. 2016 [cited 2023 Sep 5]. Available from: https://arxiv.org/abs/1610.08838

Nomenclature

Name	Description
PCA	principal component analysis
SVM	support vector machine
FLD	Fisher linear discriminant
CCA	canonical correlation analysis
PLS	partial least squares
SPCA	supervised PCA
RKHS	reproducing Kernel Hilbert space
KKT	Karush-Kuhn-Tucker
CQS	category quadratic space
CAS	category absolute value space
LS-LDA	least squares linear discriminant analysis
MC-FLD	multi-class Fisher linear discriminant
K-CQS	kernel category quadratic space
K-CAS	kernel category absolute value space
K-PCA	kernel principal component analysis
K-MC-FLD	kernel multi-class Fisher linear discriminant
K-CQS-A	kernel CQS w/angle classification
K-CAS-A	kernel CAS w/angle classification