A two-stage linear discriminant analysis via QR-decomposition

Linear discriminant analysis (LDA) is a well-known method for feature extraction and dimension reduction. It has been used widely in many applications involving high-dimensional data, such as image and text classification. An intrinsic limitation of classical LDA is the so-called singularity problems; that is, it fails when all scatter matrices are singular. Many LDA extensions were proposed in the past to overcome the singularity problems. Among these extensions, PCA+LDA, a two-stage method, received relatively more attention. In PCA+LDA, the LDA stage is preceded by an intermediate dimension reduction stage using principal component analysis (PCA). Most previous LDA extensions are computationally expensive, and not scalable, due to the use of singular value decomposition or generalized singular value decomposition. In this paper, we propose a two-stage LDA method, namely LDA/QR, which aims to overcome the singularity problems of classical LDA, while achieving efficiency and scalability simultaneously. The key difference between LDA/QR and PCA+LDA lies in the first stage, where LDA/QR applies QR decomposition to a small matrix involving the class centroids, while PCA+LDA applies PCA to the total scatter matrix involving all training data points. We further justify the proposed algorithm by showing the relationship among LDA/QR and previous LDA methods. Extensive experiments on face images and text documents are presented to show the effectiveness of the proposed algorithm.     

一种两阶段判别分析方法

为了解决LDA 对复杂分布数据的表达问题,本文提出了一种新的非参数形式的散度矩阵构造方法。该方法 能更好的刻画分类边界信息,并保留更多对分类有用的信息。同时针对小样本问题中非参数结构形式的类内散度矩阵可能奇 异,提出了一种两阶段鉴别分析方法对准则函数进行了最优化求解。该方法通过奇异值分解把人脸图像投影到混合散度矩阵 的主元空间,使类内散度矩阵在投影空间中是非奇异的,通过CS 分解,从理论上分析了同时对角化散度矩阵的求解,并证明了 得到的投影矩阵满足正交约束条件。在ORL,Yale 和YaleB 人脸库上测试的结果显示,改进的算法在性能上优于PCA+LDA, ULDA 和OLDA 等子空间方法。     

利用标准化LDA进行人脸识别

线性判别分析（LDA）是一种较为普遍的用于特征提取的线性分类方法。提出一种基于LDA的人脸识别方法－－标准化LDA，该方法克服了传统LDA方法的缺点，重新定义了样本类间离散度矩阵，在原始定义的基础上增加一个由类间距离决定的可变权函数，使得在选择投地，能够更好地分开各个类的样本；同时，它采用一种合理而有效的方法解决矩阵奇异的问题，即保留样本类内离散度矩阵的零空间，因为这个空间包含了最具有判别能力的信息。在这个零空间里，寻找对应于样本类间离散度矩阵的较大特征值的特征向量作为最后降维的转换矩阵。实验结果显示，在人脸识别中，与传统LDA相比，该方法有更好的识别率。标准化LDA也可以用于其他图像识别问题。     

一种适用于小样本问题的基于边界的特征提取算法

特征提取技术是模式识别领域进行数据降维和强化判别信息的有效方法.线性判别分析是监督特征提取方法的典型代表,获得广泛应用,但受到小样本问题的制约.对此提出一种适用于小样本问题的基于边界的特征提取算法.算法利用高维数据小样本情况下线性可分概率增加以及其低维投影趋于正态分布的特点,定义了新的类别边界,不但考虑了由线性判别分析提出的类内、类间离散度,也兼顾各类别的方差差异性.通过极大化该边界获得最优投影向量,同时避免因类内离散度矩阵奇异导致的小样本问题.进一步将算法推广到多类问题.高光谱数据特征提取与分类实验表明,算法在小样本情况下对于两类和多类问题均具有良好的推广性能,优于多种线性判别分析的改进算法,并且在样本较多时也取得了满意结果.     

改进的基于Gabor-LDA的人脸识别方法

鉴于Gabor特征对光照、表情等变化比较鲁棒,并已在人脸识别领域取得成功应用,提出了一种改进的Gabor-LDA算法.首先对人脸图像进行多方向、多尺度Gabor小渡滤波,然后对得到的特征向量使用改进的主成分分析方法(PCA)变换降维,采用自适应加权原理重建类内散布矩阵和类间散布矩阵,从而改进了最佳鉴别分析(LDA)判别函数,有效地解决了训练样本类均值与类中心的偏离问题.对Yale人脸库的数值试验表明,该算法比传统算法有更好的性能.     

一种可调控制参数的LDA人脸识别算法

线性判别分析（LDA）方法进行高维的人脸识别时,经常会遇到小样本问题（SSS）和边缘类重叠问题。本文提出一种新的LDA方法,重新定义类内离散度矩阵,利用参数来权衡其特征值估计的偏差和方差,以解决小样本问题;对类间离散矩阵加权,让边缘类均匀分布,防止边缘类的重叠,以提高识别率。大量的实验已经证明该方法能根据小样本问题的严重度调控参数以达到最高识别率,比传统的方法更优。     

基于二值数据贝叶斯子空间的人脸识别算法

基于贝叶斯空间的人脸识别算法均假定样本空间满足高斯分布,实际上样本空间很复杂,不一定能满足高斯分布。提出一种新的在贝叶斯空间进行人脸识别的算法,该算法通过设定图像灰度级的阈值,统计其出现频率,计算其类条件概率密度,利用贝叶斯公式求后验概率。该方法克服了传统贝叶斯方法难求类内和类间协方差矩阵的缺点,简单易用。实验结果证明,该方法具有可行性,识别率高于传统的基于代数的人脸识别算法(PCA、LDA和PCA+LDA)。     

A comparison of generalized linear discriminant analysis algorithms

Linear discriminant analysis (LDA) is a dimension reduction method which finds an optimal linear transformation that maximizes the class separability. However, in undersampled problems where the number of data samples is smaller than the dimension of data space, it is difficult to apply LDA due to the singularity of scatter matrices caused by high dimensionality. In order to make LDA applicable, several generalizations of LDA have been proposed recently. In this paper, we present theoretical and algorithmic relationships among several generalized LDA algorithms and compare their computational complexities and performances in text classification and face recognition. Towards a practical dimension reduction method for high dimensional data, an efficient algorithm is proposed, which reduces the computational complexity greatly while achieving competitive prediction accuracies. We also present nonlinear extensions of these LDA algorithms based on kernel methods. It is shown that a generalized eigenvalue problem can be formulated in the kernel-based feature space, and generalized LDA algorithms are applied to solve the generalized eigenvalue problem, resulting in nonlinear discriminant analysis. Performances of these linear and nonlinear discriminant analysis algorithms are compared extensively.     

An optimal symmetrical null space criterion of Fisher discriminant for feature extraction and recognition

Linear discriminant analysis (LDA) is one of the most effective feature extraction methods in statistical pattern recognition, which extracts the discriminant features by maximizing the so-called Fisher’s criterion that is defined as the ratio of between-class scatter matrix to within-class scatter matrix. However, classification of high-dimensional statistical data is usually not amenable to standard pattern recognition techniques because of an underlying small sample size (SSS) problem. A popular approach to the SSS problem is the removal of non-informative features via subspace-based decomposition techniques. Motivated by this viewpoint, many elaborate subspace decomposition methods including Fisherface, direct LDA (D-LDA), complete PCA plus LDA (C-LDA), random discriminant analysis (RDA) and multilinear discriminant analysis (MDA), etc., have been developed, especially in the context of face recognition. Nevertheless, how to search a set of complete optimal subspaces for discriminant analysis is still a hot topic of research in area of LDA. In this paper, we propose a novel discriminant criterion, called optimal symmetrical null space (OSNS) criterion that can be used to compute the Fisher’s maximal discriminant criterion combined with the minimal one. Meanwhile, by the reformed criterion, the complete symmetrical subspaces based on the within-class and between-class scatter matrices are constructed, respectively. Different from the traditional subspace learning criterion that derives only one principal subspace, in our approach two null subspaces and their orthogonal complements were all obtained through the optimization of OSNS criterion. Therefore, the algorithm based on OSNS has the potential to outperform the traditional LDA algorithms, especially in the cases of small sample size. Experimental results conducted on the ORL, FERET, XM2VTS and NUST603 face image databases demonstrate the effectiveness of the proposed method.     

一种改进的线性判别分析算法在人脸识别中的应用

线性判别分析算法是一种经典的特征提取方法,但其仅在大样本情况下适用。本文针对传统线性判别分析算法面临的小样本问题和秩限制问题,提出了一种改进的线性判别分析算法ILDA。该方法在矩阵指数的基础上,重新定义了类内离散度矩阵和类间离散度矩阵,有效地同时提取类内离散度矩阵零空间和非零空间中的信息。若干人脸数据库上的比较实验表明了ILDA在人脸识别方面的有效性。     

Unified formulation of linear discriminant analysis methods and optimal parameter selection

In the last decade, many variants of classical linear discriminant analysis (LDA) have been developed to tackle the under-sampled problem in face recognition. However, choosing the variants is not easy since these methods involve eigenvalue decomposition that makes cross-validation computationally expensive. In this paper, we propose to solve this problem by unifying these LDA variants in one framework: principal component analysis (PCA) plus constrained ridge regression (CRR). In CRR, one selects the target (also called class indicator) for each class, and finds a projection to locate the class centers at their class targets and the transform minimizes the within-class distances with a penalty on the transform norm as in ridge regression. Under this framework, many existing LDA methods can be viewed as PCA+CRR with particular regularization numbers and class indicators and we propose to choose the best LDA method as choosing the best member from the CRR family. The latter can be done by comparing their leave-one-out (LOO) errors and we present an efficient algorithm, which requires similar computations to the training process of CRR, to evaluate the LOO errors. Experiments on Yale Face B, Extended Yale B and CMU-PIE databases are conducted to demonstrate the effectiveness of the proposed methods.     

一种改进的线性判别分析法在人脸识别中的应用

提出了一种新的基于LDA的人脸识别算法。该方法重新定义了样本的类间散布矩阵，在原始的定义基础上增加了一种径向基函数（RBF）调节类间距离，使得在选择投影方向时能更好地分升各类样本；同时该方法存类间散布矩阵与类内散布矩阵的特征分解的基础上，通过变换求出符合Fisher准则的最优投影方向，可以证明这样得到的投影方向同时具有正交性与统计不相关性。通过ORL人脸数据库的数值实验，表明了该算法比传统算法有更好的性能。     

Tensor linear Laplacian discrimination (TLLD) for feature extraction

Discriminant feature extraction plays a central role in pattern recognition and classification. In this paper, we propose the tensor linear Laplacian discrimination (TLLD) algorithm for extracting discriminant features from tensor data. TLLD is an extension of linear discriminant analysis (LDA) and linear Laplacian discrimination (LLD) in directions of both nonlinear subspace learning and tensor representation. Based on the contextual distance, the weights for the within-class scatters and the between-class scatter can be determined to capture the principal structure of data clusters. This makes TLLD free from the metric of the sample space, which may not be known. Moreover, unlike LLD, the parameter tuning of TLLD is very easy. Experimental results on face recognition, texture classification and handwritten digit recognition show that TLLD is effective in extracting discriminative features.     

Discriminative common vectors for face recognition

In face recognition tasks, the dimension of the sample space is typically larger than the number of the samples in the training set. As a consequence, the within-class scatter matrix is singular and the linear discriminant analysis (LDA) method cannot be applied directly. This problem is known as the "small sample size" problem. In this paper, we propose a new face recognition method called the discriminative common vector method based on a variation of Fisher's linear discriminant analysis for the small sample size case. Two different algorithms are given to extract the discriminative common vectors representing each person in the training set of the face database. One algorithm uses the within-class scatter matrix of the samples in the training set while the other uses the subspace methods and the Gram-Schmidt orthogonalization procedure to obtain the discriminative common vectors. Then, the discriminative common vectors are used for classification of new faces. The proposed method yields an optimal solution for maximizing the modified Fisher's linear discriminant criterion given in the paper. Our test results show that the discriminative common vector method is superior to other methods in terms of recognition accuracy, efficiency, and numerical stability.     

最大散度差鉴别分析及人脸识别

传统的Fisher线性鉴别分析(LDA)在人脸等高维图像识别应用中不可避免地遇到小样本问题。提出一种基于散度差准则的鉴别分析方法。与LDA方法不同的是,该方法利用样本模式的类间散布与类内散布之差而不是它们的比作为鉴别准则,这样,从根本上避免了类内散布矩阵奇异带来的困难。在ORL人脸数据库和AR人脸数据库上的实验结果验证算法的有效性。     

Cancer classification by gradient LDA technique using microarray gene expression data

Cancer classification is one of the major applications of the microarray technology. When standard machine learning techniques are applied for cancer classification, they face the small sample size (SSS) problem of gene expression data. The SSS problem is inherited from large dimensionality of the feature space (due to large number of genes) compared to the small number of samples available. In order to overcome the SSS problem, the dimensionality of the feature space is reduced either through feature selection or through feature extraction. Linear discriminant analysis (LDA) is a well-known technique for feature extraction-based dimensionality reduction. However, this technique cannot be applied for cancer classification because of the singularity of the within-class scatter matrix due to the SSS problem. In this paper, we use Gradient LDA technique which avoids the singularity problem associated with the within-class scatter matrix and shown its usefulness for cancer classification. The technique is applied on three gene expression datasets; namely, acute leukemia, small round blue-cell tumour (SRBCT) and lung adenocarcinoma. This technique achieves lower misclassification error as compared to several other previous techniques.     

Kernel machine-based rank-lifting regularized discriminant analysis method for face recognition

To address two problems, namely nonlinear problem and singularity problem, of linear discriminant analysis (LDA) approach in face recognition, this paper proposes a novel kernel machine-based rank-lifting regularized discriminant analysis (KRLRDA) method. A rank-lifting theorem is first proven using linear algebraic theory. Combining the rank-lifting strategy with three-to-one regularization technique, the complete regularized methodology is developed on the within-class scatter matrix. The proposed regularized scheme not only adjusts the projection directions but tunes their corresponding weights as well. Moreover, it is shown that the final regularized within-class scatter matrix approaches to the original one as the regularized parameter tends to zero. Two public available databases, namely FERET and CMU PIE face databases, are selected for evaluations. Compared with some existing kernel-based LDA methods, the proposed KRLRDA approach gives superior performance.     

基于多子空间线性判别分析的特征提取与分类

为了解决高维小样本数据的分类中Fisherface思想判别分析方法的不足,在最大散度差准则的基础上,提出了利用多线性子空间技术对每类样本进行单独描述的方法,该方法能更准确地反映样本在类内类间的分布关系.在分类中不是以距离作为判别依据,而是按照贝叶斯决策规则得到的隶属置信度作为衡量标准.实验结果表明了该方法的有效性,和同类方法相比,有更高的识别率.     

最坏分离的联合分辨率判别分析

现实中,常需辨识低分辨率(low-resolution,简称LR)图像(如监控系统所捕捉的人脸),但相比通常的高(high-resolution,简称HR)或超(super-resolution,简称SR)分辨率图像而言,其含有相对较少的判别信息,致使通常的子空间学习算法,如结合主成分分析(principal components analysis,简称PCA)的线性判别分析(linear discriminant analysis,简称LDA)难以获得理想的识别效果.为了缓和该问题,最近所提出的联合判别分析(如SDA)借助与低分辨率相配对的高分辨率图像辅助设计LR图像分类器.在SDA的实现中,其采用了类似LDA的平均散度定义,使SDA遗传了LDA在投影时难以使相对靠近的类充分分离的问题.为了克服该不足,提出了针对LR图像识别的最坏分离的联合分辨率判别分析(worst-separated couple-resolution discriminant analysis,简称WSCR),从而使:(1) LR和HR投影到同一低维子空间;(2) 投影后的最小类间隔最大化.实验结果表明:与SDA相比,WSCR更适用于低分辨率的图像识别.     

多阶矩阵组合LDA及其在人脸识别中的应用

线性判别分析（LDA）是一种普遍用于特征提取的线性分类方法。但将LDA直接用于人脸识别会遇到小样本问题和秩限制问题。为了解决以上问题,提出一种基于多阶矩阵组合的LDA算法——MLDA。该算法重新定义了传统LDA中的类内离散度矩阵Sw,使传统Fisher准则具有更好的健壮性和适应性。若干人脸数据库上的比较实验证明了MLDA的有效性。