A study of the generalized eigenvalue decomposition in discriminant analysis

The well-known Linear Discriminant Analysis (LDA) approach to feature extraction in classification problems is typically formulated using a generalized eigenvalue decomposition, S ₁V=S ₂VΛ, where S ₁and S ₂are two symmetric, positive-semidefinite matrices defining the meature to be maximized and that to be minimized. Most of the LDA algorithms developed to date are based on tuning one of these two matrices to solve a specific problem. However, the search for a set of metrices that can be applied to a large number of problems has met difficulty. In this thesis, we take the view that most of these problems are caused by the use of the generalized eigenvalue decomposition equation described above. Further,we augue that many of these problems can be solved by studying and modifying this basic equation. At the core of this thesis lays a new factorization of S ₂ ^-1S ₁that can be used to resolve several of the problems of LDA.

Three novel algorithms are derived, each based on our proposed factorization. In the first algorithm, we define a criterion to prune noisy bases in LDA. This is possible thanks to the flexibility of our factorization, which allows the suppression of a set of vectors of any metric. The second algorithm is called Subclass Discriminant Analysis (SDA). SDA can be applied to a large variety of distribution types because it approximates the underlying distribution of each class with a mixture of Gaussians. The most convenient number of Gaussians can be readily selected thanks to our proposed factorization. The third algorithm is aimed to address the over-fitting issue in LDA. A direct application of this algorithm is tumor classification, where the ratio of samples versus features is very small. The main idea of the proposed algorithm is to take advantage of the information embedded in the testing samples - changing the role of testing data from passive to active samples. In all three cases, extensive experimental results are provided using a large variety of data-sets. Comparative studies are given against the most advanced and standard methods available.