Cavity method and belief propagation can be used to analyze asymptotic properties of random inference problems. In this talk I will describe and explain several phase transitions that arise in those problems, and discuss their algorithmic consequences. Depending on the parameters of the problem three distinct phases appear where inference is impossible, hard or easy. These results are very general and will be illustrated on the examples of compressed sensing and community detection in networks. In a second part I will show how these findings can be used to design significantly improved compressed sensing method.
Copyright. All Rights Reserved.