# On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
## 2 Compressed Sensing of Binary Signals
### MCMC Algorithm for Recovery
\(p_{1}^{(t)}=\frac{q_{1}^{(t)}}{q_{0}^{(t)}+q_{1}^{(t)}}\); otherwise \(\mathbf{x}_{i_{t}}^{(t+1)}=0\) \(\mathbf{x}_{\sim i_{t}}^{(t+1)}=\mathbf{x}_{\sim i_{t}}^{(t)}\) (Note: Above, \(\mathbf{x}_{i_{t}=0}^{(t)}\), \(\mathbf{x}_{i_{t}=1}^{(t)}\) stand for setting, in \(\mathbf{x}^{(t)}\), the \(i_{t}\)th coordinate to \(0,1\) respectively). end return\(\mathbf{x}^{(T)}\)
```  
**Algorithm 1**Glauber dynamics for binary compressed sensing. We can give the following guarantee for the mixing time of Glauber dynamics:  
**Lemma 2** (Fast mixing for Glauber dynamics). : _Let \(\mathbf{y}\in\mathbb{R}^{n}\), \(\mathbf{x}^{(0)}\in\{0,1\}^{M}\), \(\sigma^{2}>0\) and \(\lambda\in\mathbb{R}\) be any parameters. Denote the following distribution \(\mathbb{Q}(\cdot)\) on the cube \(\{0,1\}^{M}\) by_  
\[\mathbb{Q}^{(\infty)}(\mathbf{x})=\mathbb{Q}^{(\infty)}_{\mathbf{y},\sigma^{2}\lambda}( \mathbf{x})=\frac{1}{Z}\exp\Bigl{\{}-\frac{1}{2\sigma^{2}}\|\mathbf{y}-A\mathbf{x}\|^{2}+ \lambda\|\mathbf{x}\|_{1}\Bigr{\}}\,,\]_where \(Z\) is the partition function. Denote by \(\mathbb{Q}^{(T)}(\cdot)=\mathbb{Q}^{(T)}_{\mathbf{y}\sigma^{2},\lambda,\mathbf{x}^{(0)}}(\cdot)\) the distribution of \(\mathbf{x}^{(T)}\), the state returned after running Algorithm 1 for \(T\) steps. Suppose that_  
\[4\sigma^{2}>\
u(s-1)\, \tag{6}\]  
_where \(\
u\) and \(s\) are, respectively, the variable and factors degrees in \(A\)._  
_Let \(\epsilon>0\) let be a target precision. Then, for any \(T\geq(\log(1/\epsilon)+\log(M))\cdot\frac{4\sigma^{2}M}{4\sigma^{2}-\
u(s-1)}= \Theta(M\log M)\) (here the \(\Theta(\cdot)\) notation suppresses a dependence on \(\epsilon,\sigma^{2},\
u,s\)), one has_  
\[\mathbf{d_{TV}}\Big{(}\mathbb{Q}^{(T)},\mathbb{Q}^{(\infty)}\Big{)}\leq \epsilon\,,\]  
_where \(\mathbf{d_{TV}}(\cdot,\cdot)\) stands for total variation (statistical) distance._  
A proof is given in Appendix A.2. Note that Lemma 2 applies for _any_\(\mathbf{y}\in\mathbb{R}^{n}\) and \(\sigma^{2}\), that do not necessary have anything to do with the model (1). However, when \(\mathbf{y},\sigma^{2}\) do correspond to measurements from (1), namely \(\mathbf{y}=Ax+\sigma z\), Lemma 2, combined with Lemma 1, allows us to bound the bit error rate of the estimator \(\mathbf{x}=\mathbf{x}^{(T)}\) returned by running \(T\) iterations of Glauber dynamics. Assuming condition (6) holds, Lemma 2 tell us that running \(T=\frac{4(c+1)\sigma^{2}}{4\sigma^{2}-4\
u(s-1)}\cdot M\log M=O(M\log M)\) iterations of Glauber dynamics gives, with probability one (over \(\mathbf{x},\mathbf{y}\)) an output \(\mathbf{x}^{(T)}\) whose law is \(M^{-c}\)-close to the law of \(\widehat{\mathbf{x}}_{SAMP}\), in total variation distance--here, \(c>0\) can be taken as large as one likes. Recall that total variation distance is just \(\mathbf{d_{TV}}(\mathbb{P},\mathbb{Q})=\max_{0\leq f\leq 1}\left\{\mathbb{E}_{ \tilde{\mathbf{x}}\sim\mathbb{P}}[f(\widehat{\mathbf{x}})]-\mathbb{E}_{\tilde{\mathbf{x} }\sim\mathbb{Q}}[f(\widehat{\mathbf{x}})]\right\}\) ; maximization here is done over all bounded functions \(f:\{0,1\}^{M}\to[0,1]\) (recall that the maximum is actually attained at the indicator function \(f=\mathbf{1}_{S}\), where \(S=\{x:\mathbb{P}(x)/\mathbb{Q}(x)\geq 1\}\)). Plugging \(f(\widehat{\mathbf{x}})=\frac{1}{k}\sum_{i=1}^{M}\mathbf{1}_{x_{i}\
eq\tilde{x}_{ i}}\) and noting that \(f\) is non-negative and bounded by \(M/k\), we deduce  
\[\text{BER}(\mathbf{x},\mathbf{x}^{(T)}) \leq\text{BER}(\mathbf{x},\widehat{\mathbf{x}}_{\text{SAMP}})+\frac{M}{k} \mathbb{E}_{\mathbf{x},\mathbf{y}}\mathbf{d_{TV}}(\mathbb{P}_{\tilde{\mathbf{x}}^{(t)}}, \mathbb{P}_{\tilde{\mathbf{x}}_{\text{SAMP}}})\] \[\leq\text{BER}(\mathbf{x},\widehat{\mathbf{x}}_{\text{SAMP}})+M^{-c+1}/k\,,\]  
which, by Lemma 1, is bounded by twice the optimum BER, up to an inverse polynomial (in \(M\)) error.