.png){kind=icon}
.png){kind=icon}
Return
Efficient Approximations for Matrix-Based Renyi's Entropy on Sequential Data
.png){kind=icon}
PRE
AI
DOI：10.1109/TNNLS.2023.3314089.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Information theory
matrix-based Renyi's entropy (MBRE)
randomized numerical linear algebra
signal processing
Journal
IF:
8.9
Papers:
7.5K
Citations:
7.2W