Logs of Sums and Integrals

Suppose we want to minimize $$f(x)=-\log\int_{\mathcal{Z}} p(x,z)dz$$ where $p:\mathcal{X}\otimes\mathcal{Z}\rightarrow\mathbb{R}^+$.

It is convenient to define $$\begin{align*} p(z\mid x)&\mathop{=}\limits^{\Delta}\frac{p(x,z)}{\int_\mathcal{Z}p(x,z)dz},\\ q(x,y)&\mathop{=}\limits^{\Delta}\int_\mathcal{Z}p(z\mid y)\log p(x,z)dz, \end{align*}$$ and $$g(x,y)=f(y)+q(y,y)-q(x,y).$$

Theorem: For all $x,y\in\mathcal{X}$ we have $f(x)\leq g(x,y)$ with equality if and only if $p(x,z)=p(y,z)$ a.e. Consequently $g$ majorizes $f$ on $\mathcal{X}$.

Proof: By Jensen's inequality $$\begin{multline*} \log\frac{\int_\mathcal{Z} p(x,z)dz}{\int_\mathcal{Z} p(y,z)dz}= \log\int_\mathcal{Z} p(z\mid y)\frac{p(x,z)}{p(y,z)}dz \geq \\ \geq\int_\mathcal{Z} p(z\mid y)\log\frac{p(x,z)}{p(y,z)}dz =\\ =\int_\mathcal{Z}p(z\mid y)\log{p(x,z)}dz -\int_\mathcal{Z}p(z\mid y)\log{p(y,z)}dz. \end{multline*}$$ Thus $$-f(x)+f(y)\geq q(x,y)-q(y,y)$$ But this exactly the statement of the theorem. QED

Maximizing the right-hand-side by block relaxation is the EM algorithm \cite{delaru}. Usually, of course, the EM algorithm is presented in probabilistic terms using the concept of likelihood and expectation. This has considerable heuristic value, but it detracts somewhat from seeing the essential engine of the algorithm, which is the majorization.