Abstract
We derive a novel sparse version of Kernel Fisher Discriminant Analysis (KFDA) using an approach based on Matching Pursuit (MP). We call this algorithm Matching Pursuit Kernel Fisher Discriminant Analysis (MPKFDA). By focusing on a small subset of the data, the algorithm remains competitive with standard methods on normal datasets while significantly outperforming SVMs and full KFDA in extremely high-dimensional scenarios.
1. Introduction
Kernel Fisher Discriminant Analysis (KFDA) is a powerful tool for classification and dimensionality reduction. However, it faces a significant challenge in large-scale applications: like many kernel methods, it typically requires storing and processing a kernel matrix that grows quadratically with the number of training samples ($m \times m$). This makes it computationally expensive and memory-intensive for large datasets.
While previous research has explored low-rank approximations, this paper seeks to impose dual sparsity. The goal is to identify a very small number of "basis vectors"—representative data points—that can capture the entire dataset's structure without losing classification accuracy.
2. Methodology
The proposed Matching Pursuit Kernel Fisher Discriminant Analysis (MPKFDA) builds the classifier iteratively through a greedy strategy:
- Greedy Selection: Instead of using all data points simultaneously, the algorithm selects one data point (an "atom") at a time that maximizes the Fisher Discriminant ratio.
- Deflation: Once a point is selected, the algorithm "deflates" the kernel matrix by projecting the remaining data into a space orthogonal to the points already chosen. This ensures that subsequent selections provide new, non-redundant information.
- Nyström Approximation: The method leverages the Nyström technique to operate in a lower-dimensional subspace ($k \ll m$), where $k$ represents the number of iterations or basis vectors.
- Theoretical Guarantees: The authors derive new generalization error bounds by combining "sample compression" theory with Robust Minimax analysis.
3. Experimental Evaluation
The researchers evaluated MPKFDA against standard KFDA and Support Vector Machines (SVM) across two distinct categories of datasets.
3.1 Standard Benchmarks
On 13 standard benchmark datasets (e.g., Banana, Breast Cancer, Diabetes), MPKFDA performed almost identically to full KFDA and remained highly competitive with SVMs.
3.2 High-Dimensional Scenarios
The algorithm's strengths were most evident in high-dimensional datasets from the NIPS 2003 challenge: ARCENE (10,000 features), DEXTER (20,000 features), and DOROTHEA (100,000 features). In these cases, the number of features vastly exceeds the number of samples.
On the Dorothea dataset (100k features), MPKFDA achieved an error of 0.0571 using only 11 basis vectors, significantly outperforming KFDA (0.0971) and SVM (0.0686). Across all high-dimensional tasks, the mean error for MPKFDA was 0.1057, compared to 0.1368 for KFDA and 0.1340 for SVM.
4. Discussion and Future Work
Sparsity in MPKFDA acts as a form of regularization. By forcing the model to choose only a few "atoms," it avoids overfitting to noise in high-dimensional spaces. Furthermore, because the final model depends on only $k$ basis vectors, test-time evaluation is highly efficient, requiring only $k$ kernel calculations. In experiments, $k$ was often 10–70 times smaller than the total number of training samples $m$. Additionally, unlike SVMs, MPKFDA naturally provides conditional probabilities, which are valuable for assessing prediction confidence.
Despite these advantages, the training process remains computationally demanding, with each greedy step requiring $O(m^3)$ computations. Future work will focus on developing faster approximations for the selection step and extending the framework to multi-class classification problems.
Summary updated