Linear-Time Multivariate Unsupervised Feature Selection Using Nyström-Based Entropy Approximation

Unsupervised feature selection seeks to identify informative, nonredundant features without using class labels. Motivated by Fano’s inequality, we use the entropy of the selected feature subset as a task-agnostic heuristic for its information capacity. Because multivariate joint entropy is difficult to estimate and exact evaluation of all pairwise joint entropies is computationally costly, we propose a landmark-based block approximation inspired by the Nyström method. Features with high marginal entropy are selected as landmarks. Joint entropy is computed exactly for pairs involving at least one landmark, while non-landmark pairs are approximated in constant time per pair using the geometric mean of their marginal entropies. We establish deterministic bounds for the surrogate and incorporate the resulting hybrid estimator into an incremental feature selection strategy. Experiments on 25 public benchmark datasets show that the proposed method achieves the lowest average rank across eight evaluation metrics. It exhibits significant advantages over most baselines on information-preservation metrics while maintaining competitive classification and clustering performance.