# On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
## Appendix A Omitted Proofs
### Proof of Lemma 2
\(X_{\mathbf{x}},X_{\mathbf{x}^{\prime}}\) coincide with \(\mathbf{x},\mathbf{x}^{\prime}\), respectively, on all coordinates \(\ell\
eq i\); as for the \(i\)th coordinate, set \((X_{\mathbf{x}})_{i}=1\) if \(U\leq p_{1}(i)\) (and otherwise set to \(0\)), and likewise set \((X_{\mathbf{x}^{\prime}})_{i}=1\) if \(U\leq p_{1}(i)^{\prime}\). Clearly, the random variables \((X_{\mathbf{x}},X_{\mathbf{x}^{\prime}})\) constructed in this manner have the \"correct\" marginal distribution; thus, we have defined a legitimate coupling. It remains to show that this coupling is contracting. Since \(\mathbf{x}\sim\mathbf{x}^{\prime}\), there is a unique coordinate on which they differ, call it \(\ell_{0}\). Observe that, conditioned on \(\mathbf{i}=\ell_{0}\), we have \(X_{\mathbf{x}}=X_{\mathbf{x}^{\prime}}\) exactly. On the other hand, when \(\mathbf{i}\
eq\ell_{0}\), the Hamming distance either stays the same or increases by \(1\), depending on \(U\). Indeed, the distance increases if and only if \(\min\{p_{1}(i),p_{1}(i)^{\prime}\}<U\leq\max\{p_{1}(i),p_{1}(i)^{\prime}\}\), and, conditioned on \(\mathbf{i}\), this happens with probability \(|p_{1}(\mathbf{i})-p_{1}(\mathbf{i})^{\prime}|\). Thus,  
\[\mathbb{E}[\mathbf{d_{\mathbf{H}}}(X_{\mathbf{x}},X_{\mathbf{x}^{\prime}})]=1-\frac{1}{M}+ \frac{1}{M}\sum_{\ell\in[M],\,\ell\
eq\ell_{0}}\left|p_{1}(\ell)-p_{1}(\ell)^ {\prime}\right|.\]  
It remains to bound the expression on the right. For a variable \(\ell\in[M]\), let \(F(\ell)\subset[n]\) be all the factors to which it is connected in \(A\); similarly, for a factor \(f\in[n]\), let \(V(f)\subset[M]\) be all the variables to which it is connected. Now,  
\[p_{1}(\ell) =\varphi\biggl{(}\lambda+\frac{1}{2\sigma^{2}}\Bigl{\{}\|\mathbf{y}- A\mathbf{x}_{\ell=0}\|^{2}-\|\mathbf{y}-A\mathbf{x}_{\ell=1}\|^{2}\Bigr{\}}\biggr{)}\] \[=\varphi\Biggl{(}\lambda+\frac{1}{\sigma^{2}}\sum_{f\in F(\ell)} \left(y_{f}-\frac{1}{2}-\sum_{k\in V(f)\setminus\{\ell\}}x_{k}\right)\Biggr{)}\,,\]  
and a similar expression holds for \(p_{1}(\ell)^{\prime}\), with \(\mathbf{x}\) replaced by \(\mathbf{x}^{\prime}\). Since \(\varphi(\cdot)\) is \(1/4\)-Lipschitz,  
\[\sum_{\ell\in[M]\setminus\{\ell_{0}\}}\bigl{|}p_{1}(\ell)-p_{1}( \ell)^{\prime}\bigr{|} \leq\frac{1}{4\sigma^{2}}\sum_{\ell\in[M]\setminus\{\ell_{0}\}} \biggl{|}\sum_{f\in F(\ell)}\sum_{k\in V(f)\setminus\{\ell\}}(x_{k}-x_{k}^{ \prime})\Biggr{|}\] \[=\frac{1}{4\sigma^{2}}\sum_{\ell\in[M]\setminus\{\ell_{0}\}} \sum_{f\in F(\ell)}\mathbf{1}_{\ell_{0}\in V(f)}\,,\]  
where we used that \(\mathbf{x}\) and \(\mathbf{x}^{\prime}\) differ only on \(\ell_{0}\). Observe that the double sum simply counts the number of pairs \((\ell,f)\) such that \(\ell_{0}\) and \(\ell\
eq\ell_{0}\) are both connected to the factor \(f\)Recalling that the degree of all variables is \(\
u\) and the degree of all factors is \(s\), which is just \(\
u(s-1)\). We conclude that  
\[\mathbb{E}[\mathbf{d}_{\text{H}}(X_{\boldsymbol{x}},X_{\boldsymbol{x}^{\prime} })]\leq\eta\,.\]0  
which is \(<1\) whenever \(4\sigma^{2}>\
u(s-1)\) ; this is exactly the condition (6), appearing in the statement of Lemma 2. Applying Theorem A1,  
\[\mathbb{E}[\mathbf{d}_{\text{H}}(X_{\boldsymbol{x}},X_{\boldsymbol{x}^{\prime} })]\leq\eta\,.\]1  
This bound is \(\leq\)\(\varepsilon\) whenever \(t\) is exceeds the quantity in Lemma 2.