The 1-bit compressed sensing framework enables the recovery of a sparse vector x from the sign information of each entry of its linear transformation. Discarding the amplitude information can significantly reduce the amount of data, which is highly b
eneficial in practical applications. In this paper, we present a Bayesian approach to signal reconstruction for 1-bit compressed sensing, and analyze its typical performance using statistical mechanics. Utilizing the replica method, we show that the Bayesian approach enables better reconstruction than the L1-norm minimization approach, asymptotically saturating the performance obtained when the non-zero entries positions of the signal are known. We also test a message passing algorithm for signal reconstruction on the basis of belief propagation. The results of numerical experiments are consistent with those of the theoretical analysis.
We discuss the universality of the L1 recovery threshold in compressed sensing. Previous studies in the fields of statistical mechanics and random matrix integration have shown that L1 recovery under a random matrix with orthogonal symmetry has a uni
versal threshold. This indicates that the threshold of L1 recovery under a non-orthogonal random matrix differs from the universal one. Taking this into account, we use a simple random matrix without orthogonal symmetry, where the random entries are not independent, and show analytically that the threshold of L1 recovery for such a matrix does not coincide with the universal one. The results of an extensive numerical experiment are in good agreement with the analytical results, which validates our methodology. Though our analysis is based on replica heuristics in statistical mechanics and is not rigorous, the findings nevertheless support the fact that the universality of the threshold is strongly related to the symmetry of the random matrix.
We provide a scheme for exploring the reconstruction limit of compressed sensing by minimizing the general cost function under the random measurement constraints for generic correlated signal sources. Our scheme is based on the statistical mechanical
replica method for dealing with random systems. As a simple but non-trivial example, we apply the scheme to a sparse autoregressive model, where the first differences in the input signals of the correlated time series are sparse, and evaluate the critical compression rate for a perfect reconstruction. The results are in good agreement with a numerical experiment for a signal reconstruction.
We investigate a reconstruction limit of compressed sensing for a reconstruction scheme based on the L1-norm minimization utilizing a correlated compression matrix with a statistical mechanics method. We focus on the compression matrix modeled as the
Kronecker-type random matrix studied in research on multi-input multi-output wireless communication systems. We found that strong one-dimensional correlations between expansion bases of original information slightly degrade reconstruction performance.
