Formulating Binary Compressive Sensing Decoding with Asymmetrical Property

This paper mathematically analyzes the verification based message passing decoder for the binary compressive sensing (CS) compression problem, toward the goal of judging whether the decoding will be successful prior to the decoding process and of providing design guidelines of sensing matrices for better coding performance. For a biased binary source with unequal percentage of bit “0” and “1”, we observe that the recovery probabilities for bit “0” and “1” are different during each round of evolution in the decoding process. We refer to this property as asymmetrical recovery. To authors’ best knowledge, this paper is the first one to formulate CS decoding by taking the asymmetrical recovery into account. With the new formulation, the recursion of unrecoverable probability of source bits can be characterized more precisely than previous formulations. Furthermore, as an important property of CS decoding, we also characterize the variation on asymmetrical recovery in different rounds of evolution. The simulation results show that the new formulation has a close match with the actual decoding. Finally, we derive design guidelines for random sensing matrices from the source coding perspective.