0.5 Beyond lossless compression  (Page 6/7)

where $c_1={\left(2\pi {\sigma }_Z^2\right)}^{-M/2}$ and $c_2=\frac{1}{2{\sigma }_Z^2}$ are constants and $\parallel ·\parallel$ denotes the Euclidean norm. Plugging into [link] and taking log likelihoods, we obtain

where ${\Psi }^X(·)$ denotes the objective function (risk)

our ideal risk would be ${\Psi }^X\left(x_{MAP}\right)$ .

Instead of performing continuous-valued MAP estimation, we optimize for the MAP in the discretized domain ${\hat{\alpha }}^N$ . We begin with a technical condition on the input.

Condition 1 [link] We require that the probability density has bounded derivatives

where $\frac{d}{d{x}_n}$ is the derivative w.r.t. entry $n$ of $x$ , $n\in \{1,...,N\}$ , and $\rho >0$ .

Let ${\tilde{x}}_{MAP}$ be the quantization bin in ${\hat{\alpha }}^N$ nearest to $x_{MAP}$ .  Condition 1 ensures that a small perturbation from $x_{MAP}$ to ${\tilde{x}}_{MAP}$ does not change $ln\left(f_X(·)\right)$ by much. We use this fact to prove that ${\Psi }^X\left({\tilde{x}}_{MAP}\right)$ is sufficiently close to ${\Psi }^X\left(x_{MAP}\right)$ asymptotically.

Theorem 9 [link] Let $\Phi \in {\mathbb{R}}^{M\times N}$ be an i.i.d. Gaussian measurement matrix where each entry has mean zero and variance $\frac{1}{M}$ . Suppose that Condition 1 holds and the aspect ratio $\delta =\frac{m}{n}>0$ , and let the noise $z\in {\mathbb{R}}^M$ be i.i.d. zero-mean Gaussian.Then for all $ϵ>0$ , the quantized estimator ${\tilde{x}}_{MAP}$ satisfies

almost surely as $N\to \infty$ .

Given that Theorem 9 shows that the risk penalty due to quantization vanishes asymptotically in $n$ , we now describe a Kolmogorov-inspired estimatorfor CS over a quantized grid. We define the energy $ϵ\left(w^n\right)$ :

where $c_4=c_2{log}_2\left(e\right)$ .

Ideally, our goal is to compute the globally minimum energy solution

Theorem 10 [link] Let $X$ be a bounded stationary ergodic source. Then the outcome $w_r^n$ of Algorithm 1 after $r$ iterations obeys

We define a stochastic transition matrix $P_{\left(r\right)}$ from ${\hat{\alpha }}^n$ to itself given by the Boltzmann distribution for super-iteration $r$ . Similarly, ${\pi }_{\left(r\right)}$ defines the stable state distribution on ${\hat{\alpha }}^n$ for $P_{\left(r\right)}$ , satisfying ${\pi }_{\left(r\right)}{P}_{\left(r\right)}={\pi }_{\left(r\right)}$ .

Definition 4 [link] The Dobrushin's ergodic coefficient of a Markov chain transition matrix $P$ is denoted by $\delta \left(P\right)$ and defined as

where $p_i$ denotes the $i^{th}$ row of $P$ , $1\le n\le N$ .

From the definition, $0\le \delta \left(P\right)\le 1$ . Moreover, the ergodic coefficient can be rewritten as

where $p_{ij}$ denotes the entry of $P$ at the $i^{th}$ row and $j^{th}$ column.

We group the product of transition matrices across super-iterations as

There are two common characterizations for the stable-state behavior of a non-homogeneous MC.

Definition 5 [link] A non-homogeneous MC is called weakly ergodic if for any distributions $\mu$ and $\nu$ over the state space $\mathcal{S}$ , and any $r_1\in \mathbb{N}$ ,

Similarly, a non-homogeneous MC is called strongly ergodic if there exists a distribution $\pi$ over the state space $\mathcal{S}$ such that for any distribution $\mu$ over $\mathcal{S}$ , and any $r_1\in \mathbb{N}$ ,

We will use the following two theorems from  [link] in our proof.

Theorem 11 [link] A Markov chain is weakly ergodic if and only if there exists a sequence of integers $0\le r_1\le r_2\le ...$ such that

Theorem 12 [link] Let a Markov chain be weakly ergodic.Assume that there exists a sequence of probability distributions ${\left\{{\pi }_{\left(r\right)}\right\}}_{i=1}^{\infty }$ on the state space $\mathcal{S}$ such that ${\pi }_{\left(r\right)}{P}_{\left(r\right)}={\pi }_{\left(r\right)}$ . Then the Markov chain is strongly ergodic if