On the Power Distance Representation of Bregman Divergences
Abstract
We express Bregman divergences between parameters as power distances between corresponding weighted points, and investigate several applications of this representation. First, we show that the Bregman closest pair and diameter problems can be reformulated as bichromatic weighted point problems under the power distance. This reformulation enables Bregman nearest and farthest neighbor queries under power distances to be handled in practice through corresponding Euclidean neighbor queries in one additional dimension, after offsetting the weights. Next, we revisit the problem of computing minimum enclosing Bregman balls (Bregman MEBs) and establish their equivalence to double-sided weight power MEBs. We further show that Bregman MEBs can be approximated by relaxing the double-sided weight power MEB problem to its single-sided weight counterpart. We then present two approaches to solving general power MEB problems: An exact algorithm based on the LP-type framework and an arbitrarily accurate approximation scheme based on iterative Frank-Wolfe optimization. Finally, we show that the potential-function lifting transformations used to construct Bregman Voronoi diagrams can be reinterpreted as classical paraboloid lifting transformations applied to the corresponding weighted point sets. This establishes a direct connection between Bregman Voronoi diagrams and power diagrams, further illustrating how Bregman divergences can be represented as power distances.
Related
- Weighted Two-Parameter Quantum Divergences Generated by Matrix Power-Mean Gaps
- Relax and Follow: L0-Path Computation with L0-Bregman Relaxations
- On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression
- A greedy double-block nonlinear Bregman-Kaczmarz method for nonlinear equations
- Jensen-Bregman split Gibbs sampling
BibTeX
@misc{nielsen2026power,
title = {{On the Power Distance Representation of Bregman Divergences}},
author = {Frank Nielsen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.24197},
eprint = {2607.24197},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.24197},
}
RIS
TY - UNPB
TI - On the Power Distance Representation of Bregman Divergences
AU - Frank Nielsen
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2607.24197
UR - https://arxiv.org/abs/2607.24197
AB - We express Bregman divergences between parameters as power distances between corresponding weighted points, and investigate several applications of this representation. First, we show that the Bregman closest pair and diameter problems can be reformulated as bichromatic weighted point problems under the power distance. This reformulation enables Bregman nearest and farthest neighbor queries under power distances to be handled in practice through corresponding Euclidean neighbor queries in one additional dimension, after offsetting the weights. Next, we revisit the problem of computing minimum enclosing Bregman balls (Bregman MEBs) and establish their equivalence to double-sided weight power MEBs. We further show that Bregman MEBs can be approximated by relaxing the double-sided weight power MEB problem to its single-sided weight counterpart. We then present two approaches to solving general power MEB problems: An exact algorithm based on the LP-type framework and an arbitrarily accurate approximation scheme based on iterative Frank-Wolfe optimization. Finally, we show that the potential-function lifting transformations used to construct Bregman Voronoi diagrams can be reinterpreted as classical paraboloid lifting transformations applied to the corresponding weighted point sets. This establishes a direct connection between Bregman Voronoi diagrams and power diagrams, further illustrating how Bregman divergences can be represented as power distances.
ER -