# On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
## 2 Compressed Sensing of Binary Signals  
We now define a formal mathematical model for the problem studied in this paper. Consider a linear inverse problem of the form  
\[\mathbf{y}=A\mathbf{x}+\sigma\mathbf{z}, \tag{1}\]  
where \(\mathbf{x}\in\mathbb{R}^{M}\) is an unknown signal, to be recovered; \(A\in\mathbb{R}^{n\times M}\) is a (known) linear measurement matrix; and \(\mathbf{z}\in\mathbb{R}^{n}\) is i.i.d. Gaussian noise: \(z_{1},\ldots,z_{n}\overset{i.i.d.}{\sim}\mathcal{N}(0,1)\). This problem becomes especially interesting in the _under-determined regime_, where the number of samples\(n\) is smaller than the signal dimension \(M\)--here, clearly, one cannot recover \(x\) generically, and it is necessary to make additional structural assumptions on \(x\). In compressed sensing, one assumes that \(x\) is a sparse vector, where the number of non-zero entries \(k\) is very small compared to \(M\). Perhaps the most fundamental result in sparse recovery states that, in order to recover exactly any \(k\)-sparse \(x\) from noiseless measurements \(\mathbf{y}=A\mathbf{x}\), one in fact needs only \(n=O(k\log(M/k))\) linear measurements, where the sensing matrix \(A\) is taken to be an i.i.d. Gaussian random matrix (see, e.g., [25], Chapter 9). The recovery procedure itself, while not linear, can be formulated as a convex program which is computationally easy to solve. In recent years, a vast literature on compressed sensing has formed, spanning new theory, low-complexity algorithms and new constructions of good sensing matrices, beyond the i.i.d. Gaussian setup. We make no pretense to give a literature review on this topic; for a starting point, we refer primarily to surveys [25; 26; 27; 28; 29; 30; 31; 32; 33; 34]. We consider a setting where \(x\) is constrained to be in a discrete set, on top of being sparse. Specifically, we assume it is binary: \(\mathbf{x}\in\{0,1\}^{M}\). As described above, this problem is closely related to communication over the unsourced random access channel, but problems of this form have received some attention in the past (see, e.g., [35; 36; 37; 38]). Throughout, we assume a sparse binary prior for \(x\). Specifically, let \(k\) be the expected sparsity, and denote \(\rho=k/M\). The coordinates of \(x\) are assumed i.i.d. Bernoulli random variables:  
\[x_{1},\ldots,x_{M}\overset{i.i.d.}{\sim}\text{Bernoulli}(\rho), \tag{2}\]  
that is, \(\Pr(x_{i}=1)=\rho\) and otherwise \(x_{i}=0\). Clearly, the expected number of non-zero entries is just \(\mathbb{E}\|\mathbf{x}\|_{0}=k\). A recovery algorithm for \(\mathbf{x}\) from \(\mathbf{y}\) is a mapping \(\hat{\mathbf{x}}:\mathbb{R}^{n}\to\{0,1\}^{M}\). The performance of a recovery algorithm is measured in terms of the bit error rate (BER) it attains  
\[\text{BER}(\mathbf{x},\widehat{\mathbf{x}})=\frac{1}{k}\sum_{i=1}^{M}\Pr(x_{i}\
eq \widehat{x}_{i}(\mathbf{y})), \tag{3}\]  
where the probability is taken with respect to both the additive noise, as described in (1), and the signal prior (2). Note that the normalization in (3) is by the expected sparsity \(k\), rather than by the length \(M\) of the vector \(\mathbf{x}\). Since typically \(k\ll M\) in compressed sensing, normalizing by \(M\) would yield a very small BER for any reasonable estimator, and normalizing by \(k\) therefore makes more sense. Given a signal dimension \(M\) and budget of measurements \(n\), one would typically like to: (i) construct \"good\" sensing matrices \(A\) that allow for noise-robust recovery of signals with as little sparsity (large \(k\)) as possible; and (ii) come up with low-complexity recovery algorithms for recovering \(x\) from \(\mathbf{y}\). As for Point (ii), note that one would like to go beyond off-the-shelf compressed sensing algorithms, such as the LASSO [39; 40; 41] or Non-Negative Least Squares (NNLS) [7; 42; 43; 44; 45; 26; 46], which are designed with any real or positive signal in mind, and find algorithms that explicitly leverage the binary structure of the signal, to attain an advantage in terms of recovery performance.