p51

Problem 5.1 (Independence of mechanisms) Let $P_X$ be the mixture of $k$ sharp Gaussian peaks at positions $s_1,\dots ,s_k$ as shown in Figure 5.5, left. Let $Y$ be obtained from $X$ by adding some Gaussian noise $N$ with zero mean and a width ${\sigma }_N$ such that the separate peaks remain visible as in Figure 5.5, right.

1. Argue intuitively why $P_{X\mid Y}$ also contains information about the positions $s_1,\dots ,s_k$ of the peaks and thus $P_{X\mid Y}$ and $P_Y$ share this information.

2. The transition between $P_X$ and $P_Y$ can be described by convolution (from $P_X$ to $P_Y$) and deconvolution (from $P_Y$ to $P_X$). If $P_{Y\mid X}$ is considered as the linear map converting the input $P_X$ to the output $P_Y$, then $P_{Y\mid X}$ coincides with the convolution map. Argue why $P_{X\mid Y}$ does not coincide with the deconvolution map (as one may think at first glance).

Setup in formulas. $P_X={\sum }_{i=1}^k{w}_i\mathcal{N}(s_i,{\sigma }_0^2)$ with weights $w_i>0$, ${\sum }_i{w}_i=1$, and ${\sigma }_0$ small; $Y=X+N$ with $N\sim \mathcal{N}(0,{\sigma }_N^2)$, $N\perp \perp X$, and ${\sigma }_0\ll {\sigma }_N\ll {\min }_{i\ne j}|s_i-s_j|$.

Definition (convolution). For two probability measures $\mu ,\nu$ on $\mathbb{R}$, their convolution is the probability measure

$$(\mu \ast \nu )(B):={\int }_{\mathbb{R}}{\int }_{\mathbb{R}}{1}_B(x+z)\mu (dx)\nu (dz),B\in \mathcal{B}(\mathbb{R}).$$

It is the law of $X+Z$ when $X\sim \mu$, $Z\sim \nu$, and $X\perp \perp Z$ (by the product-measure/Fubini argument of Claim 1 in anm_claims.pdf). If $\mu ,\nu$ have Lebesgue densities $p,q$, then $\mu \ast \nu$ has density

$$(p\ast q)(y)={\int }_{\mathbb{R}}p(x)q(y-x)dx.$$

Convolution is commutative, associative and linear in each argument. In the problem, $P_Y=P_X\ast \mathcal{N}(0,{\sigma }_N^2)$, i.e. $p_Y(y)=\int p_X(x){\phi }_{{\sigma }_N}(y-x)dx$ with ${\phi }_{\sigma }$ the $\mathcal{N}(0,{\sigma }^2)$ density; the map $p_X\mapsto p_X\ast {\phi }_{{\sigma }_N}$ is linear and is exactly the kernel $P_{Y\mid X=x}=\mathcal{N}(x,{\sigma }_N^2)$ integrated against $P_X$.

Definition (deconvolution). Deconvolution is the inverse problem: given $q$ (the noise density) and the output $r=p\ast q$, recover the input $p$. Formally it is the inverse of the linear map $p\mapsto p\ast q$, whenever that inverse exists. With Fourier transforms $\hat{p}(t):=\int e^{itx}p(x)dx$ one has $\widehat{p\ast q}=\hat{p}\hat{q}$, so

$$p={\mathcal{F}}^{-1}(\hat{r}/\hat{q})$$

provided $\hat{q}$ has no zeros. For Gaussian $q$, $\hat{q}(t)=e^{-{\sigma }_N^2{t}^2/2}$ never vanishes, so the inverse exists on a suitable class of functions, but it divides by an exponentially small number at high frequencies: deconvolution is linear but ill-posed (small perturbations of $r$ blow up). Note it is a fixed linear map determined by $q$ alone; it does not depend on which $p$ produced $r$.

Solution

a) We have $X\to Y,Y=X+N,N\sim \mathcal{N}(0,{\sigma }_N^2)$.

Solution a) If we choose $y$ midway between two adjacent peaks, say $s_1$ and $s_2$, then $P_{X\mid Y=y}$ puts its mass equally at $s_1$ and $s_2$ with a gap in the middle, so we know that we are not uniquely near any $s_i$. If we choose $y$ near $s_1$, then $P_{X\mid Y=y}$ has much more mass around $s_1$. Reason: $p(x\mid y)\propto p_X(x){\phi }_{{\sigma }_N}(y-x)$, and the factor $p_X(x)$ is $\approx 0$ away from the $s_i$, so for every $y$ the mass of $P_{X\mid Y=y}$ sits at the peak positions; $y$ only sets their relative weights $\propto w_i{\phi }_{{\sigma }_N}(y-s_i)$. Hence $P_{X\mid Y}$ reveals $s_1,\dots ,s_k$, just as $P_Y$ does, while $P_{Y\mid X=x}=\mathcal{N}(x,{\sigma }_N^2)$ does not.

Solution b) Fix the model $P_X={\sum }_k{w}_k\mathcal{N}(s_k,{\sigma }_0^2)$, $Y=X+N$, $N\sim \mathcal{N}(0,{\sigma }_N^2)$, $N\perp \perp X$, and write $S:=\{s_1,\dots ,s_k\}$, $s_{\min }:=\min S$, $s_{\max }:=\max S$,

$$\kappa :=\frac{{\sigma }_0^2}{{\sigma }_0^2+{\sigma }_N^2},v:=\frac{{\sigma }_0^2{\sigma }_N^2}{{\sigma }_0^2+{\sigma }_N^2},m_j(y):=(1-\kappa )s_j+\kappa y.$$

By Bayes (deconv_helpers), the posterior is $P_{X\mid Y=y}={\sum }_j{\pi }_j(y)\mathcal{N}(m_j(y),v)$ with ${\pi }_j(y)\propto w_j{\phi }_{\sqrt{{\sigma }_0^2+{\sigma }_N^2}}(y-s_j)$ (^bde910, ). The two maps on distributions:

$$C(\tilde{Q}):=\text{deconvolution of }\tilde{Q}\text{ by }\mathcal{N}(0,{\sigma }_N^2),K(\tilde{Q})(B):=\int P_{X\mid Y=y}(B)\tilde{Q}(dy).$$

Both send $P_Y\mapsto P_X$ (Recall $P_X(B)=\int P_{X\mid Y=y}(B)P_Y(dy)$ from deconv_helpers and this is simply (actually it is a nightmare) Bayes for Kernel map and cf subtraction for deconv). Two maps differ iff they differ at one input, so we exhibit a $\tilde{Q}$ and a Borel set $B$ with $C(\tilde{Q})(B)\ne K(\tilde{Q})(B)$. (In fact they agree only at $P_Y$; not needed here.)

Representation. A sample $X^{\prime }\sim K(\tilde{Q})$ can be generated in two stages: draw $\tilde{Y}\sim \tilde{Q}$; given $\tilde{Y}=y$, pick the index $J=j$ with probability ${\pi }_j(y)$ and set $X^{\prime }=m_J(\tilde{Y})+Z$, $Z\sim \mathcal{N}(0,v)$ independent (why?). Hence

$$X^{\prime }=(1-\kappa )S^{\prime }+\kappa \tilde{Y}+Z,S^{\prime }:=s_J\in [s_{\min },s_{\max }].$$

All dependence on the intractable weights ${\pi }_j$ is confined to $S^{\prime }$, of which we use only the bound $s_{\min }\le S^{\prime }\le s_{\max }$.

Sandwich. If $X=A+W$ and $X^{\prime \prime }=A^{\prime \prime }+W$ on one probability space with $A\le A^{\prime \prime }$ a.s., then $P(X>x)\le P(X^{\prime \prime }>x)$ for all $x$ (why?). Applying this with $A=(1-\kappa )S^{\prime }$ gives, for every input $\tilde{Q}$,

$$\text{law of }(1-\kappa )s_{\min }+\kappa \tilde{Y}+Z⪯K(\tilde{Q})⪯\text{law of }(1-\kappa )s_{\max }+\kappa \tilde{Y}+Z,$$

where $\mu ⪯\nu$ means $\mu ((x,\infty ))\le \nu ((x,\infty ))$ for all $x$.

Separating input. Take $\tilde{Q}:=P_Y(\cdot -t)={\sum }_j{w}_j\mathcal{N}(s_j+t,{\sigma }_0^2+{\sigma }_N^2)$ for a shift $t>0$ to be chosen. Writing $\tilde{Y}=S^{\prime \prime }+t+W$ with $S^{\prime \prime }\in [s_{\min },s_{\max }]$, $W\sim \mathcal{N}(0,{\sigma }_0^2+{\sigma }_N^2)$ (why?), the upper bound collapses:

$$K(\tilde{Q})⪯\text{law of }{s}_{\max }+\kappa t+\kappa W+Z=\mathcal{N}(s_{\max }+\kappa t,{\sigma }_0^2),$$

using ${\kappa }^2({\sigma }_0^2+{\sigma }_N^2)+v={\sigma }_0^2$, which is the law of total variance $\mathrm{Var}X=\mathrm{Var}\mathbb{E}[X\mid Y]+\mathbb{E}\mathrm{Var}[X\mid Y]$ in the single-peak toy (why?). On the other side, deconvolution commutes with translation (why?), so $C(\tilde{Q})=P_X(\cdot -t)={\sum }_j{w}_j\mathcal{N}(s_j+t,{\sigma }_0^2)$, and the same selection trick gives $C(\tilde{Q})⪰\mathcal{N}(s_{\min }+t,{\sigma }_0^2)$.

Threshold. The bounding Gaussians have equal width ${\sigma }_0$ and centre gap $(s_{\min }+t)-(s_{\max }+\kappa t)=(1-\kappa )t-\mathrm{diam}(S)$. Choose $t>\mathrm{diam}(S)/(1-\kappa )$, so the gap is positive, and let $x^{\ast }$ be the midpoint of the two centres. Then

$$K(\tilde{Q})((x^{\ast },\infty ))<\frac{1}{2}<C(\tilde{Q})((x^{\ast },\infty )),$$

so $K(\tilde{Q})\ne C(\tilde{Q})$ and the maps differ. $\square$

Moral. $C$ is built from the noise alone and follows its input anywhere; $K$ carries the prior inside ($s_j,\kappa ,v,{\pi }_j$) and every output is dragged back to within $\kappa$-reach of the old peaks. The two coincide exactly at the one input $P_Y$ that the old prior generated — Bayes’ inversion of this joint, not an inverse of the blur.

Lemma (uniqueness). $C(\tilde{Q})=K(\tilde{Q})$ holds only at $\tilde{Q}=P_Y$.

Tools. (i) A Markov kernel $T(x,\cdot )$ is a probability measure on $\mathbb{R}$ for each $x$, measurable in $x$; it acts on measures by $(\mu T)(B):=\int T(x,B)\mu (dx)$. $\mu$ is invariant if $\mu T=\mu$. (ii) Hahn decomposition: every finite signed measure $\nu$ splits $\mathbb{R}=P\bigsqcup N$ with $\nu \ge 0$ on subsets of $P$ and $\nu \le 0$ on subsets of $N$; then ${\nu }^{+}(B):=\nu (B\cap P)$, ${\nu }^{-}(B):=-\nu (B\cap N)$ are finite measures with $\nu ={\nu }^{+}-{\nu }^{-}$.

Step 1 (reformulate as a fixed point). Define the Gibbs kernel (go $x\to y$ by the forward noise, then $y\to x^{\prime }$ by the posterior)

$$T(x,B):=\int P_{X\mid Y=y}(B){\phi }_{{\sigma }_N}(y-x)dy.$$

Then $\mu T=K(\mu \ast \mathcal{N}(0,{\sigma }_N^2))$ for every probability $\mu$ (why?). If $C(\tilde{Q})=K(\tilde{Q})=:R$, then $\tilde{Q}=R\ast \mathcal{N}(0,{\sigma }_N^2)$ by definition of $C$, hence $R=K(\tilde{Q})=RT$: $R$ is invariant for $T$. Conversely an invariant $R$ gives the agreement point $\tilde{Q}=R\ast \mathcal{N}(0,{\sigma }_N^2)$. So agreement points $\leftrightarrow$ invariant probabilities of $T$, via $\tilde{Q}=R\ast \mathcal{N}(0,{\sigma }_N^2)$.

Step 2 ($P_X$ is invariant). $P_X\ast \mathcal{N}(0,{\sigma }_N^2)=P_Y$ and $K(P_Y)=P_X$, so $P_{X}T=P_X$. This gives the known agreement point $\tilde{Q}=P_Y$.

Step 3 (no other invariant probability). $T(x,\cdot )$ has a strictly positive Lebesgue density for every $x$, since $P_{X\mid Y=y}$ is a Gaussian mixture with $v>0$ (why?). Let ${\pi }_1,{\pi }_2$ be invariant probabilities and $\nu :={\pi }_1-{\pi }_2$, so $\nu T=\nu$ and $\nu (\mathbb{R})=0$. Take a Hahn decomposition $\mathbb{R}=P\bigsqcup N$ of $\nu$. For every Borel $B$,

$${\nu }^{+}(B)=\nu (B\cap P)=({\nu }^{+}T)(B\cap P)-({\nu }^{-}T)(B\cap P)\le ({\nu }^{+}T)(B\cap P)\le ({\nu }^{+}T)(B),$$

and ${\nu }^{+}(\mathbb{R})=({\nu }^{+}T)(\mathbb{R})$ because $T$ preserves mass. A measure dominated by another of equal total mass equals it (why?), so ${\nu }^{+}={\nu }^{+}T$. Then

$$0={\nu }^{+}(N)=({\nu }^{+}T)(N)=\int T(x,N){\nu }^{+}(dx),$$

and $T(x,N)>0$ for all $x$ whenever $\mathrm{Leb}(N)>0$. Hence ${\nu }^{+}=0$ or $\mathrm{Leb}(N)=0$. Symmetrically ${\nu }^{-}=0$ or $\mathrm{Leb}(P)=0$. If $\nu \ne 0$ then ${\nu }^{+},{\nu }^{-}$ are both nonzero (equal mass, since $\nu (\mathbb{R})=0$), forcing $\mathrm{Leb}(P)=\mathrm{Leb}(N)=0$, i.e. $\mathrm{Leb}(\mathbb{R})=0$. Contradiction, so ${\pi }_1={\pi }_2$. By Steps 1–2 the unique agreement point is $P_Y$. $\square$

Check in the single-peak toy (Fourier). With $k=1$, $s_1=0$: $K(\tilde{Q})$ is the law of $\kappa \tilde{Y}+Z$, so $\widehat{K(\tilde{Q})}(t)=\hat{\tilde{Q}}(\kappa t)e^{-v{t}^2/2}$, while $\widehat{C(\tilde{Q})}(t)=\hat{\tilde{Q}}(t)e^{{\sigma }_N^2{t}^2/2}$ (Helper 3). Agreement means $\hat{\tilde{Q}}(t)=\hat{\tilde{Q}}(\kappa t)e^{-(v+{\sigma }_N^2)t^2/2}$; iterating $n$ times and letting $n\to \infty$ (using $\kappa <1$ and $\hat{\tilde{Q}}$ continuous at $0$ with $\hat{\tilde{Q}}(0)=1$) gives $\hat{\tilde{Q}}(t)=e^{-(v+{\sigma }_N^2)t^2/(2(1-{\kappa }^2))}$, and $(v+{\sigma }_N^2)/(1-{\kappa }^2)={\sigma }_0^2+{\sigma }_N^2$ (why?). So $\tilde{Q}=\mathcal{N}(0,{\sigma }_0^2+{\sigma }_N^2)=P_Y$. This route uses that convolution and $K$ are both diagonal in the Fourier basis (multiply/rescale $\hat{\tilde{Q}}$); for $k\ge 2$ the $y$-dependent weights ${\pi }_j(y)$ break this, which is why the lemma goes through $T$ instead.