The cavity method for phase transitions in sparse reconstruction algorithms

Compressed sensing methods are capable of reconstructing high-dimensional sparse signals using a limited amount of measurements under certain conditions. The boundaries of good performance of compressed sensing methods are associated with certain phase transitions when the number of variables go to infinity. Many compressed sensing methods are formulated as optimization problems. Usual statistical physics approach to this problem involves inventing a finite temperature version of the problem, analyzing the mean field theory via replica trick, and, then taking the zero temperature limit. Although this method has been very successful in reproducing the observations, the replica trick and the non-trivial zero temperature limit obscure the essential reasons for failure of a compressed sensing algorithm. In this work, we employ the cavity method to give an alternative derivation of the phase transitions, working solely with the zero-temperature limit and providing insight into the origin of different terms in the mean field self-consistency equations. The cavity method naturally invokes a susceptibility which is central to understanding different phases in this system, and could be generalized to a much broader class of compressed sensing problems.