Proximal Point Majorization

We usually write $f(x) ≤ g(x,y)$ for the key property of the majorizing function. One can also write $f (x) ≤ f (x) + d(x, y)$ with $d(x, y)\mathop{=}\limits^{\Delta}g(x, y) − f (x)$ Thus $d(x,y)$ is non-negative, and $d(x,x)=0$, i.e. $d(x,y)$ is distance-like.

Bregman

$$f(x)\leq f(x)+\lambda\|x-y\|^2$$

$$x^{(k+1)}=\mathop{\mathbf{argmin}}\limits_{x} f(x)+\lambda_k\|x-x^{(k)}\|^2$$

The majorization algorithm updates by the rule $$x^{(k+1)}\in\mathop{\mathbf{argmax}}\limits_{x} f(x)+d(x,x^{(k)})$$ This shows majorization algorithms are generalized proximal point algorithms (for which there is a lot of theory). In the EM context this is used by Stephane Chretien, Alfred Hero, Paul Tseng and others to study algorithms. In fact, they often study $$x^{(k+1)}\in\mathop{\mathbf{argmax}}\limits_{x} f(x)+λ_kd(x,x^{(k)})$$ with $\lambda_k$ a sequence of non-negative numbers.