The Iterative Solution Of Linear Discriminant Analysis And Its Application

Linear discriminant analysis (LDA) has been successfully used as a dimensionality reduction technique to many classification problems, such as speech recognition, face recognition and information retrieval.The main idea of classical LDA is to find an optimal linear transformation such that the original date from high-dimensional space is mapped to the reduced-dimensional space. LDA computes the optimal transformation, which minimizes the within-class distance (of the data set) and maximizes the between-class distance simultaneously, thus achieving maximum discrimination.Mathematically, this is expressed as the following optimization problem(ratio trace problem): W=argmaxtr[(WTSωW)-1(WTSbW)]However, a more appropriate discrimination criterion is (trace ratio problem): W=argmaxtr(WTSbW)/tr(WTSωW)The trace ratio problem does not have a explicit closed-form global optimum so-lution. Generally, the trace ratio problem is often simplified into a more tractable ratio trace problem. The ratio trace problem can be efficiently solved with the generalized eigenvalue decomposition method.In this thesis, we study some efficient iterative procedures to directly solve the trace ratio optimization problem, namely, bisection method, iterative trace ratio(ITR), and decomposed newton’s method(DNM). We made some improvements to these methods:Firstly, it is well-known that the linear discriminant analysis often suffers from the so-called”small sample size”(SSS)problem. Consequently, the computational data arehighly dimensional. We propose a method that effectively addresses the SSS problemremoving the null space of the total scatter matrix St.Secondly, we compare these three methods against ratio trace solution to LDA.Experimental results demonstrate that the trace ratio formulation generally outperformsthe corresponding ratio trace formulation in terms of recognition rate.Thirdly, for the ITR algorithm, a starting point strategy is suggested. It can beobserved from some experiments that a good choice of initial iterative matrix makes theconvergence speed of our method improved significantly.Finally, we analyze the influence of the correlation of sample to recognition ac-curacy. We select some linear independence samples as the training set, and then therecognition rate has been improved significantly. This shows that the selection of sam-ple have a direct effect on the recognition rate.