Efficient Approximations for Matrix-Based Renyi's Entropy on Sequential Data

The matrix-based Renyi's entropy (MBRE) has recently been introduced as a substitute for the original Renyi's entropy that could be directly obtained from data samples, avoiding the expensive intermediate step of density estimation. Despite its remarkable success in a broad of information-related tasks, the computational cost of MBRE, however, becomes a bottleneck for large-scale applications. The challenge, when facing sequential data, is further amplified due to the requirement of large-scale eigenvalue decomposition on multiple dense kernel matrices constructed by sliding windows in the region of interest, resulting in O(mn(3)) overall time complexity, where m and n denote the number and the size of windows, respectively. To overcome this issue, we adopt the static MBRE estimator together with a variance reduction criterion to develop randomized approximations for the target entropy, leading to high accuracy with substantially lower query complexity by utilizing the historical estimation results. Specifically, assuming that the changes of adjacent sliding windows are bounded by beta << 1, which is a trivial case in domains, e.g., time-series analysis, we lower the complexity by a factor of root beta. Polynomial approximation techniques are further adopted to support arbitrary alpha orders. In general, our algorithms achieve O(mn(2) root beta st) total computational complexity, where s, t << n denote the number of vector queries and the polynomial degrees, respectively. Theoretical upper and lower bounds are established in terms of the convergence rate for both s and t, and large-scale experiments on both simulation and real-world data are conducted to validate the effectiveness of our algorithms. The results show that our methods achieve promising speedup with only a trivial loss in performance.

Automated summary

The matrix-based Renyi's entropy (MBRE) is introduced as a substitute for original Renyi's entropy, avoiding the costly density estimation step. To overcome the computational cost issue in large-scale applications, the study proposes a static MBRE estimator combined with a variance reduction criterion to develop randomized approximations for the target entropy, achieving high accuracy with lower query complexity by utilizing historical estimation results.