| 郝一菲,王颖喆.最小熵耦合问题近似解的误差估计[J].数学年刊A辑,2025,46(4):367~382 |
| 最小熵耦合问题近似解的误差估计 |
| Error Estimation for Approximate Solutions to the Minimum Entropy Coupling Problem |
| Received:April 16, 2025 Revised:October 15, 2025 |
| DOI：10.16205/j.cnki.cama.2025.0024 |
| 中文关键词: Rényi熵 Tsallis熵 耦合 贪心算法 |
| 英文关键词:Rényi entropy Tsallis entropy Coupling Greedy algorithm |
| 基金项目:国家重点研发计划项目(No. 2020YFA0712900)；国家自然科学基金项目(No. 11871103) |
| Author Name | Affiliation | | HAO Yifei | School of Mathematical Sciences, Key Laboratory of Mathematics and Complex Systems, Ministry of Education, Beijing Normal University, Beijing 100875, China | | WANG Yingzhe | School of Mathematical Sciences, Key Laboratory of Mathematics and Complex Systems, Ministry of Education, Beijing Normal University, Beijing 100875, China |
|
| Hits: 264 |
| Download times: 696 |
| 中文摘要: |
| 针对基于Rényi Hα熵的最小熵耦合问题，通过引入profile方法，得到了贪心算法近似解与最优解之间熵函数差值的一个上界h(α)。在两个概率分布耦合的情况下，h(α)=1/(α-1) log2(1+(1/α)^(1/(α-1))-(1/α)^(α/(α-1)))；在有限个概率分布耦合的情况下，h(α)=1/(1-α) log2(1/2+1/(α2α))。并将相关结果推广至Tsallis熵。创新之处在于，给出了误差估计与参数α的函数关系，并且在α>0.365时获得了更加精确的结果。 |
| 英文摘要: |
| For the minimum entropy coupling problem based on Rényi entropy Hα, an upper bound h(α) on the entropy function difference between the greedy algorithm’s approximate solution and the optimal solution was derived by introducing the profile method. When the authors couple two probability distributions, h(α)=1/(α-1) log2(1+(1/α)^(1/(α-1))-(1/α)^(α/(α-1))). When the authors couple finite probability distributions, h(α)=1/(1-α) log2(1/2+1/(α2α)). These results were further extended to the Tsallis entropy. The innovation of this work lies in establishing the error estimate as an explicit function of the parameter α, and obtaining more precise results for α>0.365. |
| View Full Text View/Add Comment Download reader |
| Close |
