Nyström-aware approximations for matrix-based Rényi's entropy

The matrix-based Rényi's α-order entropy, a powerful tool in information-theoretical learning, offers a direct computation from empirical data without requiring knowledge of the underlying probability density function (PDF). However, its exact computation incurs a prohibitive time complexity O(n³), where n is the number of observed samples, making it impractical for modern large-scale machine-learning tasks. In response to this challenge, we propose Nyström-aware approximation strategies built upon the widely used sketching techniques for arbitrary α-order matrix-based Rényi's entropy functional, reducing the time complexity to O(n² s), where s ≪ n is the number of queried randomized vectors. Compared to the recently developed Hutch++-based approximations, our approaches require fewer passes over the input symmetric positive semi-definite matrix A∈R^n×n, hence enjoying substantially higher computational efficiency without sacrificing accuracy or reliability, while also enabling potential parallelism. Our quality-of-approximation results reveal that its query complexity is optimal up to a logarithmic factor w.r.t. the approximation error. Extensive simulations and information-theoretical learning tasks corroborate the superior performance of our proposed approximation over Hutch++-based approaches in terms of computational efficiency.