Fractional Subadditivity of Submodular Functions: Equality Conditions and Their Applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908415433900032 |
|---|---|
| author | Jakhar, Gunank Kurri, Gowtham R. Chillara, Suryajith Prabhakaran, Vinod M. |
| author_facet | Jakhar, Gunank Kurri, Gowtham R. Chillara, Suryajith Prabhakaran, Vinod M. |
| contents | Submodular functions are known to satisfy various forms of fractional subadditivity. This work investigates the conditions for equality to hold exactly or approximately in the fractional subadditivity of submodular functions. We establish that a small gap in the inequality implies that the function is close to being modular, and that the gap is zero if and only if the function is modular. We then present natural implications of these results for special cases of submodular functions, such as entropy, relative entropy, and matroid rank. As a consequence, we characterize the necessary and sufficient conditions for equality to hold in Shearer's lemma, recovering a result of Ellis \emph{et al.} (2016) as a special case. We leverage our results to propose a new multivariate mutual information, which generalizes Watanabe's total correlation (1960), Han's dual total correlation (1978), and Csiszár and Narayan's shared information (2004), and analyze its properties. Among these properties, we extend Watanabe's characterization of total correlation as the maximum correlation over partitions to fractional partitions. When applied to matrix determinantal inequalities for positive definite matrices, our results recover the equality conditions of the classical determinantal inequalities of Hadamard, Szász, and Fischer as special cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12058 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fractional Subadditivity of Submodular Functions: Equality Conditions and Their Applications Jakhar, Gunank Kurri, Gowtham R. Chillara, Suryajith Prabhakaran, Vinod M. Information Theory Submodular functions are known to satisfy various forms of fractional subadditivity. This work investigates the conditions for equality to hold exactly or approximately in the fractional subadditivity of submodular functions. We establish that a small gap in the inequality implies that the function is close to being modular, and that the gap is zero if and only if the function is modular. We then present natural implications of these results for special cases of submodular functions, such as entropy, relative entropy, and matroid rank. As a consequence, we characterize the necessary and sufficient conditions for equality to hold in Shearer's lemma, recovering a result of Ellis \emph{et al.} (2016) as a special case. We leverage our results to propose a new multivariate mutual information, which generalizes Watanabe's total correlation (1960), Han's dual total correlation (1978), and Csiszár and Narayan's shared information (2004), and analyze its properties. Among these properties, we extend Watanabe's characterization of total correlation as the maximum correlation over partitions to fractional partitions. When applied to matrix determinantal inequalities for positive definite matrices, our results recover the equality conditions of the classical determinantal inequalities of Hadamard, Szász, and Fischer as special cases. |
| title | Fractional Subadditivity of Submodular Functions: Equality Conditions and Their Applications |
| topic | Information Theory |
| url | https://arxiv.org/abs/2501.12058 |