Recursive “concave–convex” Fisher Linear Discriminant with applications to face, handwritten digit and terrain recognition

摘要

In classification, previous studies have shown that an eigenvalue based technique can be cast as an related SVM-type problem and that by solving this SVM-type problem, the performance can be improved significantly. In this paper, we develop a recursive “concave–convex” Fisher Linear Discriminant (DR) (RPFLD) for dimension reduction technique of high-dimensional data to extract as many meaningful features as possible, which incorporates the fundamental idea behind Fisher Linear Discriminant and casts the Fisher Linear Discriminant as a “concave–convex” programming problem based on the hinge loss. The solution of our method follows from solving the related SVM-type optimization problems iteratively, which means the proposed method, can be viewed as the combination of multiple related SVM-type problems. The special formulation of our method provides convenience for constructing sparse multi-class Fisher Linear Discriminant directly. Due to use of a recursive procedure, the number of features available from RPFLD is independent of the number of classes, meaning that in contrast to the original Fisher Linear Discriminant the number of features available from our method has no upper bound. We evaluate our algorithm on the Yale, and ORL face image databases, handwritten digit database and Terrain image dataset. Experimental results show that RPFLD outperforms other Fisher Linear Discriminant algorithms.