Analysis of Sparse Recovery Algorithms via the Replica Method

This manuscript goes through the fundamental connections between statistical mechanics and estimation theory by focusing on the particular problem of compressive sensing. We first show that the asymptotic analysis of a sparse recovery algorithm is mathematically equivalent to the problem of calculating the free energy of a spin glass in the thermodynamic limit. We then use the replica method from statistical mechanics to evaluate the performance in the asymptotic regime. The asymptotic results have several applications in communications and signal processing. We briefly go through two instances of these applications: Characterization of joint sparse recovery algorithms used in distributed compressive sensing, and tuning of receivers employed for detection of spatially modulated signals.