# On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
## 1 Introduction
A difficulty that arises under this framework is that the sub-messages eventually have to be stitched to one long message, and a tree code was developed by [PERSON] et al. [7] for this purpose. While there has been many important advances in the field since the first appearance of the coded compressed sensing framework [19], the idea of first solving small compressed sensing problems and then leveraging the solutions to obtain estimates of the entire message still appears in one way or another in practically all schemes achieving state of the art performance. Motivated by the above, the focus of this paper is the design of sensing matrices and efficient decoding algorithms for (small dimensions) compressed sensing of binary signals. Originally, [PERSON] et al. [7] treated this challenge by designing the sensing matrix based on BCH codes and using off-the-shelf recovery algorithms, such as LASSO or non-negative least squares (NNLS), for decoding. The main weakness of this approach is that it fails to exploit the fact that the entries are binary. Later, [PERSON], [PERSON] and [PERSON] [9] suggested using Sparse regression codes with approximate message passing (AMP) decoding. The main benefit of the AMP decoder is that it allows incorporating any prior one has on the signal \(\mathbf{x}\), and not just sparsity. Consequently, it achieves excellent performance when \(\mathbf{x}\) is a binary sparse vector and the sensing matrix \(A\) is i.i.d. Gaussian. This framework has more benefits, for example it allows one to efficiently jointly decode all compressed sensing problems corresponding to the different sub-blocks and one can even iterate between the AMP decoder and the tree decoder [11]. In this paper, we propose an alternative design for a sensing matrix \(A\) and a decoding algorithm. Our sensing matrix \(A\) is taken as the parity check matrix of a low-density parity check (LDPC) code, thought of as a matrix over the reals. The decoder is based on the Markov Chain Monte Carlo (MCMC) method, more specifically, Glauber dynamics. This method performs a random walk over a Markov chain whose state space consists of all possible values of \(\mathbf{x}\) and whose stationary distribution is the conditional probability of \(\mathbf{x}\) given the measurement \(\mathbf{y}\). Due to the sparse structure of the matrix \(A\), each step in the random walk can be simulated with a low computational cost. For the compressed sensing problem with binary signals problem, our proposed framework achieves comparable performance to that of AMP with a Gaussian sensing matrix. However, in contrast to the AMP framework, which is based on sensing matrices that are Gaussian i.i.d., or \"Gaussian i.i.d.-like\", our sensing matrix is sparse. The sparsity of the sensing matrix \(A\) in compressed sensing of binary signals has several benefits that go beyond the unsourced random access application:  
* **Storage. ** Storing a sparse matrix requires fewer memory resources than storing a dense unstructured matrix, such as a matrix sampled from the i.i.d. Gaussian ensemble. We remark, however, that the AMP algorithm often works very well for compressed sensing of binary signals even when the Gaussian i.i.d. matrix \(A\) is replaced with a sensing matrix that is dense yet easy to store. For example, [PERSON] et al. [20] suggested taking \(A\) as a sub-sampled Hadamard matrix. * **Joint source-channel coding with local updates. ** Consider the problem of storing a sparse binary vector \(\mathbf{x}\in\{0,1\}^{M}\) with Hamming weight at most \(k\), in an array of \(n\) noisy memory cells. By noisy memory cells, we mean that the value read from memory cell \(i\) is modelled as \(s_{i}+z_{i}\), where \(s_{i}\) is the stored value and \(z_{i}\) is additive noise, e.g. Gaussian. This is a reasonable model for magnetic recording (ignoring intersymbol interference) [21] and for flash memories (ignoring further impairments like cross talk) [22].