Problem 5.1 (Independence of mechanisms)

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.