# On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
## 2 Compressed Sensing of Binary Signals
### MCMC Algorithm for Recovery  
Recall that, for a given sensing matrix \(A\), our goal is to construct an estimator \(\widehat{x}=\widehat{x}(\mathbf{y})\) such as to minimize the per-bit error rate (BER), as defined in (3). Clearly, the optimal estimator in the sense of minimizing the BER is simply the per-coordinate maximum a posteriori (MAP) estimator:  
\[\widehat{x}_{\text{BER},i}=\operatorname*{argmax}_{\widehat{x}\in\{0,1\}} \operatorname{Pr}\bigl{(}x_{i}=\widehat{x}\,\big{|}\,\mathbf{y}\bigr{)}\,,\quad \text{ for all }1\leq i\leq M\,. \tag{4}\]  
Computing the posterior \(\operatorname{Pr}(x_{i}\,|\,\mathbf{y})\) is a formidable task: it requires one to marginalize over all other coordinates \(\ell\
eq i\). From a computational point of view, this is highly nontrivial, since the coupling between the coordinates of \(\mathbf{x}\), as induced by \(A\), creates a strong cross-coordinate dependency conditioned on \(\mathbf{y}\). We propose to mitigate this difficulty by **sampling**. Instead of marginalizing and and maximizing, we sample an \(\widehat{\mathbf{x}}\in\{0,1\}^{M}\) from the full posterior, given by  
\[\operatorname{Pr}\bigl{(}\mathbf{x}=\widehat{\mathbf{x}}\,\big{|}\,\mathbf{y}\bigr{)}= \frac{1}{Z}\exp\biggl{\{}-\frac{1}{2\sigma^{2}}\|\mathbf{y}-A\widehat{\mathbf{x}}\|^{2 }+\lambda\|\widehat{\mathbf{x}}\|_{1}\biggr{\}}\,, \tag{5}\]  
where \(\lambda=\log\frac{\rho}{1-\rho}\), \(\rho=k/M\) and \(Z\) is the partition function (to see the correctness of \(\lambda=\log\frac{\rho}{1-\rho}\) in the expression above, note that the prior is \(\operatorname{Pr}(x_{i}=1)=e^{\log\rho}\) and \(\operatorname{Pr}(x_{i}=0)=e^{\log(1-\rho)}\); in other words, \(\operatorname{Pr}(x_{i}=\hat{x}_{i})=e^{\hat{x}_{i}\log\rho+(1-\hat{x}_{i}) \log(1-\rho)}=e^{\hat{x}\hat{x}_{i}+\log(1-\rho)}\propto e^{\hat{x}\hat{x}_{i}}\). Taking the \(i\)th coordinate of \(\widehat{x}\), call it \(\widehat{x}_{i}\), we obtain a sample from \(\operatorname{Pr}(x_{i}=\cdot|\mathbf{y})\), the desired single-bit posterior distribution. Intuition suggests that, when \(\widehat{x}_{\text{BER},i}\) has small error, the estimator obtained by sampling, call it \(\widehat{x}_{\text{SAMP},i}\), should have small error as well. This is because, if the optimal error is small, the posterior \(\operatorname{Pr}(x_{i}|\mathbf{y})\) must put most of its mass on \(\widehat{x}_{\text{BER},i}=\widehat{x}_{\text{BER},i}(\mathbf{y})\); this in turn means that, with high probability over the sampling procedure, one should in fact get \(\widehat{x}_{\text{SAMP},i}=\widehat{x}_{\text{BER},i}\). This reasoning is formalized in the following Lemma:  
**Lemma 1**. : _Denote \(\widehat{x}_{\text{BER}}=(\widehat{x}_{\text{BER},1},\ldots,\widehat{x}_{ \text{BER},M})\), with coordinates given by Equation (4). Let \(\widehat{x}_{\text{SAMP}}=\widehat{x}_{\text{SAMP}}(\mathbf{y})\sim\operatorname{ Pr}(\cdot\,|\,\mathbf{y})\) be a random sample from the posterior (5). Then:_  
\[\operatorname{BER}(\mathbf{x},\widehat{x}_{\text{SAMP}})\leq 2\cdot\operatorname{ BER}(\mathbf{x},\widehat{x}_{\text{BER}})\]  
_In other words, the bit error rate of \(\widehat{x}_{\text{SAMP}}\) is bounded by twice the optimal bit error rate, over all estimators._  
_Note that, on the left-hand side, the probability is taken both over the randomness in \(\mathbf{x}\) and the noise, as well as the sampling procedure used for constructing \(\widehat{x}_{\text{SAMP}}\)._  
Several variants of Lemma 1 have been proved in the past (see, e.g., [58; 59; 60]). For completeness, we provide a short proof in Appendix A.1. Thus, we are left with the problem of sampling from the posterior \(\operatorname{Pr}(\mathbf{x}\,|\,\mathbf{y})\)--doing so \"directly\" might seem, at first glance, essentially just as hard as maximizing the posterior (namely, we would need to go over all \(2^{M}\) possible signal configurations). Markov-Chain Monte Carlo (MCMC) methods provide a strong toolbox for sampling, _approximately_, from high-dimensional distributions.