Max-K-Min Distance Analysis for Dimension Reduction

We propose a new criterion for discriminative dimension reduction, Max-K-Min Distance Analysis (MKMDA). Given a data set with C classes, MKMDA maximizes the sum of the K minimum pair wise distance of these C classes on the selected one-dimensional subspace. The set of the possible one-dimensional subspace, for which the order of the projected class centroids is identical, define a convex region with associated convex sum of K smallest margin functions. This allows for the maximization of the margin function using standard convex optimization algorithms. This result is further extended to obtain the d-dimensional subspace for any given d by iterative applying our algorithm to the null space of the (d -- 1)-dimensional subspace. The effectiveness of the proposed criterion and corresponding algorithm is shown by the visualization and classification experiments on both synthetic data and real data sets.