# On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
## 2 Compressed Sensing of Binary Signals
### Sensing Matrices from LDPC Codes  
We consider sensing matrices based on [PERSON]'s ensemble of LDPC codes [47]. Denote by \(\mathbf{LDPC}(\
u,s;M,n)\) the following ensemble of random bipartite and biregular graphs, described below:  
* One side of the graph has \(M\) vertices, which we call \"variables\" (the left side), and the other has \(n\) vertices, called \"factors\" (the right side). * For simplicity, assume \(vM=sn\). Each variable has degree \(\
u\), meaning it is connected to exactly \(\
u\) factors; each factor has degree \(s\). Thus, there are exactly \(vM=sn\) edges in the graph. * The edges of \(\mathcal{G}\sim\mathbf{LDPC}(\
u,s;M,n)\) are sampled according to the following procedure. The procedure runs in \(\
u\) rounds, so that in every round one introduces \(M/s\) new factors (we assume \(M/s\) is integer for simplicity), by randomly partitioning the variables \([n]\) into \(M/s\) parts of size \(s\) each, namely, \[[n]=\bigcup_{i=1}^{M/s}S_{i}\,,\quad S_{i}\cap S_{j}=\emptyset,\quad|S_{i}|=s \quad\text{for all }1\leq i,j\leq n\,,i\
eq j\,.\] For every new factor \(1\leq i\leq M/s\) introduced in this round, one adds an edge between \(i\) and all the variables in the corresponding \(S_{i}\). The sensing matrix \(A\in\{0,1\}^{n\times M}\) is taken to be the adjacency matrix of a randomly sampled graph \(\mathcal{G}\sim\mathbf{LDPC}(\
u,s;M,n)\), that is, \[A_{i,j}=A(\mathcal{G})_{i,j}= \begin{cases}1&\text{there is an edge in }\mathcal{G}\text{ between factor }i\text{ and variable }j\\ 0&\text{otherwise}\end{cases} .\] The idea of constructing sensing matrices from bipartite graphs is not new. It is known that when \(\mathcal{G}\) is a sufficiently good expander, the corresponding adjacency matrix \(A\) is a good sensing matrix (see, e.g., [48; 49; 50; 51], ([25], Chapter 13) and the references therein). Specifically, ensembles of LDPC codes have also been considered previously for compressed sensing [52; 53; 54]. It is worthwhile to recall at this point that the recovery problem we consider here is more structured than the \"standard\" compressed sensing setup: on top of being sparse, we assume the unknown signal is _binary_, and in particular _non-negative_. Past results show that the non-negativity assumption may give a considerable advantage in terms of the required number of measurements, as well as robustness to noise (see, e.g., [26; 42; 43; 44; 45; 55]). We especially mention the results of [PERSON] et al. [55]. We say that a bipartite graph with left degree \(\
u\) is an \((r,\varepsilon)\)-expander if for every set \(|S|\leq r\) of left vertices, one has \(|N(S)|\geq(1-\varepsilon)\
u|S|\), \(N(S)\) being the neighbors of vertices in \(S\). The results of [PERSON] et al. [55] state that a bipartite left-regular \((r,1-1/\
u)\)-expander yields, after applying a very small perturbation to the entries of the adjacency matrix, a sensing matrix where all **non-negative**\(\lceil r/\
u-1\rceil\) sparse vectors \(\mathbf{x}\) can be recovered from \(\mathbf{y}=Ax\) (noiseless measurements). This guarantee, for non-negative signals, is _considerably_ better than what one has without the non-negativity constraint--to get recoverability guarantees for \"general\" compressed sensing, one needs considerably larger expansion (smaller \(\varepsilon\)) (see, e.g., [25], Chapter 13). There are well-known connections between the decodability of LDPC codes and their expansion properties [56]. For example, for a slightly different ensemble of LDPC codes (that contains [PERSON]'s ensemble), one can show ([56], Theorem 8.7) (this result first appeared in [57]) that, with high probability, a random graph is an \((\alpha^{*}M,1-1/\
u)\)-expander, where \(\alpha^{*}\) is the positive solution of \[\frac{\
u-1}{\
u}h_{2}(\alpha)-\frac{1}{s}h_{2}\Big{(}\alpha\frac{s}{\
u}\Big{)} -\alpha\frac{s}{\
u}h_{2}\Big{(}\frac{\
u}{s}\Big{)}=0\,,\] and \(h_{2}(p)=-p\log(p)-(1-p)\log(1-p)\) is the binary entropy function.