"Compressed Sensing" is an active research area which touches on harmonic analysis, geometric functional analysis, applied mathematics, computer science electrical engineering and information theory. Concrete achievements, such as speeding up pediatric MRI acquistion times from several minutes to under a minute, are now entering daily use. In my talk I will discuss the notion of phase transitions in combinatorial geometry, describe how they precisely demarcate the situations where a popular algorithm in compressed sensing -- ell_1 minimization -- can succeed. Then I will discuss the issue: what is the best possible phase transition of any algorithm? We get different answers depending on the assumptions we make. If we assume the distribution of the coefficients is known/unknown, we get different answers; in each case I describe novel algorithms precisely achieving the optimal phase transition, converging to the answer at an expoential rate depending only on distance from phase transition. Both algorithms are applications of the Approximate Message Passing algorithm introduced by Maleki, Montanari and myself. This talk surveys joint work with several authors, including Andrea Montanari and Jared Tanner, as well as Adel Javanmard, Iain Johnstone and Arian Maleki.