Bregman distances for functionals

[mehrhardt]

It would be great if ODL was supporting Bregman distances. An easy way would be to define it as a function of x as (here without ODL):

given y and p
def BregmanG(x): return g(x) - g(y) - p.inner(x-y)

Is there a way to do this nicely in ODL? One would need to define a functional that does x -> p.inner(x-y).

[adler-j]

Well, you can implement it as thus:

>>> r3 = odl.rn(3)
>>> g = odl.solvers.L2Norm(r3)
>>> p = r3.element([1, 2, 3])
>>> y = r3.element([4, 5, 6])
>>> bregman = odl.solvers.FunctionalLinearPerturb(g, -p) - g(y) + p.inner(y)
>>> bregman([5, 6, 7])
-4.2868759056906072

which has all of the properties you are looking for I guess

>>> bregman.proximal(1)([5, 6, 7])
rn(3).element([5.5757359312880759, 7.4343145750507675, 9.2928932188134592])
>>> bregman.gradient([5, 6, 7])
rn(3).element([-0.52326870537720382, -1.4279224464526445, -2.3325761875280855])
>>> bregman.convex_conj([5, 6, 7])
inf

with that said, adding a BregmanDistance functional would make this more clear and less prone to misstakes.

Edit: Fixed a sign error.

[aringh]

I have started working on Bregman functional on my private fork some time ago. I just implemented and example running the iterations for Brgeman-TV, but did not have time to encapsulate it in a Bregman functional. If you are interested you could have a look at it: the branch and specifically the commit.

[adler-j]

@aringh, any chance that you can make your implementation of the bregman functional public?

[ozanoktem]

Somewhat off-topic, but I still want to mention the following publications that contain a nice overview of common functionals and their corresponding Bregman distances:
http://www.jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf (table 1 on p. 1709)
https://www.uni-muenster.de/AMM/num/burger/teaching/Doktoranden/thesisBenning.pdf (Table 3.1 on p. 58).

[aringh]

I do not have anything else than what is on the aforementioned branch... but if I find time I can try to encapsulate it into some kind of functional.

[ozanoktem]

One should perhaps consider implementing Bregman distance functionality in ODL in the same way as proximal, i.e. allow a developer to call functional.bregman. I think the Bregma distance behaves nicer than proximal in operator calculus, e.g. the Bregma distance associated with the linear combination of two functionals equals the linear combination of Bregma distances of corresponding functionals.

[ozanoktem]

Check out https://en.wikipedia.org/wiki/Bregman_divergence#Properties for a list of basic properties of Bregma distances.

[kohr-h]

Done in #1267.