0.5 Beyond lossless compression  (Page 5/7)

and so $E[\parallel x-\hat{x}{\parallel }_2^2]$ , the mean square error, is double the MMSE  [link] .

Let us pause to reflect about this result. When the SNR is high, i.e., ${\parallel x\parallel }_2^2\gg {\parallel z\parallel }_2^2$ , the MMSE should be rather low, and double the MMSE seems pretty good. On the other hand, when the SNR is low, the MMSE could be almost as large as $E[\parallel x{\parallel }_2^2]$ , and double the MMSE could be larger – as much as twice larger – than $E[\parallel x{\parallel }_2^2]$ . That is, gussing $\hat{x}=E\left[x\right]$ could give better signal estimation performance than using the Kolmogorov sampler. This pessimistic result encourages us to search for better signal reconstruction methods.

Arbitrary channels: So far we considered the Kolmogorov sampler for the white scalar channel, $y=x+z$ . Suppose instead that $x$ is processed or measured by a more complicated system,

Note that $J$ is known, e.g., in a compressed sensing application  [link] , [link] $J$ would be a known matrix. An even more involved system would be $y=(J\otimes x)\oplus z$ , where $J\otimes x$ is application of a mapping to x, $J\otimes x\in {\mathbb{R}}^L$ , and $\oplus z$ denotes application of a random noise operator to $J\otimes x$ . To keep the presentation simple, we use the additive noise setting [link] .

How can the Kolmogorov sampler [link] be applied to the additive noise setting? Recall that for the scalar channel, the Kolmogorov sampler minimizes $K\left(w\right)$ subject to ${\parallel y-w\parallel }_2^2\le n$ . For the arbitrary mapping $J$ with additive noise [link] , this implies ${\parallel y-J\left(w\right)\parallel }_2^2\le n$ . Therefore, we get

Another similar approach relies on optimization via Lagrange multipliers,

where the lagrange multiplier is 1, because both $K\left(w\right)$ and ${log}_2\left(f_z(y-J\left(w\right))\right)$ are quantified in bits.

What is the performance of the Kolmogorov sampler for an arbitrary $J$ ? We speculate  [link] , [link] that $\hat{x}$ is generated by the posterior, and so $E[\parallel x-{\hat{\parallel }}_2^2]$ is double the MMSE, where expectation is taken over the source $X$ and noise $z$ . These results remain to be shown rigorously.

Convergence of mcmc algorithm

We will now prove a substantial result – that the MCMC algorithm  [link] , [link] , [link] converges to the globally minimal energy solution for the specific case of compressed sensing  [link] , [link] . An extension of this proof to arbitrary channels $J$ is in progress.

If the operator $J$ in [link] is a matrix, and we denote it by $\Phi \in {\mathbb{R}}^{m\times n}$ where $m\ll n$ , then the setup is known as compressed sensing (CS)  [link] , [link] and the estimation problem is commonly referred to as recovery or reconstruction.By posing a sparsity or compressibility requirement on the signal and using it as a prior during recovery, it is indeed possible to accurately estimate $x$ from $y$ in the CS setting.

With the quantization alphabet definition in [link] , $\hat{\alpha }$ will quantize $x$ to a greater resolution as $N$ increases. We will show that under suitable conditions on $f_X$ , performing maximum a posteriori (MAP) estimation over the discrete alphabet $\hat{\alpha }$ asymptotically converges to the MAP estimate over the continuous distribution $f_X$ . This reduces the complexity of the estimation problem from continuous to discrete.

We assume for exposition that we know the input statistics $f_X$ . Given the measurements $y$ , the MAP estimator for $x$ has the form

Because $z$ is i.i.d. Gaussian with mean zero and known variance ${\sigma }_Z^2$ ,