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.     

Modified linear discriminant analysis

In this paper, a modified Fisher linear discriminant analysis (FLDA) is proposed and aims to not only overcome the rank limitation of FLDA, that is, at most only finding a discriminant vector for 2-class problem based on Fisher discriminant criterion, but also relax singularity of the within-class scatter matrix and finally improves classification performance of FLDA. Experiments on nine publicly available datasets show that the proposed method has better or comparable performance on all the datasets than FLDA.     

Laplacian linear discriminant analysis

A novel linear discriminant criterion function is proved to be equal to Fisher's criterion function. The analysis of the function is linked to spectral decomposition of the Laplacian of a graph. Moreover, the function is maximized using two algorithms. Experimental results show the effectiveness and some specific characteristics of our algorithms.     

Regularized orthogonal linear discriminant analysis

In this paper the regularized orthogonal linear discriminant analysis (ROLDA) is studied. The major issue of the regularized linear discriminant analysis is to choose an appropriate regularization parameter. In existing regularized linear discriminant analysis methods, they all select the “best” regularization parameter from a given parameter candidate set by using cross-validation for classification. An obvious limitation of such regularized linear discriminant analysis methods is that it is not clear how to choose an appropriate candidate set. Therefore, up to now, there is no concrete mathematical theory available in selecting an appropriate regularization parameter in practical applications of the regularized linear discriminant analysis. The present work is to fill this gap. Here we derive the mathematical relationship between orthogonal linear discriminant analysis and the regularized orthogonal linear discriminant analysis first, and then by means of this relationship we find a mathematical criterion for selecting the regularization parameter in ROLDA and consequently we develop a new regularized orthogonal linear discriminant analysis method, in which no candidate set of regularization parameter is needed. The effectiveness of our proposed regularized orthogonal linear discriminant analysis is illustrated by some real-world data sets.     

Robot visual servoing with iterative learning control

This paper presents an iterative learning scheme for vision-guided robot trajectory tracking. First, a stability criterion for designing iterative learning controller is proposed. It can be used for a system with initial resetting error. By using the criterion, one can convert the design problem into finding a positive definite discrete matrix kernel and a more general form of learning control can be obtained. Then, a three-dimensional (3D) trajectory tracking system with a single static camera to realize robot movement imitation is presented based on this criterion.     

Bayes optimality in linear discriminant analysis

We present an algorithm which provides the one-dimensional subspace where the Bayes error is minimized for the C class problem with homoscedastic Gaussian distributions. Our main result shows that the set of possible one-dimensional spaces v, for which the order of the projected class means is identical, defines a convex region with associated convex Bayes error function g(v). This allows for the minimization of the error function using standard convex optimization algorithms. Our algorithm is then extended to the minimization of the Bayes error in the more general case of heteroscedastic distributions. This is done by means of an appropriate kernel mapping function. This result is further extended to obtain the d-dimensional solution for any given d, by iteratively applying our algorithm to the null space of the (d - 1)-dimensional solution. We also show how this result can be used to improve up on the outcomes provided by existing algorithms, and derive a low-computational cost, linear approximation. Extensive experimental validations are provided to demonstrate the use of these algorithms in classification, data analysis and visualization.     

Contextual constraints based linear discriminant analysis

Linear feature extraction methods such as LDA have achieved great success in pattern recognition and image processing area. For most existing methods, the image data is usually transformed into a vector representation and the contextual information among pixels is not exploited. However, image data distribute sparsely in high-dimension feature space and the dependence among neighboring pixels is important to represent a natural image. Therefore, in this paper, we propose a novel image contextual constraint based linear discriminant analysis (CCLDA) method by taking into account the pixel dependence of an image in subspace learning process. In this way, a more discriminative subspace could be learned especially in the case of small sample size. Extensive experiments on ORL, Extended Yale-B, PIE and FRGC databases validate the efficacy of the proposed method.     

Digital iterative learning control of linear multivariable plants

It is shown that digital iterative learning controllers can be designed for linear multivariable plants using only the step-response matrices of such plants. This demonstration is effected by proving a fundamental theorem which establishes precise sufficient conditions under which iterative learning control is achieved by such digital controllers. These general results are illustrated by the presentation of numerical results for the digital iterative learning control of a third-order linear multivariable plant with two inputs and two outputs.     

An iterative nonlinear discriminant analysis program: IDA 1.0

A Fortran 77 package of an iterated discriminant analysis multi-background and signal recognition, IDA 1.0, is presented. The primary target is the high energy physics community, but it is general enough to be used in many classification application areas. The package can easily be used as is or may readily be modified for alternative purposes and optimizations.     

Fast and accurate text classification via multiple linear discriminant projections

Support vector machines (SVMs) have shown superb performance for text classification tasks. They are accurate, robust, and quick to apply to test instances. Their only potential drawback is their training time and memory requirement. For n training instances held in memory, the best-known SVM implementations take time proportional to n^a, where a is typically between 1.8 and 2.1. SVMs have been trained on data sets with several thousand instances, but Web directories today contain millions of instances that are valuable for mapping billions of Web pages into Yahoo!-like directories. We present SIMPL, a nearly linear-time classification algorithm that mimics the strengths of SVMs while avoiding the training bottleneck. It uses Fisher's linear discriminant, a classical tool from statistical pattern recognition, to project training instances to a carefully selected low-dimensional subspace before inducing a decision tree on the projected instances. SIMPL uses efficient sequential scans and sorts and is comparable in speed and memory scalability to widely used naive Bayes (NB) classifiers, but it beats NB accuracy decisively. It not only approaches and sometimes exceeds SVM accuracy, but also beats the running time of a popular SVM implementation by orders of magnitude. While describing SIMPL, we make a detailed experimental comparison of SVM-generated discriminants with Fisher's discriminants, and we also report on an analysis of the cache performance of a popular SVM implementation. Our analysis shows that SIMPL has the potential to be the method of choice for practitioners who want the accuracy of SVMs and the simplicity and speed of naive Bayes classifiers.Received: 9 September 2002, Accepted: 3 March 2003, Published online: 21 July 2003 Edited by Y. Ioannidis     

Genetic algorithms in norm-optimal linear and non-linear iterative learning control

In this paper it is analysed whether or not it is possible to apply the norm-optimal iterative learning control algorithm to non-linear plant models. As a new theoretical result it is shown that if the non-linear plant meets a certain technical invertibility condition, the sequence of tracking errors generated by the norm-optimal algorithm will converge geometrically to zero. However, due to the non-linear nature of the plant, it is typically impossible to calculate analytically the sequence of input functions produced by the norm-optimal algorithm. Therefore it is proposed that genetic algorithms can be used as a computational tool to calculate the sequence of norm-optimal inputs. The proposed approach benefits from the design of a low-pass FIR filter. This filter successfully removes unwanted high frequency components of the input signal, which are generated by the genetic algorithm method due to the random nature of the genetic algorithm search. Simulations are used to illustrate the performance of this new approach, and they demonstrate good results in terms of convergence speed and tracking of the reference signal regardless of the nature of the plant.     

基于线性判别分析的特征选择

提出一种新颖的基于特征抽取的特征选择方法,将特征选择问题建模为在子空间中的搜索问题,采用线形判别分析(LDA)的投影思想,对LDA施加一定的限制将其转换为对子空间的搜索优化问题,从而通过解LDA的优化问题得到特征选择的解,进一步把特征选择问题推导简化为对特征的评分和排序过程.通过在UCI机器学习库和Reuters-21578文本数据集上的实验,验证了该方法以较少的特征获得了比全部特征更好的分类结果.     

Cross-media retrieval based on linear discriminant analysis

Multimedia Tools and Applications - Existing cross-media retrieval approaches usually project low-level features from different modalities of data into a common subspace, in which the similarity of...     

Geometric linear discriminant analysis for pattern recognition

We propose an innovative technique, geometric linear discriminant analysis (Geometric LDA), to reduce the complexity of pattern recognition systems by using a linear transformation to lower the dimension of the observation space. We experimentally compare Geometric LDA to other dimensionality reduction methods found in the literature. We show that Geometric LDA produces the same and in many cases a significantly better linear transformation than other methods found in the literature.     

Sparse L1-norm-based linear discriminant analysis

Linear discriminant analysis (LDA) is a well-known feature extraction method, which has been widely used for many pattern recognition problems. However, the objective function of conventional LDA is based on L2-norm, which makes LDA sensitive to outliers. Besides, the basis vectors learned by conventional LDA are dense and it is often hard to explain the extracted features. In this paper, we propose a novel sparse L1-norm-based linear discriminant analysis (SLDA-L1) which not only replaces L2-norm in conventional LDA with L1-norm, but also use the elastic net to regularize the basis vectors. Then L1-norm used in SLDA-L1 is for both robust and sparse modelling simultaneously. We also propose an efficient iterative algorithm to solve SLDA-L1 which is theoretically shown to arrive at a locally maximal point. Experiment results on some image databases demonstrate the effectiveness of the proposed method.     

Monotonically convergent iterative learning control for linear discrete-time systems

In iterative learning control schemes for linear discrete time systems, conditions to guarantee the monotonic convergence of the tracking error norms are derived. By using the Markov parameters, it is shown in the time-domain that there exists a non-increasing function such that when the properly chosen constant learning gain is multiplied by this function, the convergence of the tracking error norms is monotonic, without resort to high-gain feedback.     

Digital iterative learning control of compensated linear multivariable plants

It is shown that digital iterative learning controllers can be designed for irregular linear multivariable plants by introducing appropriate digital compensators. This demonstration is effected by proving a fundamental theorem which establishes precise sufficient conditions under which iterative learning control is achieved by such digital controllers and compensators in the case of first-order irregular plants. These general results are illustrated by the presentation of numerical results for the digital iterative learning control of a third-order partially irregular plant with two inputs and two outputs. The extension of the results to higher-order irregular plants is discussed.     

Combining linear discriminant functions with neural networks for supervised learning

A novel supervised learning method is proposed by combining linear discriminant functions with neural networks. The proposed method results in a tree-structured hybrid architecture. Due to constructive learning, the binary tree hierarchical architecture is automatically generated by a controlled growing process for a specific supervised learning task. Unlike the classic decision tree, the linear discriminant functions are merely employed in the intermediate level of the tree for heuristically partitioning a large and complicated task into several smaller and simpler subtasks in the proposed method. These subtasks are dealt with by component neural networks at the leaves of the tree accordingly. For constructive learning, growing and credit-assignment algorithms are developed to serve for the hybrid architecture. The proposed architecture provides an efficient way to apply existing neural networks (e.g. multi-layered perceptron) for solving a large scale problem. We have already applied the proposed method to a universal approximation problem and several benchmark classification problems in order to evaluate its performance. Simulation results have shown that the proposed method yields better results and faster training in comparison with the multilayered perceptron.     

Fast linear discriminant analysis using binary bases

Linear Discriminant Analysis (LDA) is a widely used technique for pattern classification. It seeks the linear projection of the data to a low dimensional subspace where the data features can be modelled with maximal discriminative power. The main computation in LDA is the dot product between LDA base vector and the data point which involves costly element-wise floating point multiplications. In this paper, we present a fast linear discriminant analysis method called binary LDA (B-LDA), which possesses the desirable property that the subspace projection operation can be computed very efficiently. We investigate the LDA guided non-orthogonal binary subspace method to find the binary LDA bases, each of which is a linear combination of a small number of Haar-like box functions. We also show that B-LDA base vectors are nearly orthogonal to each other. As a result, in the non-orthogonal vector decomposition process, the computationally intensive pseudo-inverse projection operator can be approximated by the direct dot product without causing significant distance distortion. This direct dot product projection can be computed as a linear combination of the dot products with a small number of Haar-like box functions which can be efficiently evaluated using the integral image. The proposed approach is applied to face recognition on ORL and FERET dataset. Experiments show that the discriminative power of binary LDA is preserved and the projection computation is significantly reduced.