Linear-Time Multivariate Unsupervised Feature Selection Using Nyström-Based Entropy Approximation
- 1Department of Artificial Intelligence, Chung-Ang University, Seoul 06974, Republic of Korea
- 2Division of AI Computer Science and Engineering, Kyonggi University, Suwon 16227, Republic of Korea
Abstract
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.
Related
- HLR-UFS: Hessian-based Unsupervised Feature Selection using Low-Rank Approximation
- A multivariate unsupervised lognormal-GPD mixture for dependent losses
- Approximation theory of tree tensor networks: tensorized multivariate functions
- Data-driven Random-feature Approximation of Koopman Generators of Nonlinear Continuous-time Systems
- Data-driven approximation of regions of attraction via an LP-based selection of PWA Lyapunov functions
BibTeX
@article{kim2026lineartime,
title = {{Linear-Time Multivariate Unsupervised Feature Selection Using Nyström-Based Entropy Approximation}},
author = {Gyu-Il Kim and Timur Khairulov and Wangduk Seo and Jaesung Lee},
journal = {Mathematics},
year = {2026},
month = nov,
doi = {10.3390/math14214057},
url = {https://www.mdpi.com/2227-7390/14/21/4057},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Linear-Time Multivariate Unsupervised Feature Selection Using Nyström-Based Entropy Approximation
AU - Gyu-Il Kim
AU - Timur Khairulov
AU - Wangduk Seo
AU - Jaesung Lee
PY - 2026
DA - 2026/11/05
JO - Mathematics
DO - 10.3390/math14214057
UR - https://www.mdpi.com/2227-7390/14/21/4057
AB - 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.
SN - 2227-7390
ER -