Abstract
Kernel Density Estimation (KDE) is a vital tool for distribution modeling, yet it often suffers from high computational costs or excessive memory requirements. This paper introduces OROLS (Order-Recursive Orthogonal Least Squares), a memory-efficient algorithm for sparse KDE. By treating density estimation as a regression problem on the Empirical Cumulative Distribution Function (ECDF) and utilizing "thin" matrix updates, OROLS achieves state-of-the-art accuracy with significantly lower memory overhead and fewer model parameters than existing methods like $\epsilon$-SVD.
Introduction
Practitioners using KDE typically face a trade-off between the accuracy of dense models like Parzen Windows and the efficiency of sparse models like Gaussian Mixture Models (GMMs) or $\epsilon$-SVD. Dense models require every training sample for inference, while existing sparse models often rely on complex optimization or memory-intensive Gram matrices that scale quadratically ($O(N^2)$) with the number of samples. This paper addresses these limitations by proposing a recursive approach that minimizes memory usage while maintaining high sparsity.
Methodology
The proposed approach rests on two primary innovations: the OROLS algorithm and an enhanced ECDF sampling technique.
OROLS Algorithm
Instead of the standard approach of computing a full orthogonal decomposition of the kernel matrix, OROLS employs an order-recursive strategy. It updates the orthogonal decomposition matrices and the pseudo-inverse of the Gram matrix "on the fly" during the greedy selection of kernel centers. This "thin update" strategy allows the construction of a sparse model without ever storing the entire $N \times N$ matrix, reducing memory requirements from $O(SN + N^2)$ to approximately $O(3Sm + m^2/2)$, where $m \ll N$ is the number of selected centers.
Enhanced ECDF Sampling
Reframing density estimation as a regression on the ECDF requires evaluating the fit at specific points. "Naive" sampling at training data points often fails in multi-dimensional spaces as it misses the "staircase" jumps of the distribution. The authors implement an output-sensitive algorithm to identify additional "jump points," providing a richer target for regression.
Experimental Evaluation
The algorithm was tested on three benchmarks:
- Artificial 2D-Problem: A mixture of Gaussian and exponential distributions.
- Ripley Data Set: A classic 2D two-class classification problem (125 training samples).
- Thyroid Data Set (UCI): A 5-dimensional real-world dataset (140 training samples).
Key Results
OROLS demonstrated superior performance in both sparsity and accuracy across the test sets.
Sparsity and Accuracy on Ripley
On the Ripley dataset, OROLS with enhanced ECDF sampling achieved a lower error rate (8.5%) compared to $\epsilon$-SVD (9.8%). Crucially, it achieved this with far greater efficiency, using only 14 centers (7 per class) compared to the 128 centers required by $\epsilon$-SVD.
High-Dimensional Performance
On the 5D Thyroid dataset, OROLS consistently outperformed $\epsilon$-SVD across various sampling densities. It produced more accurate models while requiring less than one-third of the samples used by other sparse methods.
Conclusion and Future Work
While OROLS significantly improves memory efficiency and sparsity, the "Curse of Dimensionality" remains a challenge for ECDF sampling. In 5D, the number of jump points can grow combinatorially, necessitating random sub-sampling. Future research will focus on scaling the algorithm to even higher dimensions and larger datasets, such as high-dimensional speech feature vectors.
Summary updated