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 study a random code ensemble with a hierarchical structure, which is closely related to the generalized random energy model with discrete energy values. Based on this correspondence, we analyze the hierarchical random code ensemble by using the re
plica method in two situations: lossy data compression and channel coding. For both the situations, the exponents of large deviation analysis characterizing the performance of the ensemble, the distortion rate of lossy data compression and the error exponent of channel coding in Gallagers formalism, are accessible by a generating function of the generalized random energy model. We discuss that the transitions of those exponents observed in the preceding work can be interpreted as phase transitions with respect to the replica number. We also show that the replica symmetry breaking plays an essential role in these transitions.
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.
